Shortest Paths

Сентябрь 13, 2022

Содержание

2. The Bellman-Ford algorithm 1958 1962
3. The Bellman-Ford algorithm
4. The Bellman-Ford algorithm the fixed order: (t; x); (t; y); (t; z); (x; t); (y; x);
5. The Bellman-Ford algorithm Parts (b) through (e) show the situation after each successive pass.
6. The Bellman-Ford algorithm The shortest and pred values in part (e) are the final values.
7. The Bellman-Ford algorithm Consider a shortest path from the source s to any vertex v. If
8. The Bellman-Ford algorithm Every acyclic path must contain at most n - 1 edges. If a
9. The Bellman-Ford algorithm The graph contains a negative-weight cycle and we have already run the BELLMAN-FORD
10. The Bellman-Ford algorithm How to find a negative-weight cycle, if one exists, after running BELLMAN-FORD? Go
12. The Bellman-Ford algorithm The loop of step 2 iterates n - 1 times. The loop of
13. The Bellman-Ford algorithm To find whether a negative-weight cycle exists taking O(m) time. If there is
14. The Bellman-Ford algorithm Negative-weight cycles relate to arbitrage opportunities in currency trading.
15. The Bellman-Ford algorithm n currencies c1; c2; c3; … ; cn, all the exchange rates between
16. The Bellman-Ford algorithm
17. The Bellman-Ford algorithm
18. The Bellman-Ford algorithm To find an arbitrage opportunity, if one exists, construct a directed graph with
19. The Bellman-Ford algorithm Add a new vertex s with a 0-weight edge (s; vi) to each
20. The Floyd-Warshall algorithm The classic example of all-pairs shortest paths is the table of a road
21. The Floyd-Warshall algorithm There is one problem with this example: it’s not all-pairs. If it were
22. The Floyd-Warshall algorithm What would be a rightful application of all-pairs shortest paths? Finding the diameter
23. The Floyd-Warshall algorithm Using the Floyd-Warshall algorithm, we can solve the all-pairs problem in Θ(n3) time.
24. The Floyd-Warshall algorithm The Floyd-Warshall algorithm relies on one property of shortest paths. If a shortest
25. The Floyd-Warshall algorithm the vertices are numbered from 1 to n Vertex numbers become important. shortest[u;
26. The Floyd-Warshall algorithm Let’s consider two vertices u and v. Pick a number x in the
27. The Floyd-Warshall algorithm There are two possibilities: First possibility: x is not an intermediate vertex in
28. The Floyd-Warshall algorithm adjacency-matrix representation The entry for edge (u; v) holds the weight of the
29. The Floyd-Warshall algorithm computes shortest[u; v; x] values => x=1 computes shortest[u; v; x] values =>
31. The Floyd-Warshall algorithm example shortest[2; 4; 0] is 1, because we can get from vertex 2
32. The Floyd-Warshall algorithm pred[u; v; 0] values
33. The Floyd-Warshall algorithm After running the loop for x=1
34. The Floyd-Warshall algorithm After running the loop for x=2 After running the loop for x=3
35. The Floyd-Warshall algorithm shortest[u; v; 4] and pred[u; v; 4] values
37. Скачать презентацию

Слайд 2

The Bellman-Ford algorithm
1958
1962

Слайд 3

The Bellman-Ford algorithm

Слайд 4

The Bellman-Ford algorithm
the fixed order: (t; x); (t; y); (t; z);

(x; t); (y; x); (y; z); (z; x); (z; s); (s; t); (s; y)
Part (a) shows the situation just before the first pass.

Слайд 5

The Bellman-Ford algorithm
Parts (b) through (e) show the situation after each

successive pass.

Слайд 6

The Bellman-Ford algorithm
The shortest and pred values in part (e) are

the final values.

Слайд 7

The Bellman-Ford algorithm
Consider a shortest path from the source s to

any vertex v.
If we relax the edges, in order, along a shortest path from s to v, then shortest [v] and pred[v] are correct.
If there are not negative-weight cycles on the graph, then there is always a shortest path from s to v that does not contain a cycle.

Слайд 8

The Bellman-Ford algorithm
Every acyclic path must contain at most n -

1 edges. If a path contains n edges then it must visit some vertex twice, which would make a cycle.
The first time that step 2A relaxes all edges, it must relax the first edge on this shortest path. The second time that step 2A relaxes all edges, it must relax the second edge on the shortest path, and so on. After the (n – 1) time, all edges on the shortest path have been relaxed, in order, and therefore shortest [v] and pred [v] are correct.

Слайд 9

The Bellman-Ford algorithm
The graph contains a negative-weight cycle and we have

already run the BELLMAN-FORD procedure on it.
=>around and around a negative-weight cycle =>getting a lower-weight path each time around
That means that there is at least one edge (u; v) on the cycle for which shortest[v] will decrease if you relax it again.

Слайд 10

The Bellman-Ford algorithm
How to find a negative-weight cycle, if one exists,

after running BELLMAN-FORD?
Go through the edges once again.
If we find an edge (u; v) for which
shortest [u]+weight(u; v) < shortest[v], then
vertex v is either on a negative-weight cycle or
is reachable from one.

Слайд 11

Слайд 12

The Bellman-Ford algorithm
The loop of step 2 iterates n - 1

times.
The loop of step 2A iterates m times, once per edge. ? The total running time is Θ(nm).

Слайд 13

The Bellman-Ford algorithm
To find whether a negative-weight cycle exists taking O(m)

time.
If there is a negative-weight cycle, it can contain at most n edges, and so the time to trace it out is O(n).

Слайд 14

The Bellman-Ford algorithm
Negative-weight cycles relate to arbitrage opportunities in currency trading.

Слайд 15

The Bellman-Ford algorithm
n currencies c1; c2; c3; … ; cn,
all

the exchange rates between pairs of currencies
with 1 unit of currency ci we can buy rij units of currency cj.
rij is the exchange rate between currencies ci and cj.
both i and j range from 1 to n
!!!rii = 1 for each currency ci

Слайд 16

The Bellman-Ford algorithm

Слайд 17

The Bellman-Ford algorithm

Слайд 18

The Bellman-Ford algorithm
To find an arbitrage opportunity, if one exists,
construct

a directed graph with one vertex vi for each currency ci.
For each pair of currencies ci and cj, create directed edges (vi; vj) and (vj; vi) with
weights -lg rij and -lg rji, respectively.

Слайд 19

The Bellman-Ford algorithm
Add a new vertex s with a 0-weight edge

(s; vi) to each of the vertices v1 through vn.
Run the Bellman-Ford algorithm on this graph with s as the source vertex, and
use the result to determine whether it contains a negative-weight cycle.
If it does, then the vertices on that cycle correspond to the currencies in an arbitrage opportunity.

Слайд 20

The Floyd-Warshall algorithm
The classic example of all-pairs shortest paths is

the table of a road atlas giving distances between several cities.
You find the row for one city, you find the column for the other city, and the distance between them lies at the intersection of the row and column.

Слайд 21

The Floyd-Warshall algorithm
There is one problem with this example: it’s

not all-pairs.
If it were all pairs, the table would have one row and one column for every intersection, not for just every city.
The number of rows and columns for just the one country would be in the millions.

Слайд 22

The Floyd-Warshall algorithm
What would be a rightful application of all-pairs

shortest paths?
Finding the diameter of a network: the longest of all shortest paths.
For example, suppose that a directed graph represents a communication network, and the weight of an edge gives the time it takes for a message to traverse a communication link.
Then the diameter gives you the longest possible transit time for a message in the network.

Слайд 23

The Floyd-Warshall algorithm
Using the Floyd-Warshall algorithm, we can solve the

all-pairs problem in Θ(n3) time.
For the Floyd-Warshall algorithm the graph can have negative-weight edges but no negative-weight cycles.
The Floyd-Warshall algorithm illustrates a clever algorithmic technique called “dynamic programming”.

Слайд 24

The Floyd-Warshall algorithm
The Floyd-Warshall algorithm relies on one property of

shortest paths.
If a shortest path, call it p, from vertex u to vertex v goes from vertex u to vertex x to vertex y to vertex v, then the portion of p that is between x and y is itself a shortest path from x to y.
That is, any subpath of a shortest path is itself a shortest path.

Слайд 25

The Floyd-Warshall algorithm
the vertices are numbered from 1 to n
Vertex

numbers become important.
shortest[u; v; x] is the weight of a shortest path from vertex u to vertex v in which each intermediate vertex – a vertex on the path other than u and v – is numbered from 1 to x
(u, v, and x as integers in the range 1 to n that represent vertices)

Слайд 26

The Floyd-Warshall algorithm
Let’s consider two vertices u and v.
Pick

a number x in the range from 1 to n.
Consider all paths from u to v in which all intermediate vertices are numbered at most x.
Of all these paths, let path p be one with minimum weight.
Path p either contains vertex x or it does not.

Слайд 27

The Floyd-Warshall algorithm
There are two possibilities:
First possibility: x is not

an intermediate vertex in path p. Then all intermediate vertices of path p are numbered at most x - 1. What does this mean? Shortest[u; v; x] equals shortest[u; v; x – 1].
Second possibility: x appears as an intermediate vertex in path p. Then
shortest[u; v; x] equals shortest[u; x; x – 1] +
+ shortest[x; v; x – 1].

Слайд 28

The Floyd-Warshall algorithm
adjacency-matrix representation
The entry for edge (u; v) holds

the weight of the edge, with a weight of ∞ indicating that the edge is absent.
Shortest[u; v; 0] denotes the weight of a shortest path from u to v with all intermediate vertices numbered at most 0, such a path has no intermediate vertices.

Слайд 29

The Floyd-Warshall algorithm
computes shortest[u; v; x] values => x=1
computes shortest[u;

v; x] values => x=2
computes shortest[u; v; x] values => x=2
…
computes shortest[u; v; x] values => x=n
pred[u; v; x] as the predecessor of vertex v on a shortest path from vertex u in which all intermediate vertices are numbered at most x

Слайд 30

Слайд 31

The Floyd-Warshall algorithm
example
shortest[2; 4; 0] is 1, because we can

get from vertex 2 to vertex 4 directly, with no intermediate vertices, by taking edge (2; 4) with weight 1

Слайд 32

The Floyd-Warshall algorithm
pred[u; v; 0] values

Слайд 33

The Floyd-Warshall algorithm
After running the loop for x=1

Слайд 34

The Floyd-Warshall algorithm
After running the loop for x=2
After running the

loop for x=3

Слайд 35

Shortest Paths

Содержание

The Bellman-Ford algorithm19581962

The Bellman-Ford algorithm

The Bellman-Ford algorithmthe fixed order: (t; x); (t; y); (t; z);

The Bellman-Ford algorithmParts (b) through (e) show the situation after each

The Bellman-Ford algorithmThe shortest and pred values in part (e) are

The Bellman-Ford algorithmConsider a shortest path from the source s to

The Bellman-Ford algorithmEvery acyclic path must contain at most n -

The Bellman-Ford algorithmThe graph contains a negative-weight cycle and we have

The Bellman-Ford algorithmHow to find a negative-weight cycle, if one exists,

The Bellman-Ford algorithmThe loop of step 2 iterates n - 1

The Bellman-Ford algorithmTo find whether a negative-weight cycle exists taking O(m)

The Bellman-Ford algorithmNegative-weight cycles relate to arbitrage opportunities in currency trading.

The Bellman-Ford algorithmn currencies c1; c2; c3; … ; cn, all

The Bellman-Ford algorithm

The Bellman-Ford algorithm

The Bellman-Ford algorithmTo find an arbitrage opportunity, if one exists, construct

The Bellman-Ford algorithmAdd a new vertex s with a 0-weight edge

The Floyd-Warshall algorithm The classic example of all-pairs shortest paths is

The Floyd-Warshall algorithm There is one problem with this example: it’s

The Floyd-Warshall algorithm What would be a rightful application of all-pairs

The Floyd-Warshall algorithm Using the Floyd-Warshall algorithm, we can solve the

The Floyd-Warshall algorithm The Floyd-Warshall algorithm relies on one property of

The Floyd-Warshall algorithm the vertices are numbered from 1 to nVertex

The Floyd-Warshall algorithm Let’s consider two vertices u and v. Pick

The Floyd-Warshall algorithm There are two possibilities:First possibility: x is not

The Floyd-Warshall algorithm adjacency-matrix representationThe entry for edge (u; v) holds

The Floyd-Warshall algorithm computes shortest[u; v; x] values => x=1computes shortest[u;

The Floyd-Warshall algorithm exampleshortest[2; 4; 0] is 1, because we can

The Floyd-Warshall algorithm pred[u; v; 0] values

The Floyd-Warshall algorithm After running the loop for x=1

The Floyd-Warshall algorithm After running the loop for x=2After running the

The Floyd-Warshall algorithm shortest[u; v; 4] and pred[u; v; 4] values

Похожие презентации

The Bellman-Ford algorithm
1958
1962

The Bellman-Ford algorithm
the fixed order: (t; x); (t; y); (t; z);

The Bellman-Ford algorithm
Parts (b) through (e) show the situation after each

The Bellman-Ford algorithm
The shortest and pred values in part (e) are

The Bellman-Ford algorithm
Consider a shortest path from the source s to

The Bellman-Ford algorithm
Every acyclic path must contain at most n -

The Bellman-Ford algorithm
The graph contains a negative-weight cycle and we have

The Bellman-Ford algorithm
How to find a negative-weight cycle, if one exists,

The Bellman-Ford algorithm
The loop of step 2 iterates n - 1

The Bellman-Ford algorithm
To find whether a negative-weight cycle exists taking O(m)

The Bellman-Ford algorithm
Negative-weight cycles relate to arbitrage opportunities in currency trading.

The Bellman-Ford algorithm
n currencies c1; c2; c3; … ; cn,
all

The Bellman-Ford algorithm
To find an arbitrage opportunity, if one exists,
construct

The Bellman-Ford algorithm
Add a new vertex s with a 0-weight edge

The Floyd-Warshall algorithm
The classic example of all-pairs shortest paths is

The Floyd-Warshall algorithm
There is one problem with this example: it’s

The Floyd-Warshall algorithm
What would be a rightful application of all-pairs

The Floyd-Warshall algorithm
Using the Floyd-Warshall algorithm, we can solve the

The Floyd-Warshall algorithm
The Floyd-Warshall algorithm relies on one property of

The Floyd-Warshall algorithm
the vertices are numbered from 1 to n
Vertex

The Floyd-Warshall algorithm
Let’s consider two vertices u and v.
Pick

The Floyd-Warshall algorithm
There are two possibilities:
First possibility: x is not

The Floyd-Warshall algorithm
adjacency-matrix representation
The entry for edge (u; v) holds

The Floyd-Warshall algorithm
computes shortest[u; v; x] values => x=1
computes shortest[u;

The Floyd-Warshall algorithm
example
shortest[2; 4; 0] is 1, because we can

The Floyd-Warshall algorithm
pred[u; v; 0] values

The Floyd-Warshall algorithm
After running the loop for x=1

The Floyd-Warshall algorithm
After running the loop for x=2
After running the

The Floyd-Warshall algorithm
shortest[u; v; 4] and pred[u; v; 4] values