程序代写代做代考 algorithm data structure C game graph Graphs

Graphs
Graph Algorithms (continued) COMP4500/7500
Advanced Algorithms & Data Structures
August 21, 2019
August 21, 2019 1/72

Graphs
Overview
Admin/reminders Shortest paths:
Dijkstra’s algorithm Bellman-Ford algorithm
Priority-first search
August 21, 2019 2/72

Graphs
Shortest paths
A path p from v1 to vn is a sequence of vertices. v1 →v2 →v3 →…→vn
The total weight of the path, weight(p), is the sum of the edges along the way.
n−1
weight(p) = 􏰀 weight(vi , vi+1)
i=1
The distance from v1 to vn is the minimum weight of all paths
from v1 to vn.
Ashortestpathfromv1 tovn isapathfromv1 tovn of minimum weight.
August 21, 2019 3/72

Graphs
Shortest paths
Types of shortest paths:
1 Single-pair. Given a pair (u, v ), find a shortest path between them.
2 Single-source. Given a vertex v, find a shortest path to every other vertex. This is our focus.
3 Single-destination. Given a vertex v, find a shortest path from every other vertex.
4 All-pairs. Given a graph, find a shortest path between every pair of vertices.
August 21, 2019 4/72

Graphs
SINGLESOURCESHORTESTPATHS(G, w, s): key ideas
Given graph G with weight-function w and source vertex s, for each vertex v ∈ G.V we calculate:
v.d it’s distance from source vertex s
v.π the predecessor to v on a shortest path from s to v
Steps:
Initialise s.d = 0 and v.d = ∞ for all v ∈ G.V−{s}.
invariant: distance(s,v) ≤ v.d ≤ ∞ Initialise v.π = NIL for all v ∈ G.V.
invariant: v.π is v’s predecessor on the shortest path found so far
… we relax our estimates until they reach a solution …
August 21, 2019 5/72

Graphs
Edge relaxation: relax edge (u, v ) ∈ G.E
RELAX(u,v,w):
updates v.d and v.π if v can be reached faster via intermediate vertex u.
RELAX(u,v,w)
1 ifv.d>u.d+w(u,v)
2 3
v.d = u.d +w(u,v) v.π = u
preserves the distance and predecessor invariants: invariant: distance(s,v) ≤ v.d ≤ ∞
invariant: v.π is v’s predecessor on the shortest path found so far
does not change v.d and v.π if the shortest path to v has already been found
August 21, 2019 6/72

Graphs
Edge relaxation
Let
be a shortest path from v1 to vn.
If edge (vi−1,vi) is relaxed after a shortest path to vi−1 is found, we will find a shortest path to vi .
pn =v1 →v2 →v3 →…→vn
August 21, 2019 7/72

Graphs
Graphs without negative weight edges
Let
be any shortest path from v1 to vn in a weighted graph with no
pn =v1 →v2 →v3 →…→vn negative weight edges.
For all vi ∈ v1, v2, . . . vn−1, we must have that the path prefix pi =v1 →v2 →v3 →…→vi
is a shortest path from v1 to vi, and weight(pi) ≤ weight(pn). I.e. distance(v1, vi ) ≤ distance(v1, vn).
August 21, 2019 8/72

Graphs
Relaxation for graphs without negative weight edges
If we:
relax each edge (u, v ) ∈ G.E once
in order of u’s distance from start vertex s,
then we will find all the shortest paths from s in G.
August 21, 2019 9/72

Graphs
DIJKSTRA(G, w, s)
Solves the single-source shortest paths problem for weighted graphs without negative weight edges.
[AI in computer games use a sophisticated variant called A∗.]
August 21, 2019 10/72

Graphs
DIJKSTRA(G, w, s): key idea
For each vertex v ∈ G.V we calculate: v.d it’s distance from source vertex s
v.π the predecessor to v on the shortest path from s to v
Steps:
Initialise s.d = 0 and v.d = ∞ for all v ∈ G.V−{s}.
invariant: distance(s,v) ≤ v.d ≤ ∞ Initialise v.π = NIL for all v ∈ G.V.
invariant: v.π is a predecessor on shortest path found so far
Visit each vertex in order of its distance from the source vertex – when we visit a vertex we relax its outgoing edges.
Generalises breadth-first search for weighted graphs.
August 21, 2019 11/72

Graphs
DIJKSTRA(G, w, s)
How do we (efficiently) find the next vertex to visit?
Let
S the set of visited vertices
We maintain
Q a priority queue containing vertices V−S, with key v.d
At each step we visit the vertex u on Q with the minimum key.
When we visit vertex u, we are guaranteed to have already found a shortest path to u – assuming that the graph has no negative weight edges!.
August 21, 2019 12/72

Graphs
DIJKSTRA(G, w, s): why does the idea work?
When we visit a vertex u, we have already found a shortest path to u.
Let v be the predecessor of u on a shortest path from s to u.
distance(s, v ) ≤ distance(s, u), and so either
we have already visited v and relaxed its edges, or
we already found another shortest-path to u of length distance(s, u) = distance(s, v )
August 21, 2019 13/72

Graphs
Dijkstra’s algorithm
DIJKSTRA(G, w, s)
1 2 3 4 5 6 7 8 9
1 2 3 4
/ G is the graph, w the weight function, s the source vertex INIT-SINGLE-SOURCE(G,s)
S=∅ //Sisthesetofvisitedvertices
Q = G.V // Q is a priority queue maintaining G.V − S whileQ̸=∅
u = EXTRACT-MIN(Q)
S = S ∪ {u}
for each vertex v ∈ G.Adj[u]
RELAX(u,v,w) INIT-SINGLE-SOURCE(G,s)
RELAX(u,v,w)
1 ifv.d>u.d+w(u,v)
2 v.d = u.d +w(u,v)
3 v.π = u
for each vertex v ∈ G.V v.d = ∞
v.π = NIL s.d=0
August 21, 2019 14/72

Graphs
Example of Dijkstra’s algorithm
Graph with
nonnegative
edgeweights: A A
10
B2D BD
1 4 8 7 9
3
C2E
CE
November 14, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L17.16
August 21, 2019 15/72

Graphs
Example of Dijkstra’s
algorithm
Initialize:
∞2∞ BD
BD
10 0A14879
A
Q:ABCDE3C E
0∞∞∞∞
S: {}
C2E ∞∞
November 14, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L17.17
August 21, 2019 16/72

Graphs
Example of Dijkstra’s
algorithm
“A” ← EXTRACT-MIN(Q): 10
0A14879 A
0∞∞∞∞
S: { A }
November 14, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L17.18
∞2∞ BD
BD
Q:ABCDE3C E
C2E ∞∞
August 21, 2019 17/72

Graphs
Example of Dijkstra’s
algorithm
Relax all edges leaving A: 10
0A14879 A
0∞∞∞∞ 10 3 ∞ ∞
S: { A }
November 14, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L17.19
10 2 ∞ BD
BD
Q:ABCDE3C E
C2E 3∞
August 21, 2019 18/72

Graphs
Example of Dijkstra’s
algorithm
“C” ← EXTRACT-MIN(Q): 10
0A14879 A
0∞∞∞∞ 10 3 ∞ ∞
S: { A, C }
November 14, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L17.20
10 2 ∞ BD
BD
Q:ABCDE3C E
C2E 3∞
August 21, 2019 19/72

Graphs
Example of Dijkstra’s
algorithm
Relax all edges leaving C: 10
0A14879 A
0∞∞∞∞ 10 3 ∞ ∞ 7 115
7 2 11 BD
BD
Q:ABCDE3C E
C2E 35
S: { A, C }
November 14, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L17.21
August 21, 2019 20/72

Graphs
Example of Dijkstra’s
algorithm
“E” ← EXTRACT-MIN(Q): 10
0A14879 A
0∞∞∞∞ 10 3 ∞ ∞ 7 115
7 2 11 BD
BD
Q:ABCDE3C E
C2E 35
S: { A, C, E }
November 14, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L17.22
August 21, 2019 21/72

Graphs
Example of Dijkstra’s
algorithm
Relax all edges leaving E: 10
0A14879 A
0∞∞∞∞ 10 3 ∞ ∞ 7 115
7 2 11 BD
BD
Q:ABCDE3C E
C2E 35
S: { A, C, E }
November 14, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L17.23
7 11
August 21, 2019 22/72

Graphs
Example of Dijkstra’s
algorithm
“B” ← EXTRACT-MIN(Q): 10
0A14879 A
0∞∞∞∞ 10 3 ∞ ∞ 7 115
7 2 11 BD
BD
Q:ABCDE3C E
C2E 35
S: { A, C, E, B } November 14, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L17.24
7 11
August 21, 2019 23/72

Graphs
Example of Dijkstra’s
algorithm
Relax all edges leaving B: 10
0A14879 A
0∞∞∞∞ 10 3 ∞ ∞ 7 115
729 BD
BD
Q:ABCDE3C E
C2E 35
S: { A, C, E, B } November 14, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L17.25
7 11 9
August 21, 2019 24/72

Graphs
Example of Dijkstra’s
algorithm
“D” ← EXTRACT-MIN(Q): 10
0A14879 A
0∞∞∞∞ 10 3 ∞ ∞ 7 115
729 BD
BD
Q:ABCDE3C E
C2E 35
S: { A, C, E, B, D } November 14, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L17.26
7 11 9
August 21, 2019 25/72

Graphs
Analysis of Dijkstra
while Q ≠ ∅
do u ← EXTRACT-MIN(Q)
S ← S ∪ {u}
for each v ∈ Adj[u]
do if d[v] > d[u] + w(u, v)
then d[v] ← d[u] + w(u, v)
November 14, 2005
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L17.34
August 21, 2019 26/72

Graphs
|V| times
Analysis of Dijkstra
while Q ≠ ∅
do u ← EXTRACT-MIN(Q)
S ← S ∪ {u}
for each v ∈ Adj[u]
do if d[v] > d[u] + w(u, v)
then d[v] ← d[u] + w(u, v)
November 14, 2005
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L17.35
August 21, 2019 27/72

Graphs
|V| times
degree(u) times
S ← S ∪ {u}
for each v ∈ Adj[u]
do if d[v] > d[u] + w(u, v)
then d[v] ← d[u] + w(u, v)
Analysis of Dijkstra
while Q ≠ ∅
do u ← EXTRACT-MIN(Q)
November 14, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L17.36
August 21, 2019 28/72

Graphs
Analysis of Dijkstra
while Q ≠ ∅
do u ← EXTRACT-MIN(Q)
|V| times
degree(u) times
S ← S ∪ {u}
for each v ∈ Adj[u]
do if d[v] > d[u] + w(u, v)
then d[v] ← d[u] + w(u, v)
Handshaking Lemma ⇒ Θ(E) implicit DECREASE-KEY’s.
November 14, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L17.37
August 21, 2019 29/72

Graphs
Analysis of Dijkstra
while Q ≠ ∅
do u ← EXTRACT-MIN(Q)
|V| times
degree(u) times
S ← S ∪ {u}
for each v ∈ Adj[u]
do if d[v] > d[u] + w(u, v)
then d[v] ← d[u] + w(u, v)
Handshaking Lemma ⇒ Θ(E) implicit DECREASE-KEY’s. Time = Θ(V·TEXTRACT-MIN + E·TDECREASE-KEY)
Note: Same formula as in the analysis of Prim’s
minimum spanning tree algorithm.
November 14, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L17.38
August 21, 2019 30/72

Graphs
Analysis of Dijkstra (continued)
Time = Θ(V)·TEXTRACT-MIN + Θ(E)·TDECREASE-KEY Q TEXTRACT-MIN TDECREASE-KEY Total
November 14, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L17.39
August 21, 2019 31/72

Graphs
Analysis of Dijkstra (continued)
Time = Θ(V)·TEXTRACT-MIN + Θ(E)·TDECREASE-KEY Q TEXTRACT-MIN TDECREASE-KEY Total array O(V) O(1) O(V2)
November 14, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L17.40
August 21, 2019 32/72

Graphs
Analysis of Dijkstra (continued)
Time = Θ(V)·TEXTRACT-MIN + Θ(E)·TDECREASE-KEY
Q TEXTRACT-MIN TDECREASE-KEY array O(V) O(1)
Total
O(V2) O(E lg V)
binary heap
O(lg V) O(lg V)
November 14, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L17.41
August 21, 2019 33/72

Graphs
Analysis of Dijkstra (continued)
Time = Θ(V)·TEXTRACT-MIN + Θ(E)·TDECREASE-KEY
Q TEXTRACT-MIN
TDECREASE-KEY O(1)
O(lg V) O(1)
Total
O(V2) O(E lg V)
array
binary heap
Fibonacci heap
November 14, 2005
O(V)
O(lg V)
O(lg V) amortized
O(E + V lg V) worst case
amortized
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L17.42
August 21, 2019 34/72

Graphs
Negative-weight problems
What if our graph has negative weights?
Dijkstra’s algorithm might not relax edges in the right order.
I.e. (u,v) might be relaxed before the shortest path to u has been found.
August 21, 2019 35/72

Graphs
Negative-weight problems
Are shortest paths well-defined for graphs with negative weight cycles?
What is the shortest path from vertex a to a?
1b
a -1
-1
c
August 21, 2019 36/72

Graphs
Quick question
Give a directed, weighted graph with negative weights, but no negative weight cycles, for which Dijkstra’s algorithm fails.
4b
a -4 d
1c1
August 21, 2019 37/72

Graphs
Negative weight problems
Graphs with negative weights might have negative weight cycles.
Even if a graph with negative weights has no negative-weight cycles, we need to work out how to relax edges so that we are guaranteed to find shortest paths.
August 21, 2019 38/72

Graphs
Negative weight problems: the Bellman-Ford solution
What do we know? After initialization:
we have found all shortest paths that contain ≤ 0 edges. After relaxing each edge in the graph 1 time:
we have found all shortest paths that contain ≤ 1 edges. After relaxing each edge in the graph 2 times:
we have found all shortest paths that contain ≤ 2 edges. …
After relaxing each edge in the graph V −1 times:
we have found all shortest paths that contain ≤ V−1 edges.
August 21, 2019 39/72

Graphs
Bellman-Ford algorithm
The Bellman-Ford algorithm uses this idea to find: single-source shortest paths on directed graphs that may have negative-weight edges.
Moreover, it
detects negative weight cycles, returning false if one is found.
August 21, 2019 40/72

Graphs
Bellman-Ford algorithm
BELLMAN-FORD(G, w, s)
1 2 3 4 5 6 7 8 9
10 11
/ G is the graph, w the weight function, s the source vertex INIT-SINGLE-SOURCE(G,s)
/ Relax each edge V−1 times to find shortest paths fori=1to|G.V|−1
for each edge (u, v) ∈ G.E RELAX(u,v,w)
/ Check for negative-weight cycles for each edge (u, v) ∈ G.E
if v.d > u.d + w(u, v) return FALSE
return TRUE
What is the time complexity? O(VE) (i.e., could be O(V3)).
August 21, 2019 41/72

Graphs
Example of Bellman-Ford
B
B2 A32E
–1 A1E
4
C5D
–3
CD
November 16, 2005
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
L18.5
August 21, 2019 42/72

Graphs
Example of Bellman-Ford
∞
B
0 –1 B 2 ∞ A32E
A1E
–3
4
C5D
CD
November 16, 2005
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
L18.6
∞∞
Initialization.
August 21, 2019 43/72

Graphs
Example of Bellman-Ford
∞
A3E A5 12 8E
4 C 6 D –3 C5D
∞∞
Order of edge relaxation.
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
B1 B2
–1 04732∞
November 16, 2005
L18.7
August 21, 2019 44/72

Graphs
Example of Bellman-Ford
∞
A3E A5 12 8E
4 C 6 D –3 C5D
∞∞
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
B1 B2
–1 04732∞
November 16, 2005
L18.8
August 21, 2019 45/72

Graphs
Example of Bellman-Ford
∞
A3E A5 12 8E
4 C 6 D –3 C5D
∞∞
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
B1 B2
–1 04732∞
November 16, 2005
L18.9
August 21, 2019 46/72

Graphs
Example of Bellman-Ford
∞
A3E A5 12 8E
4 C 6 D –3 C5D
∞∞
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
B1 B2
–1 04732∞
November 16, 2005
L18.10
August 21, 2019 47/72

Graphs
Example of Bellman-Ford
−∞1
A3E A5 12 8E
4 C 6 D –3 C5D
∞∞
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
B1 B2
–1 04732∞
November 16, 2005
L18.11
August 21, 2019 48/72

Graphs
Example of Bellman-Ford
−1
A3E A5 12 8E
4 C 6 D –3 C5D
2∞ End of pass 1.
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
B1 B2
–1 04732∞
November 16, 2005
L18.16
August 21, 2019 53/72

Graphs
Example of Bellman-Ford
−1
A3E A5 12 8E
4 C 6 D –3 C5D
2 −2
End of pass 2 (and 3 and 4).
November 16, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L18.25
B1 B2
–1 047321
August 21, 2019 62/72

Graphs
Quick question
Is there a more efficient way to find single-source shortest paths for directed acyclic graphs?
August 21, 2019 63/72

Graphs
Priority first search
Dijkstra’s algorithm for finding single-source shortest paths Prim’s algorithm for finding minimum spanning trees
are specializations of priority-first search.
August 21, 2019 64/72

Graphs
PRIORITYFIRSTSEACH(G, s, …)
Vertices are visited in order of their priority.
For each vertex v ∈ G.V we calculate: v.key it’s priority relative to source vertex s
v.π the predecessor to v in a priority-first search tree
The algorithm uses:
Q a priority queue of unvisited vertices with key v.key
August 21, 2019 65/72

Graphs
Priority-first search
PRIORITYFIRSTSEACH(G, s, …)
1 2 3 4 5 6
1 2 3 4
INIT-SINGLE-SOURCE(G,s) Q=G.V
whileQ̸=∅
u = EXTRACT-MIN(Q)
for each vertex v ∈ G.Adj[u]
RELAX(u,v,…) INIT-SINGLE-SOURCE(G,s)
RELAX(u,v,…)
for each vertex v ∈ G.V v.key = ∞
v.π = NIL s.key=0
1 2 3
if v.key > PRIORITY v.key = PRIORITY
v.π = u
August 21, 2019 66/72

Graphs
Priority-first search: Prim’s algorithm
Instantiate PRIORITY = weight(u, v).
G.V−Q is the subset of vertices in the MST under
construction (T )
v.key is the least weight edge connecting v to T
v.π is the vertex adjacent to v on that least-weight edge
At the end, the priority-first search tree is a minimum spanning tree.
August 21, 2019 67/72

Graphs
Priority-first search: Dijkstra’s algorithm
Instantiate PRIORITY = u.key + w(u, v).
G.V−Q is the set of vertices already visited in order of
their distance from s
v.key is the length of the shortest-path from s to v that
only uses edges adjacent to visited vertices.
v.π is the predecessor of v on the shortest-path from s to
v that only used edges adjacent to visited vertices.
At the end, the priority-first search tree is a shortest-path-tree.
August 21, 2019 68/72

Graphs
Recap of this week
1 Single-source shortest path algorithms: Dijkstra’s algorithm:
For graphs without negative-weight edges O(E lg V ) using binary heap or
O(E + V lg V ) (using Fibonacci heap)
Bellman-ford algorithm:
Handles graphs with negative-weight edges Can detect negative-weight cycles
O(EV)
Priority-first search:
Generalises Prim and Dijkstra’s algorithms
August 21, 2019 69/72

Related Posts