Transcript shortest path

CSE 202 - Algorithms
Shortest Paths Problems
5/27/03
CSE 202 - Shortest Paths
Shortest Paths Problems
5
u
v
3
1
1
w
8
2
4
x
1
6
13
t
4
10
z
9
y
2
Given a weighted directed graph,
<u,v,t,x,z> is a path of weight 29 from u to z.
<u,v,w,x,y,z> is another path from u to z; it has
weight 16 and is the shortest path from u to z.
2
CSE 202 - Shortest Paths
Variants of Shortest Paths Problems
A. Single pair shortest path problem
•
Given s and d, find shortest path from s to d.
B. Single source shortest paths problem
•
Given s, for each d find shortest path from s to d.
C. All-pairs shortest paths problem
•
For each ordered pair s,d, find shortest path.
(A) and (B) seem to have same asymptotic complexity.
(C) takes longer, but not as long as repeating (B) for each s.
3
CSE 202 - Shortest Paths
More Shortest Paths Variants
1. All weights are non-negative.
2. Weights may be negative, but no negative cycles
(A cycle is a path from a vertex to itself.)
3. Negative cycles allowed.
Algorithm reports “- ” if there is a negative cycle on
path from source to destination
(2) and (3) seem to be harder than (1).
5
u
3
-6
4
v
w
2
u
v
w
u v
0 5
-3 0
-6 -1
w
8
3
0
5
u
v
-3
6
2
u
v
w
u
0


v
w
- -
- -
- -
w
CSE 202 - Shortest Paths
Single Source Shortest Paths
Non-negative weights (problem B-1):
From source, construct tree of shortest paths.
• Why is this a tree?
• Is this a Minimum Spanning Tree?
Basic approach: label nodes with shortest path found so far.
Relaxation step: choose any edge (u,v) . If it gives a shorter
path to v, update v ’s label.
4
4
s
1
5
5
9
9
5
2
4
4
9
s
1
relaxing
this edge
improves
this node
5
9
7
9
5
2
CSE 202 - Shortest Paths
Single Source Shortest Paths
Simplest strategy:
– Keep cycling through all edges
– When all edges are relaxed, you’re done.
What is upper bound on work?
Improvement:
Mark nodes when we’re sure we have best path.
Key insight: if you relax all edges out all marked nodes, the
unmarked node that is closest to source can be marked.
You can relax edge (u,v) only once - just after u is marked.
O(V2) algorithm: mark node; relax its edges; find new min to mark.
Dijkstra’s algorithm:
Keep nodes on min-priority queue – need E Decrease-Key’s.
Gives O(E lg V) - when is this faster?
(Aside: can also get O(E + V lg V) using Fibonacci heap.)
6
CSE 202 - Shortest Paths
Single Source Shortest Paths
Negative weights allowed (problem B-2 and B-3)
Why can’t we just add a constant to each weight?
Why doesn’t Dijkstra’s algorithm work for B-2 ?
Bellman-Ford: Cycle through edges V-1 times.
O(VE) time.
PERT chart: Arbitrary weights, graph is acyclic:
Is there a better algorithm than Bellman-Ford?
7
CSE 202 - Shortest Paths
All-pairs Shortest Paths
Naïve #1: Solve V single-source problems.
– O(V2 E) for general problem.
– O(V3) or O(V E lg V) for non-negative weights.
Naïve #2: Let dk(i,j) = shortest path from i to j
involving  k edges.
d1(i,j) = is original weight matrix.
Compute dk+1’s from dk’s by seeing if adding edge helps:
dk+1(i,j) = Min { dk(i,m) + d1(m,j) }
Hmmm ...this looks a lot like matrix multiplication
If there are no negative cycles, dV-1(i,j) is solution.
If there is a negative cycle, then dV-1  dV
8
Complexity is O(V4)
CSE 202 - Shortest Paths
All-pairs Shortest Paths
No negative cycles – Divide and Conquer says:
“Shortest path from a to b with at most 2k+1 hops
is a shortest path from a to c with at most 2k hops
followed by one from c to b with at most 2k hops.”
T(k+1) = T(k) + V3 so T(lg V) is O(V3 lg V).
This also looks like matrix multiplication, using
d2k = dk x dk instead of dk+1= dk x d1
9
CSE 202 - Shortest Paths
All-pairs Shortest Paths
No negative cycles – Dynamic Programming approach:
Number cities 1 to V.
Let S(a,b,k) be length of shortest path from a to b that
uses only cities {1,2,...,k} as intermediate points.
Intuition: At first (k=0), there are only direct flights between cities.
Then (k=1) they allow city 1 to be an intermediate connection point.
Then (k=2) they add city 2 as a possible connection point. Etc.
Claim: S(a,b,k) = min{ S(a,b,k-1), S(a,k,k-1) + S(k,b,k-1) }.
Intuition: either adding k as a possible connection point doesn’t
shorten the trip, or it does.
“No negative cycles”  needn’t consider paths going through k twice.
Complexity: T(k+1)= T(k) + cV2, and T(0) is 0.
Thus, T(V) is (V3).
This is the Floyd-Warshall algorithm
10
CSE 202 - Shortest Paths
Johnson’s All-Pairs Shortest Paths
Motivation: for sparse non-negative weights,
“O(V E lg V)”
is better than
“O(V3)”
Dijkstra V times
Floyd-Warshall
We’ll convert “arbitrary weights” (C3) to “nonnegative” (C1) problem via reweighting.
-1
-3
5
11
8
-10
3
0
0
8
Starting bonus
or finishing penalty
4
1
-9
CSE 202 - Shortest Paths
Johnson’s Algorithm
Reweighting can make all edges non-negative
5
0
-1
-3
8
5
2
3
-10
4
0
0
10
0
Make node-weight(x) = shortest path to x from anywhere.
Sounds like all-pairs problem
Slick trick
use Bellman-Ford
(only O(VE) time)
12
s
0
0
0
0
-1
-3
5
8
-10
CSE 202 - Shortest Paths
Glossary (in case symbols are weird)
      
 
 subset  element of
set

infinity  empty
 for all  there exists  intersection 
union
 big theta  big omega  summation
 >=
 <=
 about equal
 not equal  natural numbers(N)
13
CSE 202 - Shortest Paths