Find Cost of Shortest Path in DAG using one pass of Bellman-Ford

Given a directed acyclic graph (DAG) and a source vertex, find the cost of shortest path from source vertex to all other vertices present in the graph. If vertex can’t be reached from given source vertex, print its distance as infinity.

For example, consider below DAG,
 

Shortest Path in DAG

The shortest distance of source vertex 7 to


vertex 0 is  6 (7 —> 0)
vertex 1 is -2 (7 —> 5 —> 1)
vertex 2 is -6 (7 —> 5 —> 1 —> 2)
vertex 3 is  4 (7 —> 3)
vertex 4 is -1 (7 —> 5 —> 1 —> 4)
vertex 5 is -4 (7 —> 5)
vertex 6 is  6 (7 —> 5 —> 1 —> 6)

 


 

We know that a Topological Sort of a directed acyclic graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering.

topological order shortest path

We can use topological sort to solve this problem. When we consider a vertex u in topological order, it is guaranteed that we have considered every incoming edge to it. Now for each vertex v of the DAG in the topological order, we relax cost of its outgoing edges (update shortest path information). In order words since we have already found shortest path to vertex v, we can use that info to update shortest path of all its adjacent vertices. i.e.

for each vertex u in topological order
    for each edge (u, v) with weight w
        if distance[u] + w < distance[v]

            distance[v] = distance[u] + w

C++

Download   Run Code

Output:

Shortest distance of source vertex 7 to vertex 0 is 6
Shortest distance of source vertex 7 to vertex 1 is -2
Shortest distance of source vertex 7 to vertex 2 is -6
Shortest distance of source vertex 7 to vertex 3 is 4
Shortest distance of source vertex 7 to vertex 4 is -1
Shortest distance of source vertex 7 to vertex 5 is -4
Shortest distance of source vertex 7 to vertex 6 is 6
Shortest distance of source vertex 7 to vertex 7 is 0

Time complexity of above solution is O(n + m) where n is number of vertices and e is number of edges in the graph.
 

A related problem is to find the longest paths from given source vertex to all other vertices present in the graph. We can easily solve this problem by following above logic as well. The idea is to consider negative weights of the edges in the graph and find the shortest path from given source in the graph. Then the cost of longest path will be just negative of its cost of shortest path for any given vertex.

Check what Wikipedia has to say for Acyclic graphs –

A longest path between two given vertices s and t in a weighted graph G is the same thing as a shortest path in a graph – G derived from G by changing every weight to its negation. Therefore, if shortest paths can be found in -G, then longest paths can also be found in G. For most graphs, this transformation is not useful because it creates cycles of negative length in -G. But if G is a directed acyclic graph, then no negative cycles can be created, and a longest path in G can be found in linear time by applying a linear time algorithm for shortest paths in -G, which is also a directed acyclic graph

The implementation can be seen here.

 
References: https://en.wikipedia.org/wiki/Topological_sorting#Application_to_shortest_path_finding

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
kuril
Guest
kuril

the sign in algo is opposite > it should be < coz we are updating distance when we are getting minimum than current one
Admin please correct it

wpDiscuz