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