5
1. Shortest paths and trees
1.1. Shortest paths with nonnegative lengths
Let D = (V, A) be a directed graph, and let s, t ∈ V . A walk is a sequence P =
(v
0
, a
1
, v
1
, . . . , a
m
, v
m
) where a
i
is an arc from v
i−1
to v
i
for i = 1, . . . , m. If v
0
, . . . , v
m
all are different, P is called a path.
If s = v
0
and t = v
m
, the vertices s and t are the starting and end vertex of P ,
respectively, and P is called an s − t walk, and, if P is a path, an s − t path. The
length of P is m. The distance from s to t is the minimum length of any s − t path.
(If no s − t path exists, we set the distance from s to t equal to ∞.)
It is not difficult to determine the distance from s to t: Let V
i
denote the set of
vertices of D at distance i from s. Note that for each i:
(1) V
i+1
is equal to the set of vertices v ∈ V \ (V
0
∪ V
1
∪ ··· ∪ V
i
) for which
(u, v) ∈ A for some u ∈ V
i
.
This gives us directly an algorithm for determining the sets V
i
: we set V
0
:= {s} and
next we determine with rule (1) the sets V
1
, V
2
, . . . successively, until V
i+1
= ∅.
In fact, it gives a linear-time algorithm:
Theorem 1.1. The algorithm has running time O(|A|).
Proof. Directly from the description.
In fact the algorithm finds the distance from s to all vertices reachable from s.
Moreover, it gives the shortest paths. These can be described by a rooted (directed)
tree T = (V
′
, A
′
), with root s, such that V
′
is the set of vertices reachable in D from
s and such that for each u, v ∈ V
′
, each directed u − v path in T is a shortest u − v
path in D.
1
Indeed, when we reach a vertex t in the algorithm, we store the arc by which t is
reached. Then at the end of the algorithm, all stored arcs form a rooted tree with
this property.
There is also a trivial min-max relation characterizing the minimum length of an
s − t path. To this end, call a subset A
′
of A an s − t cut if A
′
= δ
out
(U) for some
subset U of V satisfying s ∈ U and t 6∈ U.
2
Then the following was observed by
Robacker [1956]:
1
A rooted tree, with root s, is a directed graph such that the underlying undirected graph is a
tree and such that each vertex t 6= s has indegree 1. Thus each vertex t is reachable from s by a
unique directed s − t path.
2
δ
out
(U) and δ
in
(U) denote the sets of arcs leaving and entering U, respectively.
评论0