Last Updated: 12 Jun, 2023
Shortest Path in DAG
Moderate
Asked in company
You are given a directed acyclic graph of 'N' vertices(0 to 'N' - 1) and 'M' weighted edges.
Return an array that stores the distance(sum of weights) of the shortest path from vertex 0 to all vertices, and if it is impossible to reach any vertex, then assign -1 as distance.
For Example:
'N' = 3, 'M' = 3, 'edges' = [0, 1, 2], [1, 2, 3], [0, 2, 6]].
Distance (0 to 0) = 0.
Distance (0 to 1) = 2.
Distance (0 to 2) = 0->1 + 1->2 = 2+3 = 5.
So our answer is [0, 2, 5].
Input format:
The first line contains two integers, 'N', and 'M'.
The next 'M' lines contain three integers each, 'u', 'v', and 'w', representing there is a directed edge from 'u' to 'v' of weight 'w'.
Output format:
The only line contains an array that stores the distance(sum of weights) of the shortest path from vertex 0 to all vertices, and if it is impossible to reach any vertex, then assign -1 as distance.
Note:
You don’t need to print anything, it has already been taken care of. Just complete the given function.
Approaches
Approach:
- We can use the Dijkstra algorithm to find the shortest distances.
- In the Dijkstra algorithm, we start with 0 and traverse to all other vertex and update the shortest distance.
- After Calculating all the shortest distances, we can return the array 'dis'.
Algorithm:
- Create an adjacency list 'adj' using given edges, which stores {destination, weight}.
- Initialize a priority queue 'pq', which stores the distance of any vertex with 0 and that vertex.
- Initialize array 'dis' of size 'N' with 10^9.
- Assign dis[0] equals 0.
- Insert {dis[0],0} in 'pq'.
- While 'pq' is non-empty:
- 'd' and 'u' be the values from the top of the priority queue.
- Remove the top element from 'pq'.
- Traverse using [v,w] in adj[u]:
- if(dis[v]>d+w)
- Update dis[v] and insert {dis[v], v} in 'pq'.
- if(dis[v]>d+w)
- If 'dis[i]' is 10^9 for some vertex 'i', then assign -1 in 'dis[i]'.
- Return 'dis'.
Approach:
- First, find the topological sort of the given graph.
- Now, we can start traversing, starting with 0 to go to other vertices.
- While traversing, we take vertex in the order they are present in topological sort and update the shortest distances simultaneously.
- After Updating all distances, we can return all the shortest distances.
Algorithm:
- Create an adjacency list 'adj' using given edges, which stores {destination, weight}.
- Initialize an empty stack 'st'.
- Call the dfs function to get the topological sort in 'st'.
- Initialize array 'dis' of size 'N' with 10^9.
- Assign dis[0] equals 0.
- While 'st' is non-empty:
- 'u' be the value from the top of the 'st'.
- Remove the top element from 'st'.
- Traverse using [v,w] in adj[u]:
- if(dis[v]>dis[u]+w)
- Update dis[v].
- if(dis[v]>dis[u]+w)
- If 'dis[i]' is 10^9 for some vertex 'i', then assign -1 in 'dis[i]'.
- Return 'dis'.