educative.io

Graph--> Data Structure --> Find the shortest path

Courses
,
#1

Hi
In this question ( Find the Shortest Path Between Two Vertices) from the data structure module from ACE Python skill path, should the following bolded part of the condition be removed(temp.data is b)? I ran the code without it and passed the test and was accepted. I’m not sure why it is there. Can you please guide me in this regard?

while temp is not None:
if not visited[temp.data] or temp.data is b:
queue.enqueue(temp.data)
visited[temp.data] = True
distance[temp.data] = distance[current_node] + 1
if temp.data is b:
return distance[b]
temp = temp.next_element

Course: https://www.educative.io/collection/5642554087309312/5634727314718720
Lesson: https://www.educative.io/collection/page/5642554087309312/5634727314718720/5687682516647936

#2

Hi @Setarehalsadat_Chang !!
The condition temp.data is b is helpful in the following case:

  1. When there are multiple paths from vertex a to vertex b.
  2. The goal is to find the shortest path between a and b.

In such cases, without the condition temp.data is b, the algorithm would continue exploring other paths even after finding a path to b. This can be inefficient because once the shortest path to b is found, there is no need to continue exploring other paths.

By including the condition temp.data is b, the algorithm will immediately return the distance when the destination vertex is encountered. This can significantly improve the efficiency of the algorithm in cases where there are multiple paths and the goal is to find the shortest path.
Here’s an example of a graph where the condition temp.data is b would be helpful:

Consider the following graph:

     1
   /   \
  2     3
   \   / \
    4     5
     \   /
       6

In this graph, there are multiple paths from vertex 1 to vertex 6:

  1. Path 1: 1 → 2 → 4 → 5 → 6 (distance = 4)
  2. Path 2: 1 → 3 → 5 → 6 (distance = 3)

Let’s say we want to find the shortest path from vertex 1 to vertex 6 using the find_min function. If we remove the condition temp.data is b, the algorithm will continue exploring both paths, even after finding the shortest path (Path 2).

However, if we include the condition temp.data is b, the algorithm will terminate as soon as it encounters vertex 6 (destination vertex) along Path 2. It will return the distance of 3, indicating that it has found the shortest path.

So, in this example, the condition temp.data is b is helpful in ensuring that the algorithm terminates early and returns the shortest path from vertex 1 to vertex 6.
I hope it helps. Happy Learning :blush: