Shortest Path Algorithms

Deliverables

Shortest Path Algorithms

Dijkstra Algorithm
Bellman Ford Algorithm
Ford Fulkerson
11/13/2023 11:45 PM Copyright @ gdeepak.com® 2
 Definition
• Given a Graph Path P= V1  V2  V3 … Vk has weight
k −1


W(p) =
w(Vi ~ Vi + 1)
i =1
• Shortest path from u to v is a path of minimum possible weight
from u to v. Shortest path weight from u to v is
δ(u, v) = min{W(p) : P from u to v}
= ∞ if there is no path from u to v
• Negative edge weights does not affect the definition of shortest
path, however if there is a cycle containing negative edge weight
then the shortest path does not exist and δ(u, v) = - ∞

11/13/2023 11:45 PM Copyright @ gdeepak.com® 3

 Optimal substructure property
• A sub path of a shortest path is a shortest path

u x y v

Hypothetical shortest path

• U to V has a shortest path including the sub path X to Y. If there is
an alternative shortest path from x to y, then that should have been
included in calculating shortest path from u to v.

11/13/2023 11:45 PM Copyright @ gdeepak.com® 4

 Triangle Inequality
• For all vertices u, v, x є V
• δ (u, v) ≤ δ(u, x) + δ (x, v)
δ(u,v)
u v

δ(u,x) δ(x,v)

11/13/2023 11:45 PM Copyright @ gdeepak.com® 5

 Single Source Shortest Path

From a given source vertex s є V find

shortest path weight δ (s, v) for all v є V.
The best way to solve from a to b is no
easier then solving from a to everyone else.
Assuming No negative weights exist and
w(u, v) ≥ 0
11/13/2023 11:45 PM Copyright @ gdeepak.com® 6
 Greedy approach

1. Maintain set S of vertices whose shortest

path distance from s is known s є S

2. At each step add to S one vertex v є {V-S}

whose estimated distance from s is
minimum.

3. Update distance estimates of vertices

adjacent to v.

11/13/2023 11:45 PM Copyright @ gdeepak.com® 7

 Dijkstra Example
• Q A BC DE
2 D
B
10

8 9
A 4 7
1
3

C E
2

11/13/2023 11:45 PM Copyright @ gdeepak.com® 8

 Dijkstra Example
• Q A B C D E
∞
∞
2 D
• 0 ∞ ∞ ∞ ∞
B
10
s
8 9
A 4 7
1
0
3

C E
2
∞ ∞

11/13/2023 11:45 PM Copyright @ gdeepak.com® 9

 Dijkstra Example
• Q A B C D E
∞
10
2 D
• 0 ∞ ∞ ∞ ∞
B
10 • 10 3 ∞ ∞
s
8 9
A 4 7
1
0
3

C E
2
3 ∞

11/13/2023 11:45 PM Copyright @ gdeepak.com® 10

 Dijkstra Example
• Q A B C D E
11
7
2 D
• 0 ∞ ∞ ∞ ∞
B
10 • 10 3 ∞ ∞
s
A
1 4
8
7
9 • 7 11 5
0
3

C E
2
3 5

11/13/2023 11:45 PM Copyright @ gdeepak.com® 11

 Dijkstra Example
• Q A B C D E
11
7
2 D
• 0 ∞ ∞ ∞ ∞
B
10 • 10 3 ∞ ∞
s
A
1 4
8
7
9 • 7 11 5
0
3 • 7 11
C E
2
3 5

11/13/2023 11:45 PM Copyright @ gdeepak.com® 12

 Dijkstra Example
• Q A B C D E
9
7
2 D
• 0 ∞ ∞ ∞ ∞
B
10 • 10 3 ∞ ∞
s
A
1 4
8
7
9 • 7 11 5
0
3 • 7 11
E
C
2 • 9
3 5

11/13/2023 11:45 PM Copyright @ gdeepak.com® 13

 Algorithm
Dijkstra Algorithm(G,V,E){
d[s]  0
for each v є V –{s}
d[v]  ∞, S  Φ, Q  V
while Q ≠ Null
u  Extract-min(Q) implicit decrease
S  S U {u} key or relaxation
for each v є Adj(u) step
if d[v] > d[u] + w(u, v)
then d[v]  d[v] + w(u, v)
}

11/13/2023 11:45 PM Copyright @ gdeepak.com® 14

 Time Complexity
• Shortest path tree is union of all shortest path.

• Complexity = |v| extract-min + |E| decrease key

• For Array O(V2)
• For Binary heap O(V+E) lgV
• For Fibonacci Heap O(E+V lg V)

• Dijkstra is equivalent to a BFS if weights of all the edges

are taken as one.

11/13/2023 11:45 PM Copyright @ gdeepak.com® 15

 Bellman Ford Example
• A B C D E
B
2
-1
A 1 E
3 2
4 -3

C 5 D

11/13/2023 11:45 PM Copyright @ gdeepak.com® 16

 Bellman Ford Example
• A B C D E
∞
B #1 • 0 ∞ ∞ ∞ ∞
#4 2
-1
#7 E ∞
0 A 1
3 2 #3
#5 #2 #8
4 -3

C 5 D
∞
∞ #6

11/13/2023 11:45 PM Copyright @ gdeepak.com® 17

 Bellman Ford Example
We start from #1, ∞ +2 is ∞ so no change
Then edge #2, ∞ +2 is ∞ so no change
Then edge #3, ∞ +1 is ∞ so no change
Then edge #4, 0 + (-1) is -1 which is less than ∞ so change to -1
Then edge #5, 0 +4 Which is less that ∞ so change it to 4
Then edge #6, ∞ +5 is ∞ so no change
Then edge #7, -1 +3 is 2 so change 4 to 2
Then edge #8, ∞ - 3 is ∞ so no change

11/13/2023 11:45 PM Copyright @ gdeepak.com® 18

 Bellman Ford Example
• A B C D E
-1
B #1 • 0 ∞ ∞ ∞ ∞
#4 2
-1 • 0 -1 ∞ ∞ ∞
#7 E ∞
0 A 1
3 #3
• 0 -1 4 ∞ ∞
2
#5 #2 #8
4 -3

C 5 D
∞
4 #6

11/13/2023 11:45 PM Copyright @ gdeepak.com® 19

 Bellman Ford Example
• A B C D E
-1
B #1 • 0 ∞ ∞ ∞ ∞
#4 2
-1 • 0 -1 ∞ ∞ ∞
#7 E ∞
0 A 1
3 #3
• 0 -1 4 ∞ ∞
2
#5
4
#2
-3
#8
• 0 -1 2 ∞ ∞
C 5 D
∞
2 #6

11/13/2023 11:45 PM Copyright @ gdeepak.com® 20

 Bellman Ford Example
• A B C D E
-1
B #1 • 0 ∞ ∞ ∞ ∞
#4 2
-1 • 0 -1 ∞ ∞ ∞
#7 E 1
0 A 1
3 #3
• 0 -1 4 ∞ ∞
2
#5
4
#2
-3
#8
• 0 -1 2 ∞ ∞
C D • 0 -1 2 ∞ 1
5 ∞
2 #6

11/13/2023 11:45 PM Copyright @ gdeepak.com® 21

 Bellman Ford Example
• A B C D E
-1
B #1 • 0 ∞ ∞ ∞ ∞
#4 2
-1 • 0 -1 ∞ ∞ ∞
#7 E 1
0 A 1
3 #3
• 0 -1 4 ∞ ∞
2
#5
4
#2 #8
-3 • 0 -1 2 ∞ ∞
C D • 0 -1 2 ∞ 1
5 1
2 #6
• 0 -1 2 1 1
11/13/2023 11:45 PM Copyright @ gdeepak.com® 22
 Bellman Ford Example
• A B C D E
-1
B #1
• 0 ∞ ∞ ∞ ∞
#4
-1
2 • 0 -1 ∞ ∞ ∞
0 A
#7
1 E 1 • 0 -1 4 ∞ ∞
3 2 #3
#5 #2 #8 • 0 -1 2 ∞ ∞
4 -3
• 0 -1 2 ∞ 1
2
C
#6
5 D
-2 • 0 -1 2 1 1
• 0 -1 2 -2 1
11/13/2023 11:45 PM Copyright @ gdeepak.com® 23
 Few points
It is also possible to implement this algorithm in
distributed systems because the relaxation step is local and
can be independent of other parts.
Bellman ford is used a lot in internet to find the shortest
path
If bellman ford fails to converge after |v-1| rounds then
there is a negative edge cycle

11/13/2023 11:45 PM Copyright @ gdeepak.com® 24

 Bellman Ford Algorithm
• Computes δ (s, v) from source vertex s є V to all vertices v є V or reports that a negative
weight cycle exists.
Bellman_Ford(G, w, s){
D[s]  0
for each v є V-{s}
do d[v]  ∞
for i  1 to |v|-1
do for each edge (u, v) є E
do if d[v] > d[u] + w(u, v)
then d[v]  d[u] + w(u, v)
for each edge (u, v) є E
do if d[v] > d[u] + w(u, v)
then report that a negative weight cycle exists
else d[v] = δ (s, v)
}

11/13/2023 11:45 PM Copyright @ gdeepak.com® 25

 Time Complexity
Bellman-Ford: O(VE)
One pass of Bellman-Ford: O(V + E)
Bellman Ford is Slower than Dijkstra but Dijkstra does not
handle negative edge weights

11/13/2023 11:45 PM Copyright @ gdeepak.com® 26

 All Pairs Shortest Path
• Non Negative Edge Weights
• Dijkstra’s Algorithm |V| times: O(VE + V2lgV)
• Bellman Ford (once from each vertex)
• Time O(V2E) so for Dense Graph O(v4)

11/13/2023 11:45 PM Copyright @ gdeepak.com® 27

 Another Approach
Consider nXn adjacency matrix A=(aij) of the digraph and
define
(dij)(m) =Weight of a shortest path from i to j that uses at
most m edges.

dij(0) = 0 if i=j
dij(0) = ∞ if i≠j

and for m= 1,2,…,n-1

(dij)(m) = mink {(dik)(m-1) +akj}
11/13/2023 11:45 PM Copyright @ gdeepak.com® 28
 (dij)(m) = mink {(dik)(m-1) +akj}
for m← 1 to n-1
do for i ← 1 to n Relaxation
Step
do for j ← 1 to n
do for k ← 1 to n
do if dij > dik + akj
then dij ← dik + akj

Complexity O(n4)

11/13/2023 11:45 PM Copyright @ gdeepak.com® 29

 Questions, Comments and Suggestions

11/13/2023 11:45 PM Copyright @ gdeepak.com® 45

 Question 1
Adding same weight to all the graph edges keeps the
shortest path intact?
A) True
B) False

11/13/2023 11:45 PM Copyright @ gdeepak.com® 46

 Question 2
Given a graph G = (V;E) with positive edge weights, the
Bellman-Ford algorithm and Dijkstra’s algorithm can
produce different shortest-path trees despite always
producing the same shortest-path weights. Reason?
A) True
B) False

11/13/2023 11:45 PM Copyright @ gdeepak.com® 47

 Question 3
If all edges in a graph have distinct weights, then the
shortest path between two vertices is unique.
• A) True
• B) False

11/13/2023 11:45 PM Copyright @ gdeepak.com® 48