Shortest Paths Algorithm Using Topological Sort and Vertex Relaxation
Spoiler Alert: This algorithm can also be used to find Longest Paths! Time Complexity: O(E + V). Space Complexity: O(V)

Customer Support: admin@thealgorists.com

Feedback:
We are listening to your every feedback,
and taking action to constantly improve your learning experience.
If you have any feedback, please use this form:
https://thealgorists.com/Feedback.
Prerequisite: Shortest Path Algorithms Fundamentals and Dijkstra's Algorithm
We can very easily find Shortest Path in a graph by using Topological Sort and Vertex Relaxation operation discussed in our previous chapter. The only restriction is that the graph cannot have a cycle. This limitation comes from the core concept of Topological Sort. If there is a cycle we cannot have a Topological Sort in the first place.
How it works is very simple: first do a Topological Sort of the given graph. Then relax each of the vertices in the order they appear in the topological sort.
Why it works is pretty darn simple: say, we have a graph with V number of vertices labeled as 0 to (V  1), and topSort[] is the array which contains the vertices in topological order. Now we are iterating over the array from index 0 to all the way to the index (V  1) and relaxing each of these vertices (in topological order). Now think, when we are at index i (where 0 < i < V) what can we say about the vertex i ? We have processed all the vertices from which we have inbound edge(s) to vertex i, and we have relaxed all those parent vertices (immediate parents of vertex i) already. Which means we have already computed which inbound edge to vertex i contributes to the shortest path. In short, vertex i is already processed and we have the shortest path and distance for vertex i. This is true for all the vertices 0 to (V  1). This is how this approach computes the shortest paths from a source to any vertex in a given graph.
Let's take a look at the code now. If you already gone through the code for Dijkstra's Algorithm in the previous chapter, then this code would look very similar, since we will try to maintain the same template, so that by the end of this section we have a standardized template for solving Shortest Path Problems.
This is a Premium content.
Please subscribe to Algorithms course to access the code.
Time Complexity:
Time Complexity to do Topological Sort: O(E + V), Please refer to https://www.thealgorists.com/Algo/TopologicalSortTime Complexity to do Vertex Relaxation for all vertices: O(E + V), since we relax all E edges and we the foreach loop is O(V).
Overall Time Complexity: O(E + V) + O(E + V) = O(E + V)
We cannot use Dijkstra's Algorithm to efficiently find Longest Paths from a source to all other vertices in a graph.
But Topological Sort Approach can be efficiently used to find Longest Paths as well, which we will
discuss in a later chapter focusing mainly on finding Longest paths
.
Related MustRead Topics:
 Dijkstra's Algorithm
 Longest Paths Algorithm
 BellmanFord Algorithm & Negative Cycle Detection
 Optimized BellmanFord
 Sequential Job Scheduling
 Parallel Job Scheduling

Parallel Job Scheduling
w/ Relative Deadlines  Arbitrage
The above content is written by:
Abhishek Dey
A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More
Microsoft  University of Florida
If you have any feedback, please use this form: https://thealgorists.com/Feedback.
Follow Us On LinkedIn