Algorithms and Data Structures: TheAlgorist.com
System Design: SystemsDesign.Cloud
Low Level Design: LowLevelDesign.io
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.
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/TopologicalSort
Time 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
If you have any feedback, please use this form: https://thealgorists.com/Feedback.
Follow Us On LinkedIn