程序代写代做代考 algorithm Directed Graphs

Directed Graphs

More Terminology

Definition (Directed Graph)

A directed graph is a graph G = (V ,E ) where V is a set (of objects) and
E is a set of ordered pairs of elements of V .

In a directed graph each edge (u, v) has a direction

Edges (u, v) and (v , u) can both exist, and have different weights

An undirected graph can be seen as a special type of directed graph

Algorithms (580) Weighted Graphs February 2018 32 / 54

Directed Graphs

Shortest Paths

With weighted edges a simple breadth-first search will not find the shortest
paths

The ‘shortest’ path from a to e is 〈a, b, c , e〉

Questions

What might a “brute force” algorithm do?

How long would it take?

Algorithms (580) Weighted Graphs February 2018 33 / 54

The Bellman-Ford Algorithm Algorithm

Bellman-Ford

The Bellman-Ford algorithm solves the general problem where edges may
have negative weights

A distance array is used again

distance[v] is the current estimate of the shortest path to v

The algorithm proceeds by gradually reducing these estimates

Algorithms (580) Weighted Graphs February 2018 34 / 54

The Bellman-Ford Algorithm Algorithm

Bellman-Ford

Relaxing edge (u, v) checks if s u → v reduces distance[v]

Relax (Input: weighted edge (u, v))

If distance[v ] is greater than distance[u] + w(u, v) then:

distance[v ] is distance[u] + w(u, v)
Parent of v is u

Algorithms (580) Weighted Graphs February 2018 35 / 54

The Bellman-Ford Algorithm Algorithm

Bellman-Ford

Bellman-Ford (Input: weighted graph G = (V ,E ) and vertex s)

Set distance[v ] =∞ for all vertices
Set distance[s] = 0

Repeat |V | − 1 times:
For each edge e ∈ E

Relax e

For each edge (u, v) ∈ E
If distance[v ] is greater than distance[u] + w(u, v)

Return FALSE

Return TRUE

Question

Why does the loop run |V | − 1 times?

Algorithms (580) Weighted Graphs February 2018 36 / 54

The Bellman-Ford Algorithm Algorithm

Bellman-Ford

Bellman-Ford (Input: weighted graph G and vertex s)

Set distance[v ] =∞ for all vertices
Set distance[s] = 0

Repeat |V | − 1 times:
For each edge e ∈ E

Relax e

For each edge (u, v) ∈ E
If distance[v ] is greater than distance[u] + w(u, v)

Return FALSE

Return TRUE

All edges are relaxed |V | − 1 times so all paths are tried
The algorithm returns FALSE if a negative weight cycle occurs

Algorithms (580) Weighted Graphs February 2018 37 / 54

The Bellman-Ford Algorithm Algorithm

Bellman-Ford

Relax (Input: weighted edge (u, v))

If distance[v ] is greater than distance[u] + w(u, v) then:

distance[v ] is distance[u] + w(u, v)
Parent of v is u

In iteration i all edges in paths containing i edges have been relaxed

The most edges in any (simple) path is |V | − 1

Algorithms (580) Weighted Graphs February 2018 38 / 54

The Bellman-Ford Algorithm Algorithm

Bellman-Ford

Relax (Input: weighted edge (u, v))

If distance[v ] is greater than distance[u] + w(u, v) then:

distance[v ] is distance[u] + w(u, v)
Parent of v is u

In iteration i all edges in paths containing i edges have been relaxed

The most edges in any (simple) path is |V | − 1

Algorithms (580) Weighted Graphs February 2018 38 / 54

The Bellman-Ford Algorithm Algorithm

Bellman-Ford

Relax (Input: weighted edge (u, v))

If distance[v ] is greater than distance[u] + w(u, v) then:

distance[v ] is distance[u] + w(u, v)
Parent of v is u

In iteration i all edges in paths containing i edges have been relaxed

The most edges in any (simple) path is |V | − 1

Algorithms (580) Weighted Graphs February 2018 38 / 54

The Bellman-Ford Algorithm Algorithm

Bellman-Ford

Relax (Input: weighted edge (u, v))

If distance[v ] is greater than distance[u] + w(u, v) then:

distance[v ] is distance[u] + w(u, v)
Parent of v is u

In iteration i all edges in paths containing i edges have been relaxed

The most edges in any (simple) path is |V | − 1

Algorithms (580) Weighted Graphs February 2018 38 / 54

The Bellman-Ford Algorithm Algorithm

Bellman-Ford

Relax (Input: weighted edge (u, v))

If distance[v ] is greater than distance[u] + w(u, v) then:

distance[v ] is distance[u] + w(u, v)
Parent of v is u

In iteration i all edges in paths containing i edges have been relaxed

The most edges in any (simple) path is |V | − 1

Algorithms (580) Weighted Graphs February 2018 38 / 54

The Bellman-Ford Algorithm Algorithm

Bellman-Ford

Relax (Input: weighted edge (u, v))

If distance[v ] is greater than distance[u] + w(u, v) then:

distance[v ] is distance[u] + w(u, v)
Parent of v is u

In iteration i all edges in paths containing i edges have been relaxed

The most edges in any (simple) path is |V | − 1

Algorithms (580) Weighted Graphs February 2018 38 / 54

The Bellman-Ford Algorithm Algorithm

Bellman-Ford

Relax (Input: weighted edge (u, v))

If distance[v ] is greater than distance[u] + w(u, v) then:

distance[v ] is distance[u] + w(u, v)
Parent of v is u

In iteration i all edges in paths containing i edges have been relaxed

The most edges in any (simple) path is |V | − 1

Algorithms (580) Weighted Graphs February 2018 38 / 54

The Bellman-Ford Algorithm Algorithm

Bellman-Ford

Definition (Negative Weight Cycle)

A path C = 〈v1, v2, . . . , vn〉 in a directed graph is a negative weight cycle
iff C is a cycle and

∑n−1
i=1 w(vi , vi+1) < 0. If a directed graph G contains a negative weight cycle 〈v1, v2, . . . , vn〉 then: The shortest paths to all vertices reachable from v1, . . . , vn are undefined In this case Bellman-Ford will return FALSE Algorithms (580) Weighted Graphs February 2018 39 / 54 The Bellman-Ford Algorithm Algorithm Time Question What is the time complexity of Bellman–Ford? Bellman-Ford (Input: weighted graph G and vertex s) Set distance[v ] =∞ for all vertices Set distance[s] = 0 Repeat |V | − 1 times: For each edge e ∈ E Relax e For each edge (u, v) ∈ E If distance[v ] is greater than distance[u] + w(u, v) Return FALSE Return TRUE Algorithms (580) Weighted Graphs February 2018 40 / 54 Dijkstra’s Algorithm Dijkstra’s Algorithm If G has non-negative edges only then we can use Dijkstra’s Algorithm Bellman-Ford relaxes every edge of every path The running time of Bellman-Ford is O(VE ) Dijkstra’s algorithm instead uses a greedy strategy Algorithms (580) Weighted Graphs February 2018 41 / 54 Dijkstra’s Algorithm Dijkstra’s Algorithm Basic idea: Relax edges from one vertex Will have then found shortest path to at least one other vertex Repeat Algorithms (580) Weighted Graphs February 2018 42 / 54 Dijkstra’s Algorithm Dijkstra’s Algorithm Dijkstra’s algorithm maintains a set of vertices whose distance[v ] is correct Dijkstra (Input: weighted graph G = (V ,E ), vertex s) distance[v] = infinity for all vertices distance[s] = 0 S = {} while V - S != {} u is vertex in V - S with least distance[u] for v in G.adj[u] relax (u,v) S = S + {u} The next vertex added to S is the one with the least distance[u] This value is now assumed to be minimal. Is this correct? Algorithms (580) Weighted Graphs February 2018 43 / 54 Dijkstra’s Algorithm Correctness Correctness In the following, the function p represents the (actual) length of the shortest path from the source to a given vertex If there is no path s v , then p(v) =∞ ∞+ x =∞, for all x ∈ R Theorem (Correctness of Dijkstra) At the start of the while loop of Dijkstra’s algorithm, run on weighted, directed graph G = (V ,E ) with non-negative weight function w , and vertex s ∈ V : if distance[v ] = p(v) for all vertices v ∈ S , then distance[u] = p(u) for u, the next vertex added to S . Algorithms (580) Weighted Graphs February 2018 44 / 54 Dijkstra’s Algorithm Correctness Proof First we prove two useful properties Lemma (Triangle Lemma) Let G = (V ,E ) be a weighted, directed graph with weight function w , and source vertex s. If (u, v) is an edge in E , then p(v) ≤ p(u) + w(u, v). Proof. If there is no path s u, then p(u) =∞, so p(v) ≤ p(u) and the lemma holds. If there is a path s u, then s u → v is a path to v . The length of one such path to v is p(u) + w(u, v). The shortest path to v cannot be longer than this, so the lemma also holds in this case. Algorithms (580) Weighted Graphs February 2018 45 / 54 Dijkstra’s Algorithm Correctness Proof First we prove two useful properties Lemma (Triangle Lemma) Let G = (V ,E ) be a weighted, directed graph with weight function w , and source vertex s. If (u, v) is an edge in E , then p(v) ≤ p(u) + w(u, v). Proof. If there is no path s u, then p(u) =∞, so p(v) ≤ p(u) and the lemma holds. If there is a path s u, then s u → v is a path to v . The length of one such path to v is p(u) + w(u, v). The shortest path to v cannot be longer than this, so the lemma also holds in this case. Algorithms (580) Weighted Graphs February 2018 45 / 54 Dijkstra’s Algorithm Correctness Proof First we prove two useful properties Lemma (Triangle Lemma) Let G = (V ,E ) be a weighted, directed graph with weight function w , and source vertex s. If (u, v) is an edge in E , then p(v) ≤ p(u) + w(u, v). Proof. If there is no path s u, then p(u) =∞, so p(v) ≤ p(u) and the lemma holds. If there is a path s u, then s u → v is a path to v . The length of one such path to v is p(u) + w(u, v). The shortest path to v cannot be longer than this, so the lemma also holds in this case. Algorithms (580) Weighted Graphs February 2018 45 / 54 Dijkstra’s Algorithm Correctness Proof First we prove two useful properties Lemma (Triangle Lemma) Let G = (V ,E ) be a weighted, directed graph with weight function w , and source vertex s. If (u, v) is an edge in E , then p(v) ≤ p(u) + w(u, v). Proof. If there is no path s u, then p(u) =∞, so p(v) ≤ p(u) and the lemma holds. If there is a path s u, then s u → v is a path to v . The length of one such path to v is p(u) + w(u, v). The shortest path to v cannot be longer than this, so the lemma also holds in this case. Algorithms (580) Weighted Graphs February 2018 45 / 54 Dijkstra’s Algorithm Correctness Proof First we prove two useful properties Lemma (Triangle Lemma) Let G = (V ,E ) be a weighted, directed graph with weight function w , and source vertex s. If (u, v) is an edge in E , then p(v) ≤ p(u) + w(u, v). Proof. If there is no path s u, then p(u) =∞, so p(v) ≤ p(u) and the lemma holds. If there is a path s u, then s u → v is a path to v . The length of one such path to v is p(u) + w(u, v). The shortest path to v cannot be longer than this, so the lemma also holds in this case. Algorithms (580) Weighted Graphs February 2018 45 / 54 Dijkstra’s Algorithm Correctness Proof This lemma shows that distance[u] is always an upper bound for p(u) Lemma (Upper Bound Lemma) Let G = (V ,E ) be a weighted, directed graph with weight function w , and source vertex s. If distance[s] is initialised to 0 and distance[v ], for all v ∈ V where v 6= s, is initialised to ∞, then distance[u] ≥ p(u), for all u ∈ V , after relaxing any sequence of edges in G . Proof. Firstly, consider a sequence of 0 relaxed edges. distance[u] =∞, for u 6= s distance[s] = 0 If s is part of a negative weight cycle, then p(s) = −∞, otherwise p(s) = 0. So, distance[u] ≥ p(u) for all u ∈ V in this case. Algorithms (580) Weighted Graphs February 2018 46 / 54 Dijkstra’s Algorithm Correctness Proof Proof (continued). Now consider the relaxation of edge (x , y) within some sequence of relaxations. Assume distance[u] ≥ p(u) for all u ∈ V , prior to relaxing (x , y) When (x , y) is relaxed either all distance[u] are unchanged, or distance[y ] = distance[x ] + w(x , y). In the latter case: distance[y ] = distance[x ] + w(x , y), so distance[y ] ≥ p(x) + w(x , y), by the assumption, and distance[y ] ≥ p(y), by the Triangle Lemma So after relaxing (x , y), distance[u] ≥ p(u) still holds for all vertices in G , and by the principle of induction distance[u] ≥ p(u) is always true for any sequence of edge relaxations. Algorithms (580) Weighted Graphs February 2018 47 / 54 Dijkstra’s Algorithm Correctness Proof Theorem (Correctness of Dijkstra) At the start of the while loop of Dijkstra’s algorithm, run on weighted, directed graph G = (V ,E ) with non-negative weight function w , and vertex s ∈ V : if distance[v ] = p(v) for all vertices v ∈ S , then distance[u] = p(u) for u, the next vertex added to S . Proof. If there is no path s u then p(u) =∞. Since: distance[u] ≥ p(u), by the Upper Bound Lemma, then distance[u] =∞, so distance[u] = p(u). and the theorem is true. Algorithms (580) Weighted Graphs February 2018 48 / 54 Dijkstra’s Algorithm Correctness Proof Proof (continued). If there is a path s u, then consider the shortest such path. Let this path be s px → y qu, where y is the first vertex on the path not in S . First, it is shown that distance[y ] = p(y), as follows. s px → y must be a shortest path from s to y . (Or there would be a shorter path to u.) Then, distance[x ] = p(x) distance[y ] = distance[x ] + w(x , y) = p(x) + w(x , y) since x is in S and (x , y) was relaxed when x was added to S . Algorithms (580) Weighted Graphs February 2018 49 / 54 Dijkstra’s Algorithm Correctness Proof Proof (continued). And, since s px → y is a shortest path from s to y , then: p(y) = p(x) + w(x , y) = distance[y ] Next we show that distance[u] = distance[y ] = p(y) = p(u) using the observations that (1) distance[u] ≤ distance[y ], since u is added next to S (2) p(y) ≤ p(u), since all edges are non-negative. Algorithms (580) Weighted Graphs February 2018 50 / 54 Dijkstra’s Algorithm Correctness Proof Proof (continued). So, beginning with Observation (1): distance[u] ≤ distance[y ], and therefore distance[u] ≤ p(y), and distance[u] ≤ p(u), by Observation (2). But distance[u] ≥ p(u) by the Upper Bound Lemma, so distance[u] = p(u) and the theorem is true. Algorithms (580) Weighted Graphs February 2018 51 / 54 Dijkstra’s Algorithm Performance Dijkstra’s Algorithm Discussion What is the time complexity of Dijkstra’s algorithm? Dijkstra (Input: weighted graph G = (V ,E ), vertex s) distance[v] = infinity for all vertices distance[s] = 0 S = {} while V - S != {} u is vertex in V - S with least distance[u] for v in G.adj[u] relax (u,v) S = S + {u} Algorithms (580) Weighted Graphs February 2018 52 / 54 Dijkstra’s Algorithm Performance Dijkstra’s Algorithm Discussion What is the time complexity of Dijkstra’s algorithm? Dijkstra (Input: weighted graph G = (V ,E ), vertex s) distance[v] = infinity for all vertices distance[s] = 0 S = {} while V - S != {} u is vertex in V - S with least distance[u] for v in G.adj[u] relax (u,v) affects ordering of vertices S = S + {u} Algorithms (580) Weighted Graphs February 2018 53 / 54 Dijkstra’s Algorithm Performance Performance The running time of Dijkstra’s algorithm depends on the way in which the ordering of the vertices is managed Implement V − S as a priority queue There is one iteration through the graph vertices Each edge is relaxed once, giving an aggregate of |E | With a binary-heap-based priority queue adding, removing and updating (changing key) all run in O(log2 V ) time. Overall running time is then O(E log2 V ) Algorithms (580) Weighted Graphs February 2018 54 / 54