BFS is a single-source shortest-path algorithm

that works on unweighted graphs, that is,

graphs in which each edge has unit weight.

Shortest Path Algorithms

?? Minimize weights ??

Time, cost,
penalties, loss,
etc.
Introduction
• Given a weighted, directed graph G = (V, E), with
weight function w : E → ℝ.
• w(p), the weight of path p from v0 to vk is given by

• Then shortest-path weight 𝛿(u,v) is defined as

• Shortest path from vertex u to vertex v is then

defined as any path p with weight w(p) = 𝛿(u,v).
Contd…
• Single-source shortest-paths problem, i.e. given a
graph find a shortest path from a given source
vertex to each other vertex.
– Dijkstra’s algorithm.
• Variants:
– Single-destination shortest-paths problem
– Single-pair shortest-path problem
– All-pairs shortest-paths problem, i.e. find a shortest
path from u to v for every pair of vertices u and v.
• Floyd-Warshall algorithm.
Dijkstra’s Algorithm
• Solves single-source shortest-paths problem on a
weighted, directed graph in which all edge weights
are nonnegative.
Example
 s → t 10 → y 5

Implementation t → x 1 → y 2

x → z 4

y → t 3 → x 9 → z 2

z → s 7 → x 6
 s → t 10 → y 5
Example - Execution t → x 1 → y 2

Vertex π d x → z 4

s NIL 0 y → t 3 → x 9 → z 2
S = {}
t NIL ∞ z → s 7 → x 6
x NIL ∞
y NIL ∞
z NIL ∞

Q
 s → t 10 → y 5
Example - Execution t → x 1 → y 2

Vertex π d x → z 4

s NIL 0 y → t 3 → x 9 → z 2
S = {s}
t NIL ∞ z → s 7 → x 6
x NIL ∞
y NIL ∞
z NIL ∞

Q
 s → t 10 → y 5
Example - Execution t → x 1 → y 2

Vertex π d x → z 4

s NIL 0 y → t 3 → x 9 → z 2
S = {s}
t s 10 z → s 7 → x 6
x NIL ∞
y NIL ∞
z NIL ∞

Q
 s → t 10 → y 5
Example - Execution t → x 1 → y 2

Vertex π d x → z 4

s NIL 0 y → t 3 → x 9 → z 2
S = {s}
t s 10 z → s 7 → x 6
x NIL ∞
y s 5
z NIL ∞

Q
 s → t 10 → y 5
Example - Execution t → x 1 → y 2

Vertex π d x → z 4

s NIL 0 y → t 3 → x 9 → z 2
S = {s, y}
t s 10 z → s 7 → x 6
x NIL ∞
y s 5
z NIL ∞

Q
 s → t 10 → y 5
Example - Execution t → x 1 → y 2

Vertex π d x → z 4

s NIL 0 y → t 3 → x 9 → z 2
S = {s, y}
t y 8 z → s 7 → x 6
x NIL ∞
y s 5
z NIL ∞

Q
 s → t 10 → y 5
Example - Execution t → x 1 → y 2

Vertex π d x → z 4

s NIL 0 y → t 3 → x 9 → z 2
S = {s, y}
t y 8 z → s 7 → x 6
x y 14
y s 5
z NIL ∞

Q
 s → t 10 → y 5
Example - Execution t → x 1 → y 2

Vertex π d x → z 4

s NIL 0 y → t 3 → x 9 → z 2
S = {s, y}
t y 8 z → s 7 → x 6
x y 14
y s 5
z y 7

Q
 s → t 10 → y 5
Example - Execution t → x 1 → y 2

Vertex π d x → z 4

s NIL 0 y → t 3 → x 9 → z 2
S = {s, y, z}
t y 8 z → s 7 → x 6
x y 14
y s 5
z y 7

Q
 s → t 10 → y 5
Example - Execution t → x 1 → y 2

Vertex π d x → z 4

s NIL 0 y → t 3 → x 9 → z 2
S = {s, y, z}
t y 8 z → s 7 → x 6
x z 13
y s 5
z y 7

Q
 s → t 10 → y 5
Example - Execution t → x 1 → y 2

Vertex π d x → z 4

s NIL 0 y → t 3 → x 9 → z 2
S = {s, y, z, t}
t y 8 z → s 7 → x 6
x z 13
y s 5
z y 7

Q
 s → t 10 → y 5
Example - Execution t → x 1 → y 2

Vertex π d x → z 4

s NIL 0 y → t 3 → x 9 → z 2
S = {s, y, z, t}
t y 8 z → s 7 → x 6
x t 9
y s 5
z y 7

Q
 s → t 10 → y 5
Example - Execution t → x 1 → y 2

Vertex π d x → z 4

s NIL 0 y → t 3 → x 9 → z 2
S = {s, y, z, t, x}
t y 8 z → s 7 → x 6
x t 9
y s 5
z y 7