Find shortest paths in DAG using Topological order
Shortest path problem can be defined as a problem to find minimum distance between two vertices/nodes of connected weighted graph.Dijkstra’s algorithm is an efficient algorithm for finding shortest path in a connected weighted graph. But the Dijkstra’s algorithm does not work with negative edge weights. The below graph is containing negative weight in it, so Dijkstra’s algorithm will not work. The given graph is acyclic and directed so its topological order is possible and in this case it is possible to find shortest path from a given source.
Steps to find longest distance form Source S to all other vertices based on topological order
- Represent the graph as Adjacency matrix or Adjacency List. Here we are going to use Adjacency matrix.
Topologically sort the vertices of graph.
- Traverse the graph in topological order, update the min distance as below.
For each vertex u ,taken from topological order For each adjacent vertex v of u if (dist[v] > dist[u] + weight(u, v)) dist[v] = dist[u] + weight(u, v)
Here we have already calculated the longest path based on topological sort. http://wikistack.com/longest-path-propbem-in-directed-acyclic-graph-using-topological-sort/.
We can modify the source code and can find shortest path. Let us read the link and modify the source code for shortest path for given graph (above).