Shortest Path

 The shortest path problem is the problem of finding a path

between two vertices (aka nodes) in a graph such that the
sum of the weights of the edges in the path is minimized.

 We distinguish several variations of the shortest path

problem:

o Single-pair shortest path problem, in which we have to

find the shortest path between a pair of vertices.

o Single-source shortest path problem, in which we have

to find the shortest pair between a pair of vertices.

o Single-destination shortest path problem, in which we

have to find the shortest pair between a pair of vertices.

o All-pairs shortest path problem, in which we have to

find shortest paths between all pairs of vertices in the
graph.

 Here are the most important algorithms for solving the

shortest path problem:

o Breadth-first search finds the shortest paths

for unweighted graphs.

o Dijkstra’s algorithm solves the single-source shortest

path problem for a graph with non-negative edge
weights.

o Bellman–Ford algorithm solves the single-

source shortest path problem for a graph where edge
weights may be negative.

o A* algorithm solves the single-pair shortest path

problem using heuristics to speed up the search.

o Floyd–Warshall algorithm solves all-pairs shortest

path problem for a graph where edge weights may be
negative.

An Introduction to Dijkstra's Algorithm

Now that we know some basic Graphs concepts let's dive into understanding the
concept of Dijkstra's Algorithm.
Ever wondered how does Google Maps finds the shortest and fastest route between
two places?

Well, the answer is Dijkstra's Algorithm. Dijkstra's Algorithm is a Graph

algorithm that finds the shortest path from a source vertex to all other vertices in
the Graph (single source shortest path). It is a type of Greedy Algorithm that only
works on Weighted Graphs having positive weights. The time complexity of Dijkstra's
Algorithm is O(V2) with the help of the adjacency matrix representation of the graph.
This time complexity can be reduced to O((V + E) log V) with the help of an
adjacency list representation of the graph, where V is the number of vertices and E is
the number of edges in the graph.

Fundamentals of Dijkstra's Algorithm

The following are the basic concepts of Dijkstra's Algorithm:

1. Dijkstra's Algorithm begins at the node we select (the source node), and it examines
the graph to find the shortest path between that node and all the other nodes in the
graph.
2. The Algorithm keeps records of the presently acknowledged shortest distance from
each node to the source node, and it updates these values if it finds any shorter path.
3. Once the Algorithm has retrieved the shortest path between the source and another
node, that node is marked as 'visited' and included in the path.
4. The procedure continues until all the nodes in the graph have been included in the
path. In this manner, we have a path connecting the source node to all other nodes,
following the shortest possible path to reach each node.

Understanding the Working of Dijkstra's

Algorithm
A graph and source vertex are requirements for Dijkstra's Algorithm. This Algorithm
is established on Greedy Approach and thus finds the locally optimal choice (local
minima in this case) at each step of the Algorithm.

Each Vertex in this Algorithm will have two properties defined for it:

1. Visited Property
2. Path Property

Let us understand these properties in brief.

Visited Property:
1. The 'visited' property signifies whether or not the node has been visited.
2. We are using this property so that we do not revisit any node.
3. A node is marked visited only when the shortest path has been found.

Path Property:
1. The 'path' property stores the value of the current minimum path to the node.
2. The current minimum path implies the shortest way we have reached this node till
now.
3. This property is revised when any neighbor of the node is visited.
4. This property is significant because it will store the final answer for each node.

Initially, we mark all the vertices, or nodes, unvisited as they have yet to be visited.
The path to all the nodes is also set to infinity apart from the source node. Moreover,
the path to the source node is set to zero (0).

We then select the source node and mark it as visited. After that, we access all the
neighboring nodes of the source node and perform relaxation on every node.
Relaxation is the process of lowering the cost of reaching a node with the help of
another node.

In the process of relaxation, the path of each node is revised to the minimum value
amongst the node's current path, the sum of the path to the previous node, and the
path from the previous node to the current node.

Let us suppose that p[n] is the value of the current path for node n, p[m] is the value
of the path up to the previously visited node m, and w is the weight of the edge
between the current node and previously visited one (edge weight between n and
m).

In the mathematical sense, relaxation can be exemplified as:

p[n] = minimum(p[n], p[m] + w)

We then mark an unvisited node with the least path as visited in every subsequent
step and update its neighbor's paths.

We repeat this procedure until all the nodes in the graph are marked visited.

Whenever we add a node to the visited set, the path to all its neighboring nodes also
changes accordingly.
If any node is left unreachable (disconnected component), its path remains 'infinity'.
In case the source itself is a separate component, then the path to all other nodes
remains 'infinity'.

Understanding Dijkstra's Algorithm with an

Example
The following is the step that we will follow to implement Dijkstra's Algorithm:

Step 1: First, we will mark the source node with a current distance of 0 and set the
rest of the nodes to INFINITY.

Step 2: We will then set the unvisited node with the smallest current distance as the
current node, suppose X.

Step 3: For each neighbor N of the current node X: We will then add the current
distance of X with the weight of the edge joining X-N. If it is smaller than the current
distance of N, set it as the new current distance of N.

Step 4: We will then mark the current node X as visited.

Step 5: We will repeat the process from 'Step 2' if there is any node unvisited left in
the graph.

How does Dijkstra’s Algorithm works?

Let’s see how Dijkstra’s Algorithm works with an example given below:
Dijkstra’s Algorithm will generate the shortest path from Node 0 to all other Nodes
in the graph.
Consider the below graph:
 Dijkstra’s Algorithm

The algorithm will generate the shortest path from node 0 to all the other nodes in
the graph.
For this graph, we will assume that the weight of the edges represents the distance
between two nodes.
As, we can see we have the shortest path from,
Node 0 to Node 1, from
Node 0 to Node 2, from
Node 0 to Node 3, from
Node 0 to Node 4, from
Node 0 to Node 6.
Initially we have a set of resources given below :
 The Distance from the source node to itself is 0. In this example the source
node is 0.
 The distance from the source node to all other node is unknown so we
mark all of them as infinity.
Example: 0 -> 0, 1-> ∞,2-> ∞,3-> ∞,4-> ∞,5-> ∞,6-> ∞.
 we’ll also have an array of unvisited elements that will keep track of
unvisited or unmarked Nodes.
 Algorithm will complete when all the nodes marked as visited and the
distance between them added to the path. Unvisited Nodes:- 0 1 2 3 4 5 6.
Step 1: Start from Node 0 and mark Node as visited as you can check in below image
visited Node is marked red.
 Dijkstra’s Algorithm

Step 2: Check for adjacent Nodes, Now we have to choices (Either choose Node1
with distance 2 or either choose Node 2 with distance 6 ) and choose Node with
minimum distance. In this step Node 1 is Minimum distance adjacent Node, so
marked it as visited and add up the distance.
Distance: Node 0 -> Node 1 = 2

Dijkstra’s Algorithm

Step 3: Then Move Forward and check for adjacent Node which is Node 3, so
marked it as visited and add up the distance, Now the distance will be:
Distance: Node 0 -> Node 1 -> Node 3 = 2 + 5 = 7
 Dijkstra’s Algorithm

Step 4: Again we have two choices for adjacent Nodes (Either we can choose Node 4
with distance 10 or either we can choose Node 5 with distance 15) so choose Node
with minimum distance. In this step Node 4 is Minimum distance adjacent Node, so
marked it as visited and add up the distance.
Distance: Node 0 -> Node 1 -> Node 3 -> Node 4 = 2 + 5 + 10 = 17

Dijkstra’s Algorithm

Step 5: Again, Move Forward and check for adjacent Node which is Node 6, so
marked it as visited and add up the distance, Now the distance will be:
Distance: Node 0 -> Node 1 -> Node 3 -> Node 4 -> Node 6 = 2 + 5 + 10 + 2 = 19
 Dijkstra’s Algorithm

So, the Shortest Distance from the Source Vertex is 19 which is optimal one
Floyd Warshall Algorithm:
The Floyd Warshall Algorithm is an all pair shortest path algorithm
unlike Dijkstra and Bellman Ford which are single source shortest path algorithms.
This algorithm works for both the directed and undirected weighted graphs. But, it
does not work for the graphs with negative cycles (where the sum of the edges in a
cycle is negative). It follows Dynamic Programming approach to check every possible
path going via every possible node in order to calculate shortest distance between
every pair of nodes.
Idea Behind Floyd Warshall Algortihm:
Suppose we have a graph G[][] with V vertices from 1 to N. Now we have to
evaluate a shortestPathMatrix[][] where shortestPathMatrix[i][j] represents the
shortest path between vertices i and j.
Obviously the shortest path between i to j will have some k number of intermediate
nodes. The idea behind floyd warshall algorithm is to treat each and every vertex
from 1 to N as an intermediate node one by one.
The following figure shows the above optimal substructure property in floyd
warshall algorithm:

Algorithm:
 Initialize the solution matrix same as the input graph matrix as a first step.
 Then update the solution matrix by considering all vertices as an
intermediate vertex.
  The idea is to pick all vertices one by one and updates all shortest paths
which include the picked vertex as an intermediate vertex in the shortest
path.
 When we pick vertex number k as an intermediate vertex, we already have
considered vertices {0, 1, 2, .. k-1} as intermediate vertices.
 For every pair (i, j) of the source and destination vertices respectively,
there are two possible cases.
 k is not an intermediate vertex in shortest path from i to j. We
keep the value of dist[i][j] as it is.
 k is an intermediate vertex in shortest path from i to j. We
update the value of dist[i][j] as dist[i][k] + dist[k][j], if dist[i]
[j] > dist[i][k] + dist[k][j]
Pseudo-Code:
For k = 0 to n – 1
For i = 0 to n – 1
For j = 0 to n – 1
Distance[i, j] = min(Distance[i, j], Distance[i, k] + Distance[k, j])
where i = source Node, j = Destination Node, k = Intermediate Node
Illustration:
Suppose we have a graph as shown in the image:
Step 1: Initialize the Distance[][] matrix using the input graph such that
Distance[i][j]= weight of edge from i to j, also Distance[i][j] = Infinity if there is
no edge from i to j.
Step 2: Treat node A as an intermediate node and calculate the Distance[][] for
every {i,j} node pair using the formula:
= Distance[i][j] = minimum (Distance[i][j], (Distance from i to A) + (Distance
from A to j ))
= Distance[i][j] = minimum (Distance[i][j], Distance[i][A] + Distance[A][j])

Step 3: Treat node B as an intermediate node and calculate the Distance[][] for
every {i,j} node pair using the formula:
= Distance[i][j] = minimum (Distance[i][j], (Distance from i to B) + (Distance
from B to j ))
= Distance[i][j] = minimum (Distance[i][j], Distance[i][B] + Distance[B][j])
Step 4: Treat node C as an intermediate node and calculate the Distance[][] for
every {i,j} node pair using the formula:
= Distance[i][j] = minimum (Distance[i][j], (Distance from i to C) + (Distance
from C to j ))
= Distance[i][j] = minimum (Distance[i][j], Distance[i][C] + Distance[C][j])

Step 5: Treat node D as an intermediate node and calculate the Distance[][] for
every {i,j} node pair using the formula:
= Distance[i][j] = minimum (Distance[i][j], (Distance from i to D) + (Distance
from D to j ))
= Distance[i][j] = minimum (Distance[i][j], Distance[i][D] + Distance[D][j])
Step 6: Treat node E as an intermediate node and calculate the Distance[][] for
every {i,j} node pair using the formula:
= Distance[i][j] = minimum (Distance[i][j], (Distance from i to E) + (Distance
from E to j ))
= Distance[i][j] = minimum (Distance[i][j], Distance[i][E] + Distance[E][j])

Step 7: Since all the nodes have been treated as an intermediate node, we can now
return the updated Distance[][] matrix as our answer matrix.
Bellman-Ford Algorithm
Bellman-Ford is a single source shortest path algorithm that determines the shortest
path between a given source vertex and every other vertex in a graph. This algorithm
can be used on both weighted and unweighted graphs.
A Bellman-Ford algorithm is also guaranteed to find the shortest path in a graph,
similar to Dijkstra’s algorithm . Although Bellman-Ford is slower than Dijkstra’s
algorithm, it is capable of handling graphs with negative edge weights, which
makes it more versatile. The shortest path cannot be found if there exists a negative
cycle in the graph. If we continue to go around the negative cycle an infinite number
of times, then the cost of the path will continue to decrease (even though the length
of the path is increasing). As a result, Bellman-Ford is also capable of detecting
negative cycles, which is an important feature.
The idea behind Bellman Ford Algorithm:
The Bellman-Ford algorithm’s primary principle is that it starts with a single source
and calculates the distance to each node. The distance is initially unknown and
assumed to be infinite, but as time goes on, the algorithm relaxes those paths by
identifying a few shorter paths. Hence it is said that Bellman-Ford is based on
“Principle of Relaxation“.
Principle of Relaxation of Edges for Bellman-Ford:
 It states that for the graph having N vertices, all the edges should be
relaxed N-1 times to compute the single source shortest path.
 In order to detect whether a negative cycle exists or not, relax all the edge
one more time and if the shortest distance for any node reduces then we
can say that a negative cycle exists. In short if we relax the edges N times,
and there is any change in the shortest distance of any node between
the N-1th and Nth relaxation than a negative cycle exists, otherwise not
exist.
Why Relaxing Edges N-1 times, gives us Single Source Shortest Path?
In the worst-case scenario, a shortest path between two vertices can have at most N-
1 edges, where N is the number of vertices. This is because a simple path in a graph
with N vertices can have at most N-1 edges, as it’s impossible to form a closed loop
without revisiting a vertex.
By relaxing edges N-1 times, the Bellman-Ford algorithm ensures that the distance
estimates for all vertices have been updated to their optimal values, assuming the
graph doesn’t contain any negative-weight cycles reachable from the source vertex.
If a graph contains a negative-weight cycle reachable from the source vertex, the
algorithm can detect it after N-1 iterations, since the negative cycle disrupts the
shortest path lengths.
In summary, relaxing edges N-1 times in the Bellman-Ford algorithm guarantees that
the algorithm has explored all possible paths of length up to N-1, which is the
maximum possible length of a shortest path in a graph with N vertices. This allows
the algorithm to correctly calculate the shortest paths from the source vertex to all
other vertices, given that there are no negative-weight cycles.
Why Does the Reduction of Distance in the N’th Relaxation Indicates the
Existence of a Negative Cycle?
As previously discussed, achieving the single source shortest paths to all other nodes
takes N-1 relaxations. If the N’th relaxation further reduces the shortest distance for
any node, it implies that a certain edge with negative weight has been traversed once
more. It is important to note that during the N-1 relaxations, we presumed that each
vertex is traversed only once. However, the reduction of distance during the N’th
relaxation indicates revisiting a vertex.
Working of Bellman-Ford Algorithm to Detect the Negative cycle in the graph:
Let’s suppose we have a graph which is given below and we want to find whether
there exists a negative cycle or not using Bellman-Ford.

Initial Graph
Step 1: Initialize a distance array Dist[] to store the shortest distance for each
vertex from the source vertex. Initially distance of source will be 0 and Distance of
other vertices will be INFINITY.

Initialize a distance array

Step 2: Start relaxing the edges, during 1st Relaxation:

 Current Distance of B > (Distance of A) + (Weight of A to B) i.e. Infinity
>0+5
 Therefore, Dist[B] = 5

1st Relaxation

Step 3: During 2nd Relaxation:

 Current Distance of D > (Distance of B) + (Weight of B to D) i.e. Infinity
>5+2
  Dist[D] = 7
 Current Distance of C > (Distance of B) + (Weight of B to C) i.e. Infinity
>5+1
 Dist[C] = 6

2nd Relaxation

Step 4: During 3rd Relaxation:

 Current Distance of F > (Distance of D ) + (Weight of D to F) i.e. Infinity
>7+2
 Dist[F] = 9
 Current Distance of E > (Distance of C ) + (Weight of C to E) i.e. Infinity
>6+1
 Dist[E] = 7

3rd Relaxation
Step 5: During 4th Relaxation:
 Current Distance of D > (Distance of E) + (Weight of E to D) i.e. 7 > 7 +
(-1)
 Dist[D] = 6
 Current Distance of E > (Distance of F ) + (Weight of F to E) i.e. 7 > 9 +
(-3)
 Dist[E] = 6

4th Relaxation

Step 6: During 5th Relaxation:

 Current Distance of F > (Distance of D) + (Weight of D to F) i.e. 9 > 6 +
2
 Dist[F] = 8
 Current Distance of D > (Distance of E ) + (Weight of E to D) i.e. 6 > 6 +
(-1)
 Dist[E] = 5
 Since the graph h 6 vertices, So during the 5th relaxation the shortest
distance for all the vertices should have been calculated.
 5th Relaxation

Step 7: Now the final relaxation i.e. the 6th relaxation should indicate the presence
of negative cycle if there is any changes in the distance array of 5th relaxation.
During the 6th relaxation, following changes can be seen:
 Current Distance of E > (Distance of F) + (Weight of F to E) i.e. 6 > 8 +
(-3)
 Dist[E]=5
 Current Distance of F > (Distance of D ) + (Weight of D to F) i.e. 8 > 5 +
2
 Dist[F]=7
Since, we observer changes in the Distance array Hence ,we can conclude the
presence of a negative cycle in the graph.

6th Relaxation
Result: A negative cycle (D->F->E) exists in the graph.
Algorithm to Find Negative Cycle in a Directed Weighted Graph Using
Bellman-Ford:
 Initialize distance array dist[] for each vertex ‘v‘ as dist[v] = INFINITY.
 Assume any vertex (let’s say ‘0’) as source and assign dist = 0.
 Relax all the edges(u,v,weight) N-1 times as per the below condition:
 dist[v] = minimum(dist[v], distance[u] + weight)
 Now, Relax all the edges one more time i.e. the Nth time and based on the
below two cases we can detect the negative cycle:
 Case 1 (Negative cycle exists): For any edge(u, v, weight), if
dist[u] + weight < dist[v]
 Case 2 (No Negative cycle) : case 1 fails for all the edges.
Handling Disconnected Graphs in the Algorithm:
The above algorithm and program might not work if the given graph is
disconnected. It works when all vertices are reachable from source vertex 0.
To handle disconnected graphs, we can repeat the above algorithm for vertices
having distance = INFINITY, or simply for the vertices that are not visited.