Shortest Paths

Text

Discrete Mathematics and Its

Applications (7 Edition)
th

Kenneth H. Rosen

Chapter 10.6
Instructor: Longin Jan Latecki
latecki@[Link]
Some slides from Chuck Allison,
Michael T. Goodrich, and Roberto Tamassia
Weighted Graphs

Graphs that have a number assigned to

each edge are called weighted graphs. BOS

CHI NY
SF DEN

ATL
LA

MIA
Weighted Graphs
MILES

BOS
2534

1855 722 NY
CHI
SF DEN 908
957

349
ATL
LA 595
MIA
Weighted Graphs
FARES

BOS
$129
$39
$99 $59 NY
CHI
SF DEN
$89

$39
ATL
LA

MIA
Weighted Graphs
FLIGHT
TIMES

BOS
4:05
0:50
2:55 NY
CHI 1:50
SF DEN 2:10
2:20

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.
 % L = d (on previous slides)
% S represents the “cloud”

(such that v is adjacent to u)

Subpaths of shortest paths are
shortest paths
Dijkstra Animation
⚫ Youtube video:
⚫ [Link]

⚫ Java animation:
⚫ [Link]
[Link]/ikeda/suuri/dijkstra/[Link]
Find a shortest path
from a to z

a b c d e z S
0 ∞ ∞ ∞ ∞ ∞ a
Find a shortest path
from a to z

a b c d e z S
0 ∞ ∞ ∞ ∞ ∞ a
x 4(a) 3(a) ∞ ∞ ∞ c
x x
Find a shortest path
from a to z

a b c d e z S
0 ∞ ∞ ∞ ∞ ∞ a
x 4(a) 3(a) ∞ ∞ ∞ c
x 3(a,c) x 10(a,c) 12(a,c) ∞ b
Find a shortest path
from a to z

a b c d e z S
0 ∞ ∞ ∞ ∞ ∞ a
x 4(a) 3(a) ∞ ∞ ∞ c
x 3(a,c) x 10(a,c) 12(a,c) ∞ b
x x x 8(a,c,b) 12(a,c) ∞ d
x x x x
Find a shortest path
from a to z

a b c d e z S
0 ∞ ∞ ∞ ∞ ∞ a
x 4(a) 3(a) ∞ ∞ ∞ c
x 3(a,c) x 10(a,c) 12(a,c) ∞ b
x x x 8(a,c,b) 12(a,c) ∞ d
x x x x 10(a,c,b,d) 14(a,c,b,d) e
x x x x x
Find a shortest path
from a to z

a b c d e z S
0 ∞ ∞ ∞ ∞ ∞ a
x 4(a) 3(a) ∞ ∞ ∞ c
x 3(a,c) x 10(a,c) 12(a,c) ∞ b
x x x 8(a,c,b) 12(a,c) ∞ d
x x x x 10(a,c,b,d) 14(a,c,b,d) e
x x x x x 13(a,c,b,d,e) z
x x x x x x
Find a shortest path
from a to z

a b c d e z S
0 ∞ ∞ ∞ ∞ ∞ a
x 4(a) 3(a) ∞ ∞ ∞ c
x 3(a,c) x 10(a,c) 12(a,c) ∞ b
x x x 8(a,c,b) 12(a,c) ∞ d
x x x x 10(a,c,b,d) 14(a,c,b,d) e
x x x x x 13(a,c,b,d,e) z
x x x x x x
 1 20
15
35 5
10 75
2
3
50
7
40 35
15
1 2 3 4 5 6 7 S
4
10
6
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

1 50
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 210
2. H-O1-O2-O4-O3-H 195 Minimum
3. H-O1-O3-O2-O3-H 240
4. H-O1-O3-O4-O2-H 200
5. H-O1-O4-O2-O3-HFor this problem we have 225
6. H-O1-O4-O3-O2-H(5-1)! / 2 = 12 cycles. 200
Symmetrical problems
7. H-O2-O3-O1-O4-H 265
need to enumerate only
8. H-O2-O1-O3-O4-H 235
(m-1)! / 2 cycles.
9. H-O2-O4-O1-O3-H 250
10. H-O2-O1-O4-O3-H 220
11. H-O3-O1-O2-O4-H 260
12. H-O3-O1-O2-O4-H 260
FEMA – optimal solution

2 40
3
25 50 35
40
1 50 4
45 65
30 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!
⚫Thismeans 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.