🙏

জয়  শ্রী  রাম

🕉

---

When it comes to Shortest Path Algorithms, we most commonly hear about Dijkstra's Algorithm, Bellman-Ford Algorithm, and Topological Sort with Vertex Relaxation. It is very important to know why we should learn all these algorithms to apparently serve the same purpose. This clear understanding will help you to confidently decide which algorithm to use depending on the problem you are solving.

• Dijktra's Algorithm cannot be used if there is one or more edges with negative weight.
  Having one or more cycles in the graph is fine.
  
  
• Topological Sort with Vertex Relaxation approach for finding shortest paths cannot be used if there is any cycle in the graph. In fact, a graph with cycle(s) has no Topological Sort.
  Having edges with negative weight is fine.
  
  
• Bellman-Ford Algorithm can handle both: (1) Edges with negative weight, (2) Cycles.
  So you might be thinking if Bellman-Ford Algorithm can handle both then why we even bother to learn Dijkstra's algorithm and Topological Sort w/ Vertex Relaxation approach in the first place. It is because among all these three algorithms, Bellman-Ford Algorithm has the worst time complexity.
  
  

Please note that, none of the above three algorithm can be used if there is a negative cycle in the graph. Whenever I say cycle, I mean a positive cycle. A positive cycle is a cycle, for which if you add up the weights of all the edges the sum of the weights that you would get, would be zero or more.
A cycle can have one or more edges with negative weight, this is not a problem. A cycle is a negative cycle only when the sum of the weights of all the edges in the cycles is negative.
A graph with negative cycle is an ill-posed problem for shortest path problem, because you can just spin a negative cycle multiple times just to get a path with lower and lower weight.

So we see that the characteristics of the graph we are working on will have huge influence on which algorithm(s) can or cannot be used to find shortest path. To summarize, below are the characteristics of the graph that we are interested in:

• Presence of one or more edges with negative weight.
• Presence of Cycle.
• Presence of Negative Cycle. A cycle is a negative cycle only when the sum of the weights of all the edges in the cycles is negative.

All the algorithms we discuss here can be used in any problem where we can convert the problem in a graph and reduce the problem to a finding shortest path(s) problem. Some very common use cases are:

• Map Application or Navigation/GPS system: The vertices of the graph will represent intersections of the roads and the edges will represent the roads.
• Computer Network: The vertices will represent router, and the edges will represent connections between any pair of routers.
• Job Schedule: Vertices -> Jobs. Edges -> Precedence. We will have a dedicated series of contents just on discussion on how to solve problems similar in concept as that of Job Schedules.

All of these algorithms are based on the concept of Relaxation : Edge Relaxation and Vertex Relaxation. As we will see Edge Relaxation is actually part of Vertex Relaxation.
We would also always have a source vertex. Our goal would be to find the shortest path starting from this source vertex, to some other vertex. We would call this other vertex destination vertex.

• Edge Relaxation

  Say, a directed edge connects vertex u to vertex v and is directed from u to v, which means this is an inbound edge of vertex v.
  
  Edge Relaxation is all about finding out whether the current inbound edge under consideration contributes towards having a shorter distance to reach vertex v from the source than that it is right now. And how is this distance calculated ? In general, if there is a path from source vertex (starting vertex) to vertex v through a vertex u then distance to v from source = distance from source to vertex u + distance from u to v.
  Now if uv is an inbound edge of vertex v then distance to v from source = distance from source to u + weight of the directed edge uv.

          
  private void relax(int[] edge, int edgeWeight) { 
      int fromVertex = edge[0]; 
      int toVertex = edge[1]; 
  
      // is path through fromVertex to toVertex shorter than current distance of v from source ?
      if (distance[toVertex] > distance[fromVertex] + edgeWeight) {  // distance[i] is the current
                                        // shortest distance from source to node i
          distance[toVertex] = distance[fromVertex] + edgeWeight;
          parent[toVertex] = fromVertex; // parent[i] array keeps track of which vertex comes before
                                          // before vertex i in a path. parent[] array helps in
                                          // reconstructing the shortest path from source to a vertex.
      }
  }
              
          

• Vertex Relaxation

  All the shortest path algorithms we will be discussing here, would involve the following:
  • For one or more vertices u we would need to check for all its outbound directed edges u -> v, whether having a route from source to v through u would result in a shorter route than the one that already exist from source to v. So basically for some vertices u we would have to relax all of its outbound edges. What we just did here is vertex relaxation. We relaxed the vertex u by relaxing all its outbound directed edges.
  Let's suppose that we are given a directed graph which has n number of vertices. The vertices are labeled from 0 to (n - 1). The graph is represented by adjacency list.
  adjacencyList[i] would give you all the outbound directed edges from vertex i.
  We also have weight[][] array.
  weight[i][j] gives you the weight for the directed edge i -> j.

          
  private void relax(List< int[] > adjacencyList, int[][] weight, int vertex) {
      for (int adjacentVertex : adjacencyList.get(vertex)) { // adjacencyList.get(vertex) will give all the adjacentVertices of vertex
          int edgeWeight = weight[vertex][adjacentVertex]; 
          if (distance[adjacentVertex] > distance[vertex] + edgeWeight) { 
              distance[adjacentVertex] = distance[vertex] + edgeWeight;
              parent[adjacentVertex] = vertex; 
          }
      }
  }
  
  OR,
  
  private void relax(List< int[] > adjacencyList, int[][] weight, int vertex) {
      for (int adjacentVertex : adjacencyMatrix.get(vertex)) { // adjacencyList.get(vertex) will give all the adjacentVertices of vertex
          int[] outboundEdge = new int[] {vertex, adjacentVertex};
          relax(outboundEdge, weight[fromVertex][toVertex]);  // edge relaxation
      }
  }
              
          

The term relaxation comes from the idea of a rubber band stretched tight on a path connecting two vertices (source and destination). If we get a shorter path than the current one connecting the two vertices (source and destination), the the tension on the rubber band will be relaxed.

Now that we have covered the basics of the shortest path concept, let's discuss the Shortest Path Algorithms one by one.

Dijkstra's Algorithm:

Dijkstra's Algorithm is a Shortest Path Algorithm. If you have a graph where nodes represent places and weights of the edges represent distances, and one of the nodes is marked as source, then by using Dijkstra's Algorithm you can achieve all of the following:

1. Determine shortest distance from the source to all other nodes/places.
2. Determine shortest distance from the source to a specific node called destination.
3. Determine shortest distance from all nodes to all other nodes. This is a variation of #1. You just need to treat every node as source and run Dijkstra's Algorithm to find shortest distance to all other nodes.

What kind of problems can be solved by Dijkstra's Algorithm ?

Any problem that has the following characteristics can be solved using Dijkstra:

1. the problem can be represented with directed graph and the edges have some kind of weight (distance, price etc).
2. the problem involves minimization based on the weights of the edges. Example: Finding shortest path. Please note that Dijkstra's Algorithm is not meant for computing longest path, since longest path problem has no optimal substructure for any graph. If there is one or more positive weight cycle, you can just spin around the cycle to get longer and longer paths.
   We might think that we might use max heap and make Dijkstra's Algorithm work for computing Longest Paths, but that won't work. Let's consider the below directed weighted graph.
   

   
         D
      _
   8  /| /|\
     /    |
    S     | 7
   4 \    |
     _\|  |
   
         B
   
   

   We have directed edge from S to D (with weight 8), S to B (with weight 4) and B to D (with weight 7). Let's say S is the source. We initialize distance to S as 0 and all other to Negative INFINITY. When we process source vertex we see that D has the maximum distance since distance of B from source is 4 and that of D is 8. We pop D from max heap and mark this as processed and assign 8 as the longest distance of D from source. But this is clearly wrong. The longest path to D is S -> B -> D and the longest distance would be (4 + 7) = 11 and not 8. Sure, you can tweak Dijkstra's Algorithm to achieve maximization or compute longest path, but that definitely won't be efficient.
   To compute longest path or to solve for maximization, use:
   • Topological sort with vertex relaxation.
   • Negate all the weights of the edges and use Bellman Ford. Please note that, Bellman-Ford algorithm works for negative edge weight unlike Dijkstra.
3. None of the edge's weight is negative.
4. The graph can be either cyclic or acyclic. However, no negative cycle is allowed.

Real World Application: GPS Maps looking for the most time-saving route for driving or walking (as the case may be) from place A to place B.

How Dijkstra's Algorithm works ?

I would ask you to please keep the big picture in mind all the time. Our goal here is to find the shortest distance route from place A (source) to place B (destination).

Let's suppose we have a graph represented by an adjacency matrix where adjacencyMatrix[i][j] represents the distance between node i and node j.

Here is how Dijkstra's Algorithm works:

Dijkstra's Algorithm examines vertices in the increasing order of their distance from the source and relax their outgoing edges. We stop this process when either

• the destination vertex happens to be closest to the source among all the unprocessed vertices if we are looking for shortest path between the source and a specific destination vertex,
• or, if we are looking for shortest paths to all reachable vertices from the source, then once all the vertices have been processed.

Below is the algorithm that implements the above described procedure:

• We need the below two data structures:
  1. parent[] array to keep track of which vertex comes before another vertex in the shortest path. If say u -> v is a directed edge that is part of the shortest path, then parent[v] = u.
     parent[] array helps us to reconstruct the shortest path.
  2. distance[] array to keep track of the shortest distance of a vertex from the source.
• Initialize parent for the source as null or -1, as appropriate, in parent[] array.
• Initialize distance to source as 0 in distance[] array. distance from source vertex to source vertex is 0.
• Initialize distance for all other vertices to INFINITY. Since we do not know the shortest distance to the vertices from the source vertex. We do not even know if they are reachable or not from the source. Unreachable vertices will have the distance as INFINITY even after the algorithm is done processing.
• Now let's keep in mind how we described the Dijkstra's Algorithm succinctly before: Dijkstra's Algorithm examines vertices in the increasing order of their distance from the source and relax their outgoing edges.
  Since at first source's distance is 0 and all other INFINITY, source is the vertex that is closest to the source. So we pick the source vertex and do a vertex relaxation operation on the source vertex, i.e, relax all of it's outgoing edges.
  
  Then repeat the operation "examining vertices in the increasing order of their distance from the source and relax their outgoing edges" , which means we will now have to find the next closest vertex.
  How do we do this efficiently ? We can achieve this by using a min heap based on the shortest distance of the vertices from source. We initialize the min heap by inserting the source vertex along with its distance (which is 0). Then in each iteration remove the min from the min heap, i.e. the vertex which is at the head of the min heap because this vertex has the minimum distance from source among all the vertices present in the min heap, and then relax this vertex (i.e, relax all the outbound edges).

Let's look at the code for the Dijkstra's Algorithm implementation and that should clarify everything for you whatever we discussed so far.


Login to Access Content

Time Complexity:

If you have followed the time complexity mentioned inline in the code, you would easily see that the overall time complexity is O(ElogV). Anyways, let's discuss how we reached there:

1. We relax each edge at most once. So overall: O(ElogV)
2. We do extract min from head of the min heap O(V) times in average case, and O(V^2) in worst case (dense graph). Note that in that case E = V^2, which means it is O(E). So overall, O(VlogV) in average case and O(ElogV) in worst case.

Combining (1) and (2), overall time complexity = O(VlogV) + O(ElogV) = O((E + V)logV) <= O((E + E)logV) = O(2 * E * logV) = O(ElogV)

Why does having cycles in a graph not negatively impact Dijkstra's Algorithm?

Because, reaching a vertex via a cycle will only make the distance of the vertex from source longer than before and will automatically be ignored as a shorter distance is already available which we get by querying distance[vertex]. Since in Dijkstra's Algorithm is based on relaxation, cycle has no impact.

How can we use Dijkstra's Algorithm on an edge-weighted UNDIRECTED graph ?

By converting the graph to a directed one. Reconstruct the graph as below:

• For every edge UV in the undirected graph, create two directed edges : one in each direction, i.e, one from U to V (U -> V) and another one from V to U (V -> U). For each of these two edges, assign the same weight as that of the undirected edge UW.

Why Dijkstra's Algorithm cannot be used if the given graph has edge(s) with negative weight(s) ?

Because according to Dijkstra's Algorithm once a vertex is relaxed (i.e, extracted as min from the head of the min heap), the vertex is considered as processed. By processed we mean that we have already found the shortest path to this vertex. Dijkstra's Algorithm assumes that any edge originating from the vertex (i.e, outbound edges) will lead to a greater distance.
Dijkstra's Algorithm replies on a simple fact: if all weights are non-negative, adding an edge will never make a path shorter. That is why picking the next vertex (minHeap.poll())as the one which is at the shortest distance from the source(local optimality) always end up being correct (global optimality).
If we have negative weight edges, the above statement that "adding an edge will never make a path shorter" won't hold true.

Why don't we need to mark a vertex as visited once it is processed and we have found the shortest path to it ?

Because, after a vertex is processed and found the shortest path to it even if we find the vertex again while doing relaxation operations, the distance we would find for the vertex would always be greater than or equal to the shortest distant already computed. So it would be ignored anyways and won't be brought to the heap again.

Problem Solving using Dijkstra's Algorithm:

Now we will se how the code we have written above to implement Dijkstra's Algorithm can be used to solve problems.

Problem #1

Problem Statment: There is a ball in a maze with empty spaces and walls. The ball can go through empty spaces by rolling up, down, left or right, but it won't stop rolling until hitting a wall. When the ball stops, it could choose the next direction.
Given the ball's start position, the destination and the maze, find the shortest distance for the ball to stop at the destination. The distance is defined by the number of empty spaces traveled by the ball from the start position (excluded) to the destination (included). If the ball cannot stop at the destination, return -1.
The maze is represented by a binary 2D array. 1 means the wall and 0 means the empty space. You may assume that the borders of the maze are all walls. The start and destination coordinates are represented by row and column indexes.

Example 1:
Input 1: a maze represented by a 2D array

0 0 1 0 0
0 0 0 0 0
0 0 0 1 0
1 1 0 1 1
0 0 0 0 0

Input 2: start coordinate (rowStart, colStart) = (0, 4)
Input 3: destination coordinate (rowDest, colDest) = (4, 4)
Output: 12
Explanation: One shortest way is : left -> down -> left -> down -> right -> down -> right. The total distance is 1 + 1 + 3 + 1 + 2 + 2 + 2 = 12.

Example 2:
Input 1: a maze represented by a 2D array

0 0 1 0 0
0 0 0 0 0
0 0 0 1 0
1 1 0 1 1
0 0 0 0 0

Input 2: start coordinate (rowStart, colStart) = (0, 4)
Input 3: destination coordinate (rowDest, colDest) = (3, 2)
Output: -1
Explanation: There is no way for the ball to stop at the destination.

Solution:
This problem can be represented by a graph with no negative weight edges, so we should be able to use Dijkstra's Algorithm.

This problem is an ideal candidate to be solved by Dijkstra's Algorithm. The starting point is our source vertex and the destination is our destination vertex. Since the ball can roll only in 4 directions: up, down, left, right, we look for edges in these 4 directions. All the routes in which the ball can roll in these 4 directions will be our edges. Since the ball does not stop rolling until it hits a wall, any edge ends only when we have reached a wall. Once we construct the edge, we do edge relaxation. After vertex relaxation for the source is done we pick the vertex with the shortest distance and repeat process till we reach the destination, if it is reachable. Or else we stop once all the vertices reachable from the source is processed.
Let's look at the code now:

Login to Access Content

Time Complexity:

O(ElogV), where V = number of vertices possible = M * N, E = V * V. Matrix size = M x N. Complete traversal of maze will be done in the worst case. So its a dense graph.
So overall O((M*N)^2)log(M*N)) .

Problem #2

There are n cities connected by m flights. Each flight starts from city u and arrives at v with a price w.
Now given all the cities and flights, together with starting city src and the destination dst, your task is to find the cheapest price from src to dst with up to k stops. If there is no such route, output -1.
Example 1:
Input:
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 1
Output: 200
The cheapest price from city 0 to city 2 with at most 1 stop costs 200.

Example 2:
Input:
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 0
Output: 500
Explanation:
The cheapest price from city 0 to city 2 with at most 0 stop costs 500.

Solution:

This problem can be represented by a graph with no negative weight edges, so we should be able to use Dijkstra's Algorithm.

Please follow the comments in the code and that would clarify how this Dijkstra's Algorithm is used to solve this problem efficiently. We have used the same code template.


Login to Access Content

Time Complexity:

O(ElogV).
Here E = N * N, because in worst case every city can be connected to all other cities. N = number of cities. So overall, O((N^2)logN).

Related Must-Read Topics:

1. Longest Paths Algorithm
2. Topological Sort w/ Vertex Relaxation
3. Bellman-Ford Algorithm & Negative Cycle Detection
4. Optimized Bellman-Ford
5. Sequential Job Scheduling
6. Parallel Job Scheduling
7. Parallel Job Scheduling
   w/ Relative Deadlines
8. Arbitrage

Instructor: