graphtopological-sortlongest-path

Why is topological sort needed for Longest Path in Directed Acyclic Graph?


Problem: Given a Weighted Directed Acyclic Graph (DAG) and a source vertex s in it, find the longest distances from s to all other vertices in the given graph.

Please find the reference graph: link

Why do we need topological sorting? Can we not simply use modified BFS from source vertex. Why do we care so much about the linear ordering.

If this is a repetition then kindly redirect me to relevant answers.

Thanks


Solution

  • If we don't sort it, we don't know which adjacent vertex to choose first and it may lead to a situation where we use distance of a vertex v to update distances of its adjacent vertices adj[v], but after that, the distance of vertex v gets updated, so vertices from adj[v] could also get bigger distances, but we won't visit them anymore.

    Example based on the graph you have referenced (http://www.geeksforgeeks.org/wp-content/uploads/LongestPath.png):
    Let's say that at this step:
    Step 1
    Say, we start to traverse the graph from vertex '0', and we choose vertex with distance 6 (instead of vertex with distance 2, which we would have chosen if we had used topological order). Already processed vertices are green, vertex currently being processed is red:
    Step 2
    We have updated the distance of the last vertex to 7 and we won't increase it, however if we had visited vertex with distance 2 in previous step, the distance of this vertex would have been 10: Step 3