Introduction to Algorithms, Third Edition

shortest-paths problem
, we are given a weighted, directed graph
G
D
.V; E/
, with weight function
w
W
E
!
R
mapping edges to real-valued
weights. The
weight
w.p/
of path
p
D h
0
; 
1
; : : : ; 
k
i
is the sum of the weights
of its constituent edges:
w.p/
D
k
X
i
D
1
w.
i
1
; 
i
/ :
We define the
shortest-path weight
ı.u; /
from
u
to
by
ı.u; /
D
(
min
f
w.p/
W
u
p
;
g
if there is a path from
u
to
;
1
otherwise
:
A
shortest path
from vertex
u
to vertex
is then defined as any path
p
with weight
w.p/
D
ı.u; /
.
In the Phoenix-to-Indianapolis example, we can model the road map as a graph:
vertices represent intersections, edges represent road segments between intersec-
tions, and edge weights represent road distances. Our goal is to find a shortest path
from a given intersection in Phoenix to a given intersection in Indianapolis.

---

644
Chapter 24
Single-Source Shortest Paths
Edge weights can represent metrics other than distances, such as time, cost,
penalties, loss, or any other quantity that accumulates linearly along a path and
that we would want to minimize.
The breadth-first-search algorithm from Section 22.2 is a shortest-paths algo-
rithm that works on unweighted graphs, that is, graphs in which each edge has unit
weight. Because many of the concepts from breadth-first search arise in the study
of shortest paths in weighted graphs, you might want to review Section 22.2 before
proceeding.