Last Updated: 27 Dec, 2020
Dijkstra's shortest path
Easy
Asked in companies
You have been given an undirected, connected graph of ‘V’ vertices (labelled from 0 to V-1) and ‘E’ edges. Each edge connecting two nodes 'u' and 'v' has a weight denoting the distance between them.
Your task is to find the shortest path distance from the source node 'S' to all the vertices. You have to return a list of integers denoting the shortest distance between each vertex and source vertex 'S'.
Note:
1. There are no self-loops(an edge connecting the vertex to itself) in the given graph.
2. There are no parallel edges i.e no two vertices are directly connected by more than 1 edge.
For Example:
Input:
4 5
0 1 5
0 2 8
1 2 9
1 3 2
2 3 6
The source node is node 0.
The shortest distance from node 0 to node 0 is 0.
The shortest distance from node 0 to node 1 is 5. In the above figure, the green path represents this distance. The path goes from node 0->1, giving distance = 5.
The shortest distance from node 0 to node 2 is 8. In the above figure, the pink path represents this distance. The path goes from node 0->2, giving distance = 8.
The shortest distance from node 0 to node 3 is 7. In the above figure, the yellow path represents this distance. The path goes from node 0->1->3, giving distance = 7.
Input format:
The first line contains three space-separated integers ‘V’, ‘E’ and 'S', denoting the number of vertices, the number of edges in the undirected graph and starting vertex, respectively.
The next ‘E’ lines each contain three single space-separated integers ‘u’, ‘v’, and ‘distance’, denoting a node ‘u’, a node ‘v’, and the distance between nodes (u, v), respectively.
Output format:
The only line contains the list of integers denoting the shortest distance between each node and source vertex 'S'.
Approaches
The idea is to maintain two arrays, one stores the visited nodes, and the other array stores the distance (element at index ‘i’ denotes the distance from node 0 to node ‘i’). We pick an unvisited minimum distance vertex, then update the distance of all its adjacent vertices considering the path from source to an adjacent vertex to pass through the picked minimum distance vertex. Repeat the process till all nodes are visited.
Steps:
- We will make an adjacency matrix of size ‘V*V’, initialize all the positions to 0. Now, update the distance between two vertices in the matrix (denoted by the row number and column number) to the given distance in the input.
- We also initialize the distance vector to ‘INT_MAX’ and the visited nodes vector to false. Since the distance of the source node i.e. node 0 to itself will be 0, update ‘distance[0]’ to 0.
- Now, we find the shortest path for all vertices using the steps below:
- We pick the minimum distance vertex, which is not yet visited, let’s say ‘u’. Mark it as true in the visited vector.
- We update the distances of the adjacent vertices. Update distance[v] only if vertex ‘v’ is not already visited and the current distance of the vertex ‘v’ is greater than the distance from source vertex 0 to vertex ‘u’ plus the distance from ‘u’ to ‘v’.
- Repeat the above steps till all the vertices are visited.
- Return the distance vector, which is our required solution.
The idea is to use a priority queue which creates a min-heap for us. In the priority queue, we will be storing the ‘distance’ and node ‘v’ which will give us the minimum distance vertex. We will pick an unvisited minimum distance vertex which will be the first element of the priority queue, then update the distance of all its adjacent vertices (using adjacency list) considering the path from source to an adjacent vertex to pass through the picked minimum distance vertex. Repeat the process till the priority queue is empty.
Steps:
- We will make an adjacency list that will be storing the two nodes between which an edge exists. We initialize the distance vector to ‘INT_MAX’ and the visited nodes vector to false.
- Since the distance of the source node i.e node 0 to itself will be 0, update ‘distance[0]’ to 0.
- Now, we find the shortest path for all vertices using the steps below:
- Pick the first element of the priority queue, which will give the minimum distance vertex which is not yet visited, let’s say ‘u’. Pop it from the priority queue and mark it as true in the visited vector.
- Iterate through the adjacency list to find all the adjacent vertices to the vertex ‘u’.
- Now, update the distances of the adjacent vertices. Update distance[v] only if vertex ‘v’ is not already visited and the current distance of the vertex ‘v’ is greater than the distance from source vertex 0 to vertex ‘u’ plus the distance from ‘u’ to ‘v’.
- Repeat the above steps till the priority queue is not empty.
- Return the distance vector, which is our required solution.