Shortest Path ARKADEEP GOSWAMI
Algorithms ASST. PROFESSOR, CSE, MCKVIE
Agenda
Dijkstra’s algorithm
Bellman-Ford algorithm
Floyd-Warshall algorithm
Presentation Title
The shortest path algorithms are the
ones that focuses on calculating the
minimum travelling cost from source
node to destination node of a graph in
optimal time and space complexities.
Definition kind of searching algorithm of
calculator graphics
Searches for the lowest cost path
between the starting point and the
object point.
9/3/20XX Presentation Title 3
There are two categories of shortest path
algorithms:
Single Source Shortest Path Algorithms:
In this algorithm we determine the shortest path
of all the nodes in the graph with respect to a
single node i.e. we have only one source node in
this algorithms.
• Depth-First Search (DFS)
• Breadth-First Search (BFS)
• Multi-Source BFS
Categories
• Dijkstra’s algorithm
• Bellman-Ford algorithm
• Topological Sort
• A* search algorithm
All Pair Shortest Path Algorithms:
Contrary to the single source shortest path
algorithm, in this algorithm we determine the
shortest path between every possible pair of
nodes.
• Floyd-Warshall algorithm
• Johnson’s algorithm
9/3/20XX Presentation Title 4
Dijkstra’s
algorithm
Purpose & use
cases
With Dijkstra's Algorithm, you can find the
shortest path between nodes in a graph.
Particularly, you can find the shortest path
from a node (called the "source node") to
all other nodes in the graph, producing a
shortest-path tree.
This algorithm is used in GPS devices to find
the shortest path between the current
location and the destination. It has broad
applications in industry, specially in domains
that require modeling networks.
“What’s the shortest way to travel from
Rotterdam to Groningen? It is the algorithm
for the shortest path, which I designed in
about 20 minutes. One morning I was
shopping in Amsterdam with my young
fiancée, and tired, we sat down on the café
terrace to drink a cup of coffee and I was
just thinking about whether I could do this,
and I then designed the algorithm for the
History
shortest path.” ----- Dijkstra
Presentation Title 7
Algorithm
9/3/20XX Presentation Title 8
Relaxation
If dist=4 dist=∞
{ s v u
= 4 2
dist=6
}
9/3/20XX Presentation Title 9
Algorithm
9/3/20XX Presentation Title 10
Pseudo code
9/3/20XX Presentation Title 11
9/3/20XX Presentation Title 12
Selected
B D E F C vertex
2,A 8,A INF,_ INF,_ INF,_ B
2,A 7,B 8,B INF,_ INF,_ D
2,A 7,B 8,B 9,D INF,_ E
A B D F C
2,A 7,B 8,B 9,D 17,E F
Shortest path total weightage=12
2,A 7,B 8,B 9,D 12,F C
9/3/20XX Presentation Title 13
Time complexity
• There are multiple ways we can implement this algorithm.
Each way utilizes different data structures to store the
graph, as well as the priority queue. Thus, the differences
between these implementations leads to different time
complexities.
9/3/20XX Presentation Title 14
Time complexity – case 1
9/3/20XX Presentation Title 15
Time complexity – case 2
9/3/20XX Presentation Title 16
Time complexity – case 3
9/3/20XX Presentation Title 17
Time complexity conclusion
• Overall, the Fibonacci heap-based implementation will
run at the fastest speed.
• Conversely, the slowest version will be the unordered list-
based priority queue version.
• However, if the graph is well-connected (i.e., having a
huge number of edges, aka, having high density), there is
not much difference between these three
implementations.
9/3/20XX Presentation Title 18
Bellman Ford
algorithm
9/3/20XX Presentation Title 19
Problem with Dijkstra algo – Negative
weight edge
8 -> -1 1 -> -1
8 1
1 4 1 4
2 -6 2 -6
2 3 2 3
2 3 5 2 3 5
Presentation Title
Algorithm
DYNAMIC
PROGRAMMING
Presentation Title
Example Relax each edge N-1 Times
Here we relax each edge 7-1=6 times
-1
B E
3
6 -2
1
A C G
5
-2
5 3
-1
D F
9/3/20XX Presentation Title 22
ITERATION B C D E F G
6,A 5,A 8,E
1 5,A 5,B 4,D
3,C 3,D 7,F
edges
AB
AC 3,C 7,F
2 3,D 5,A 2,B 4,D
1,C 5,E
AD
BE
CB 2,B 5,E
3 1,C 3,D 5,A 4,D
CE 0,B 3,E
DC
DF
4 1,C 3,D 5,A 0,B 4,D 3,E
EG
FG
9/3/20XX Presentation Title 23
• A->D->C->B->E->G
9/3/20XX Presentation Title 24
Floyd Warshall
algorithm
9/3/20XX Presentation Title 25
1 2 3 4
3 1 0 3 INF 7
1 2
A 0 2
3
8
5
0
INF
2
0
INF
1
8 4 2 INF INF 0
7 2 2
5 1
1
0
2
3
3
INF
4
7
4
1
3 A1 2
3
8
5
0
8
2
0
15
1
4 2 5 INF 0
A1[2,3] = min { A0[2,3], A0[2,1] + A0[1,3] } = min { 2, 8 + INF } = 2
A1[2,4] = min { A0[2,4], A0[2,1] + A0[1,4] } = min { INF, 8 + 7 } = 15
Presentation Title
1 2 3 4 1 2 3 4
1 0 3 INF 7
A1
1 0 3 INF 7
A0 2 8 0 2 INF 2 8 0 2 15
3
3 5 INF 0 1 3 5 8 0 1
4 2 INF INF 0 4 2 5 INF 0
1 2 1 2 3 4
1 2 3 4
8 1 0 3 5 7
1 0 3 5 6
A2 2 8 0 2 15
A3
2 7 0 2 3
2
3 5 8 0 1
7 2
3 5 8 0 1
4 2 5 7 0
4 2 5 7 0
5
1 2 3 4
4 3 1 0 3 5 6
1 A4 2
3
5
3
0
6
2
0
3
4 2 5 7 0
A2[1,3] = min { A1[1,3], A1[1,2] + A1[2,3] } = min { INF, 3 + 2 } = 5
A2[4,3] = min { A1[4,3], A1[4,2] + A1[2,3] } = min { INF, 5 + 2 } = 7
A3[1,4] = min { A2[1,4], A2[1,3] + A2[3,4] } = min { 7, 5 + 1 } =6
Presentation Title
FORMULA
• Ak[i,j] = min {Ak-1[i,j], Ak-1[i,k] + Ak-1[k,j]}
In code:
if (distance[i][j] > distance[i][k] + distance[k][j])
{
distance[i][j] <- distance[i][k] + distance[k][j];
}
9/3/20XX Presentation Title 28
9/3/20XX Presentation Title 29
