Shortest Paths Algorithm Using Topological Sort and Vertex Relaxation
Get started
জয় শ্রী রাম
🕉Pre-requisite: 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.
Login to Access Content
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 Must-Read Topics:
- Dijkstra's Algorithm
- Longest Paths Algorithm
- Bellman-Ford Algorithm & Negative Cycle Detection
- Optimized Bellman-Ford
- Sequential Job Scheduling
- Parallel Job Scheduling
-
Parallel Job Scheduling
w/ Relative Deadlines - Arbitrage
