|
Preserving shortest paths by reweighting
The following lemma shows how easily we can reweight the edges to satisfy the
first property above. We use
ı
to denote shortest-path weights derived from weight
function
w
and
y
ı
to denote shortest-path weights derived from weight function
y
w
.
Lemma 25.1 (Reweighting does not change shortest paths)
Given a weighted, directed graph
G
D
.V; E/
with weight function
w
W
E
!
R
,
let
h
W
V
!
R
be any function mapping vertices to real numbers. For each edge
.u; /
2
E
, define
y
w.u; /
D
w.u; /
C
h.u/
h./ :
(25.9)
Let
p
D h
0
;
1
; : : : ;
k
i
be any path from vertex
0
to vertex
k
. Then
p
is a
shortest path from
0
to
k
with weight function
w
if and only if it is a shortest path
with weight function
y
w
. That is,
w.p/
D
ı.
0
;
k
/
if and only if
y
w.p/
D y
ı.
0
;
k
/
.
Furthermore,
G
has a negative-weight cycle using weight function
w
if and only
if
G
has a negative-weight cycle using weight function
y
w
.
Proof
We start by showing that
y
w.p/
D
w.p/
C
h.
0
/
h.
k
/ :
(25.10)
We have
y
w.p/
D
k
X
i
D
1
y
w.
i
1
;
i
/
D
k
X
i
D
1
.w.
i
1
;
i
/
C
h.
i
1
/
h.
i
//
D
k
X
i
D
1
w.
i
1
;
i
/
C
h.
0
/
h.
k
/
(because the sum telescopes)
D
w.p/
C
h.
0
/
h.
k
/ :
702
Chapter 25
All-Pairs Shortest Paths
Therefore, any path
p
from
0
to
k
has
y
w.p/
D
w.p/
C
h.
0
/
h.
k
/
. Be-
cause
h.
0
/
and
h.
k
/
do not depend on the path, if one path from
0
to
k
is
shorter than another using weight function
w
, then it is also shorter using
y
w
. Thus,
w.p/
D
ı.
0
;
k
/
if and only if
y
w.p/
D y
ı.
0
;
k
/
.
Finally, we show that
G
has a negative-weight cycle using weight function
w
if
and only if
G
has a negative-weight cycle using weight function
y
w
. Consider any
cycle
c
D h
0
;
1
; : : : ;
k
i
, where
0
D
k
. By equation (25.10),
y
w.c/
D
w.c/
C
h.
0
/
h.
k
/
D
w.c/ ;
and thus
c
has negative weight using
w
if and only if it has negative weight us-
ing
y
w
.
Producing nonnegative weights by reweighting
Our next goal is to ensure that the second property holds: we want
y
w.u; /
to be
nonnegative for all edges
.u; /
2
E
. Given a weighted, directed graph
G
D
.V; E/
with weight function
w
W
E
!
R
, we make a new graph
G
0
D
.V
0
; E
0
/
,
where
V
0
D
V
[ f
s
g
for some new vertex
s
62
V
and
E
0
D
E
[ f
.s; /
W
2
V
g
.
We extend the weight function
w
so that
w.s; /
D
0
for all
2
V
. Note that
because
s
has no edges that enter it, no shortest paths in
G
0
, other than those with
source
s
, contain
s
. Moreover,
G
0
has no negative-weight cycles if and only if
G
has no negative-weight cycles. Figure 25.6(a) shows the graph
G
0
corresponding
to the graph
G
of Figure 25.1.
Now suppose that
G
and
G
0
have no negative-weight cycles. Let us define
h./
D
ı.s; /
for all
2
V
0
.
By the triangle inequality (Lemma 24.10),
we have
h./
h.u/
C
w.u; /
for all edges
.u; /
2
E
0
. Thus, if we de-
fine the new weights
y
w
by reweighting according to equation (25.9), we have
y
w.u; /
D
w.u; /
C
h.u/
h./
0
, and we have satisfied the second property.
Figure 25.6(b) shows the graph
G
0
from Figure 25.6(a) with reweighted edges.
Computing all-pairs shortest paths
Johnson’s algorithm to compute all-pairs shortest paths uses the Bellman-Ford al-
gorithm (Section 24.1) and Dijkstra’s algorithm (Section 24.3) as subroutines. It
assumes implicitly that the edges are stored in adjacency lists. The algorithm re-
turns the usual
j
V
j j
V
j
matrix
D
D
d
ij
, where
d
ij
D
ı.i; j /
, or it reports that
the input graph contains a negative-weight cycle. As is typical for an all-pairs
shortest-paths algorithm, we assume that the vertices are numbered from
1
to
j
V
j
.
25.3
Johnson’s algorithm for sparse graphs
703
2
1
5
4
3
4
8
2
6
7
1
0
0
0
0
0
0
0
2/1
2/–3
2/2
0/–4
2/3
0/–4
0/1
2/–1
2/7
0/4
0/5
2/3
2/2
0/–1
0/–5
2/–2
4/8
2/5
2/1
2/6
(a)
(c)
(b)
–4
–4
–1
–5
–5
3
2
1
5
4
4
0
13
2
2
10
0
5
1
0
4
0
0
0
0
–4
–1
–5
0
3
2
1
5
4
4
0
13
2
2
10
0
0
0
3
(d)
2
1
5
4
4
0
13
2
2
10
0
0
0
3
(e)
2
1
5
4
4
0
13
2
2
10
0
0
0
3
(f)
2
1
5
4
4
0
13
2
2
10
0
0
0
3
(g)
2
1
5
4
4
0
13
2
2
10
0
0
0
3
0/0
0/0
0/0
0/0
0/0
0
0
Figure 25.6
Johnson’s all-pairs shortest-paths algorithm run on the graph of Figure 25.1. Ver-
tex numbers appear outside the vertices.
(a)
The graph
G
0
with the original weight function
w
.
The new vertex
s
is black. Within each vertex
is
h./
D
ı.s; /
.
(b)
After reweighting each
edge
.u; /
with weight function
y
w.u; /
D
w.u; /
C
h.u/
h./
.
(c)–(g)
The result of running
is black, and shaded edges are in the shortest-paths tree computed by the algorithm. Within each
vertex
are the values
y
ı.u; /
and
ı.u; /
, separated by a slash. The value
d
u
D
ı.u; /
is equal to
y
ı.
/
C
h./
h.u/
Dijkstra’s algorithm on each vertex of
G
using weight function
w
y
. In each part, the source vertex
u
.
u;
704
Chapter 25
All-Pairs Shortest Paths
J
OHNSON
.G; w/
1
compute
G
0
, where
G
0
:
V
D
G:
V
[ f
s
g
,
G
0
:
E
D
G:
E
[ f
.s; /
W
2
G:
V
g
, and
w.s; /
D
0
for all
2
G:
V
2
if
B
ELLMAN
-F
ORD
.G
0
; w; s/
==
FALSE
3
print “the input graph contains a negative-weight cycle”
4
else for
each vertex
2
G
0
:
V
5
set
h./
to the value of
ı.s; /
computed by the Bellman-Ford algorithm
6
for
each edge
.u; /
2
G
0
:
E
7
y
w.u; /
D
w.u; /
C
h.u/
h./
8
let
D
D
.d
u
/
be a new
n
n
matrix
9
for
each vertex
u
2
G:
V
10
run D
IJKSTRA
.G;
y
w; u/
to compute
y
ı.u; /
for all
2
G:
V
11
for
each vertex
2
G:
V
12
d
u
D y
ı.u; /
C
h./
h.u/
13
return
D
This code simply performs the actions we specified earlier. Line 1 produces
G
0
.
Line 2 runs the Bellman-Ford algorithm on
G
0
with weight function
w
and source
vertex
s
. If
G
0
, and hence
G
, contains a negative-weight cycle, line 3 reports the
problem. Lines 4–12 assume that
G
0
contains no negative-weight cycles. Lines 4–5
set
h./
to the shortest-path weight
ı.s; /
computed by the Bellman-Ford algo-
rithm for all
2
V
0
. Lines 6–7 compute the new weights
y
w
. For each pair of ver-
tices
u;
2
V
, the
for
loop of lines 9–12 computes the shortest-path weight
y
ı.u; /
by calling Dijkstra’s algorithm once from each vertex in
V
. Line 12 stores in
matrix entry
d
u
the correct shortest-path weight
ı.u; /
, calculated using equa-
tion (25.10). Finally, line 13 returns the completed
D
matrix. Figure 25.6 depicts
the execution of Johnson’s algorithm.
If we implement the min-priority queue in Dijkstra’s algorithm by a Fibonacci
heap, Johnson’s algorithm runs in
O.V
2
lg
V
C
VE/
time. The simpler binary min-
heap implementation yields a running time of
O.VE
lg
V /
, which is still asymp-
totically faster than the Floyd-Warshall algorithm if the graph is sparse.
Exercises
25.3-1
Use Johnson’s algorithm to find the shortest paths between all pairs of vertices in
the graph of Figure 25.2. Show the values of
h
and
y
w
computed by the algorithm.
Problems for Chapter 25
705
25.3-2
What is the purpose of adding the new vertex
s
to
V
, yielding
V
0
?
25.3-3
Suppose that
w.u; /
0
for all edges
.u; /
2
E
. What is the relationship
between the weight functions
w
and
y
w
?
25.3-4
Professor Greenstreet claims that there is a simpler way to reweight edges than
the method used in Johnson’s algorithm. Letting
w
D
min
.u;/
2
E
f
w.u; /
g
, just
define
y
w.u; /
D
w.u; /
w
for all edges
.u; /
2
E
. What is wrong with the
professor’s method of reweighting?
25.3-5
Suppose that we run Johnson’s algorithm on a directed graph
G
with weight func-
tion
w
. Show that if
G
contains a
0
-weight cycle
c
, then
y
w.u; /
D
0
for every
edge
.u; /
in
c
.
25.3-6
Professor Michener claims that there is no need to create a new source vertex in
line 1 of J
OHNSON
. He claims that instead we can just use
G
0
D
G
and let
s
be any
vertex. Give an example of a weighted, directed graph
G
for which incorporating
the professor’s idea into J
OHNSON
causes incorrect answers. Then show that if
G
is strongly connected (every vertex is reachable from every other vertex), the results
returned by J
OHNSON
with the professor’s modification are correct.
Do'stlaringiz bilan baham: |
