Transcript Shortest Path

Shortest Paths
Text
Discrete Mathematics and Its
Applications (5 Edition)
th
Kenneth H. Rosen
Chapter 10.6
Based on slides from Chuck Allison,
Michael T. Goodrich, and Roberto Tamassia
By Longin Jan Latecki
Weighted Graphs
Graphs that have a number assigned to
each edge are called weighted graphs.
BOS
NY
CHI
SF
DEN
ATL
LA
MIA
Weighted Graphs
MILES
BOS
2534
1855
SF
957
DEN
CHI
722
NY
908
349
LA
ATL
595
MIA
Weighted Graphs
FARES
BOS
$129
$99
SF
$89
CHI
$39
NY
$59
DEN
$39
ATL
LA
MIA
Weighted Graphs
FLIGHT
TIMES
BOS
4:05
2:55
SF
2:20
DEN
CHI
0:50
NY
1:50
2:10
1:15
ATL
LA
MIA
Weighted Graphs




A weighted graph is a graph in which each
edge (u, v) has a weight w(u, v). Each weight
is a real number.
Weights can represent distance, cost, time,
capacity, etc.
The length of a path in a weighted graph is the
sum of the weights on the edges.
Dijkstra’s Algorithm finds the shortest path
between two vertices.
Dijkstra Animation




Youtube video:
http://www.youtube.com/watch?v=gdmfOwyQlcI
Java animation:
http://weierstrass.is.tokushimau.ac.jp/ikeda/suuri/dijkstra/Dijkstra.shtml
b
4
Find a
shortest
a
path
3
from a to z
f
d 5
5
7
3
4
1
2
z
4
c
5
e 5
g
a
b
c
d
e
f
g
z
S
0
∞
∞
∞
∞
∞
∞
∞
a
x
4(a) 3(a) ∞
∞
∞
∞
∞
c
x
x
1
20
15
35
2
10
3
40
35
5
75
7
50
15
4
10
6
1
2
3
4
5
6
7
S
0
∞
∞
∞
∞
∞
∞
1
x
15(1)
35(1)
∞
20(1)
∞
∞
2
x
x
Theorems
Dijkstra’s algorithm finds the length of a shortest
path between two vertices in a connected simple
undirected weighted graph G=(V,E).
The time required by Dijkstra's algorithm is O(|V|2).
It will be reduced to O(|E|log|V|) if heap is used to keep
{vV\Si : L(v) < }, where Si is the set S after iteration i.
The Traveling Salesman Problem
The
traveling salesman problem is one of the classical problems
in computer science.
A
traveling salesman wants to visit a number of cities and then
return to his starting point. Of course he wants to save time and
energy, so he wants to determine the shortest cycle for his trip.
We
can represent the cities and the distances between them by a
weighted, complete, undirected graph.
The
problem then is to find the shortest cycle (of minimum total
weight that visits each vertex exactly one).
The Traveling Salesman Problem

Importance:
•
•
Variety of scheduling application can be solved as a
traveling salesmen problem.
Examples:
• Ordering drill position on a drill press.
• School bus routing.
THE FEDERAL EMERGENCY MANAGEMENT
AGENCY

A visit must be made to four local offices
of FEMA, going out from and returning to
the same main office in Northridge,
Southern California.
FEMA traveling salesman
Network representation
2
40
3
25
35
50
40
50
1
4
45
65
30
80
Home
FEMA - Traveling Salesman
• Solution approaches
– Enumeration of all possible cycles.
• This results in (m-1)! cycles to enumerate for a graph with m
nodes.
• Only small problems can be solved with this approach.
FEMA – full enumeration
Possible cycles
Cycle
Total Cost
1. H-O1-O2-O3-O4-H
2. H-O1-O2-O4-O3-H
3. H-O1-O3-O2-O3-H
4. H-O1-O3-O4-O2-H
5. H-O1-O4-O2-O3-HFor this problem we have
6. H-O1-O4-O3-O2-H(5-1)! / 2 = 12 cycles.
Symmetrical problems
7. H-O2-O3-O1-O4-H
need to enumerate only
8. H-O2-O1-O3-O4-H
(m-1)! / 2 cycles.
9. H-O2-O4-O1-O3-H
10. H-O2-O1-O4-O3-H
11. H-O3-O1-O2-O4-H
12. H-O3-O1-O2-O4-H
210
195
240
200
225
200
265
235
250
220
260
260
Minimum
FEMA – optimal solution
2
25
40
3
50
40
1
50
30
45
35
4
65
80
Home
The Traveling Salesman Problem
Finding
the shortest cycle is different than Dijkstra’s shortest path. It
is much harder too, no algorithm exists with polynomial worst-case
time complexity!
This
means that for large numbers of vertices, solving the traveling
salesman problem is impractical.
The
problem has theoretical importance because it represents a
class of difficult problems known as NP-hard problems.
In
these cases, we can use efficient approximation algorithms
that determine a path whose length may be slightly larger than the
traveling salesman’s path.