Shortest Paths

Июль 25, 2022

Содержание

2. Dijkstra’s algorithm are given: source vertex s; the weight weight (u, v) of each edge (u,
3. Dijkstra’s algorithm
4. Dijkstra’s algorithm the situation at time 0 shortest[s]= 0
5. Dijkstra’s algorithm at time 4 shortest[y]= 4, pred[y]= s
6. Dijkstra’s algorithm at time 5 shortest[t]=5, pred[t]= y
7. Dijkstra’s algorithm at time 7 shortest[z]=7, pred[z]= y
8. Dijkstra’s algorithm at time 8 shortest[x]=8, pred[x]=t
9. Dijkstra’s algorithm Dijkstra’s algorithm works a little differently. It treats all edges the same. Dijkstra’s algorithm
11. Dijkstra’s algorithm A set Q is a set of vertices for which the final shortest and
12. Dijkstra’s algorithm A set Q is a set of vertices for which the final shortest and
13. Dijkstra’s algorithm Question 1: How does the algorithm find new paths and do the relaxation? Question
14. Dijkstra’s algorithm
15. Dijkstra’s algorithm Answer to Question 1: How does the algorithm find new paths and do the
16. Dijkstra’s algorithm Remaid: The Algorithm for Relaxing an Edge. Relax(u, v) { If (shortest[u] + weight(u,v)
17. Dijkstra’s algorithm Idea of Dijkstra’s Algorithm: Repeated Relaxation Dijkstra’s algorithm operates by maintaining a subset of
18. Dijkstra’s algorithm Idea of Dijkstra’s Algorithm: Repeated Relaxation Initially Q=NULL, the empty set, and we set
19. Dijkstra’s algorithm Idea of Dijkstra’s Algorithm: Repeated Relaxation The set Q can be implemented using an
20. Dijkstra’s algorithm The Selection in Dijkstra’s Algorithm Recall Question 2: What is the best order in
21. Dijkstra’s algorithm Question 2: How does the algorithm select which vertex among the vertices of V\Q?
22. Dijkstra’s algorithm Question: How do we implement this selection of vertices efficiently? Answer: We store the
23. Dijkstra’s algorithm Review of Priority Queues A Priority Queue is a data structure (can be implemented
24. Dijkstra’s algorithm EXTRACT-MIN (Q) removes the vertex in Q with the minimum shortest value and returns
25. Dijkstra’s algorithm Example.
26. Dijkstra’s algorithm Step 0: Initialization. Priority Queue.
27. Dijkstra’s algorithm Step 1: As Adjacent[s]={a,b}, work on a and b and update information. Priority Queue:
28. Dijkstra’s algorithm Step 2: After Step 1, a has the minimum key in the priority queue.
29. Dijkstra’s algorithm Step 3: After Step 2, b has the minimum key in the priority queue.
30. Dijkstra’s algorithm Step 4: After Step 3, c has the minimum key in the priority queue.
31. Dijkstra’s algorithm Step 5: After Step 4, d has the minimum key in the priority queue.
32. Dijkstra’s algorithm Shortest Path Tree: T=(V,A), where A={(pred[v],v)|v from V\{s}}. The array pred[v] is used to
33. Dijkstra’s algorithm
34. Dijkstra’s algorithm Simple array implementation The simplest way to implement the priority queue operations is to
35. Dijkstra’s algorithm Simple array implementation The INSERT operation is easy: just add the vertex to the
36. Dijkstra’s algorithm Simple array implementation Once we find this vertex, deleting it is easy: just move
37. Dijkstra’s algorithm Binary heap implementation A binary heap organizes data as a binary tree stored in
38. Dijkstra’s algorithm
39. Dijkstra’s algorithm Nodes with no children, such as nodes 6 through 10, are leaves. A binary
40. Dijkstra’s algorithm The node with the minimum key must always be at position 1. The children
41. Dijkstra’s algorithm Therefore, we can traverse a path from the root down to a leaf, or
43. Скачать презентацию

Слайд 2

Dijkstra’s algorithm
are given:
source vertex s;
the weight weight (u, v) of each

edge (u, v);
to calculate:
for each vertex v the shortest-path weight sp(s, v);
=> shortest[v]
the vertex preceding v;=> pred[v]

Слайд 3

Dijkstra’s algorithm

Слайд 4

Dijkstra’s algorithm
the situation at time 0
shortest[s]= 0

Слайд 5

Dijkstra’s algorithm
at time 4
shortest[y]= 4, pred[y]= s

Слайд 6

Dijkstra’s algorithm
at time 5
shortest[t]=5, pred[t]= y

Слайд 7

Dijkstra’s algorithm
at time 7
shortest[z]=7, pred[z]= y

Слайд 8

Dijkstra’s algorithm
at time 8
shortest[x]=8, pred[x]=t

Слайд 9

Dijkstra’s algorithm
Dijkstra’s algorithm works a little differently. It treats all edges

the same.
Dijkstra’s algorithm works by calling the RELAX procedure once for each edge.

Слайд 10

Слайд 11

Dijkstra’s algorithm
A set Q is a set of vertices for which

Слайд 12

Dijkstra’s algorithm
A set Q is a set of vertices for which

the final shortest and pred values are not yet known.
All vertices not in Q have their final shortest and pred values.
In the step 1 shortest[s] = 0, shortest[v] = ∞ for all other vertices, and pred[v] = NULL for all vertices.
Algorithm repeatedly finds the vertex u in set Q with the lowest shortest value, removes that vertex from Q, and relaxes all the edges leaving u.

Слайд 13

Dijkstra’s algorithm
Question 1: How does the algorithm find new paths and

do the relaxation?
Question 2: In which order does the algorithm process the vertices one by one?

Слайд 14

Dijkstra’s algorithm

Слайд 15

Dijkstra’s algorithm
Answer to Question 1: How does the algorithm find new

paths and do the relaxation?
Relaxation. If the new path from s to v
is shorter than shortest[v], then update shortest[v] to the length of this new path.
Remark: Whenever we set shortest[v] to a finite value, there exists a path of that length. Therefore
shortest[v] ≥ sp(s,v).
Note: If shortest[v]= sp(s,v), then further relaxations cannot change its value.

Слайд 16

Dijkstra’s algorithm
Remaid: The Algorithm for Relaxing an Edge.
Relax(u, v)
{
If (shortest[u] +

weight(u,v)< shortest[v])
{
shortest[v]= shortest[u] + weight(u,v);
pred[v]=u;
}
}

Слайд 17

Dijkstra’s algorithm
Idea of Dijkstra’s Algorithm: Repeated Relaxation
Dijkstra’s algorithm operates by maintaining

a subset of vertices, Q comprise V, for which we know the true distance, that is
shortest[v]= sp(s,v).

Слайд 18

Dijkstra’s algorithm
Idea of Dijkstra’s Algorithm: Repeated Relaxation
Initially Q=NULL, the empty set,

and we set shortest[s]=0 and shortest[v]=∞ for all others vertices v. One by one we select vertices from V\Q to add to Q.

Слайд 19

Dijkstra’s algorithm
Idea of Dijkstra’s Algorithm: Repeated Relaxation
The set Q can be

implemented using an array of vertex colors. Initially all vertices are white, and we set color[v]=black to indicate that v comprise Q.

Слайд 20

Dijkstra’s algorithm
The Selection in Dijkstra’s Algorithm
Recall Question 2: What is the

best order in which to process vertices, so that the estimates are guaranteed to converge to the true distances?
That is, how does the algorithm select which vertex among the vertices of V\Q?

Слайд 21

Dijkstra’s algorithm
Question 2: How does the algorithm select which vertex among

the vertices of V\Q?
Answer: We use a greedy algorithm. For each vertex in u from V\Q we have computed a distance estimate shortest[u].
The next vertex processed is always a vertex u from V\Q for which shortest[u] is minimum, that is, we take the unprocessed vertex that is closest (by our estimate) to s.

Слайд 22

Dijkstra’s algorithm
Question: How do we implement this selection of vertices efficiently?
Answer:

We store the vertices of V\Q in a priority queue, where the key value of each vertex v is shortest[v].
Note: if we implement the priority queue using a heap, we can perform the operations Insert(), Extract Min(), and Decrease Key(), each in O(logn) time.

Слайд 23

Dijkstra’s algorithm
Review of Priority Queues
A Priority Queue is a data structure

(can be implemented as a heap) which supports the following operations:
INSERT (Q; v) inserts vertex v into set Q.
(Dijkstra’s algorithm calls INSERT n times.)
…

Слайд 24

Dijkstra’s algorithm
EXTRACT-MIN (Q) removes the vertex in Q with the minimum

shortest value and returns this vertex to its caller.
(Dijkstra’s algorithm calls EXTRACT-MIN n times.)
DECREASE-KEY (Q; v) performs whatever bookkeeping is necessary in Q to record that shortest[v] was decreased by a call of RELAX. (Dijkstra’s algorithm calls DECREASE-KEY up to m times.)

Слайд 25

Dijkstra’s algorithm
Example.

Слайд 26

Dijkstra’s algorithm
Step 0: Initialization.
Priority Queue.

Слайд 27

Dijkstra’s algorithm
Step 1: As Adjacent[s]={a,b},
work on a and b and update

information.

Priority Queue:

Слайд 28

Dijkstra’s algorithm
Step 2: After Step 1, a has the minimum key

in the priority queue. As Adjacent[a]={b,c,d},
work on b,c,d and update information.

Priority Queue:

Слайд 29

Dijkstra’s algorithm
Step 3: After Step 2, b has the minimum key

in the priority queue. As Adjacent[b]={a,c},
work on a,c and update information.

Priority Queue:

Слайд 30

Dijkstra’s algorithm
Step 4: After Step 3, c has the minimum key

in the priority queue. As Adjacent[c]={d},
work on d and update information.

Priority Queue:

Слайд 31

Dijkstra’s algorithm
Step 5: After Step 4, d has the minimum key

in the priority queue. As Adjacent[d]={c},
work on c and update information.

Priority Queue: Q=0.

Слайд 32

$Dijkstra’s algorithm Shortest Path Tree: T=(V,A), where A={(pred[v],v)|v from V\{s}}. The$

Dijkstra’s algorithm
Shortest Path Tree: T=(V,A),
where A={(pred[v],v)|v from V\{s}}.
The array pred[v]

is used to build the tree.

Слайд 33

Dijkstra’s algorithm

Слайд 34

Dijkstra’s algorithm
Simple array implementation
The simplest way to implement the priority queue

operations is to store the vertices in an array with n positions.
If the priority queue at the moment contains k vertices, then they are in the first k positions of the array, in no particular order.

Слайд 35

Dijkstra’s algorithm
Simple array implementation
The INSERT operation is easy: just add the

vertex to the next unused position in the array and increment the count.
DECREASE-KEY is even easier: do nothing! Both of these operations take constant time.
The EXTRACT-MIN operation takes O(n) time, however, since we have to look at all the vertices currently in the array to find the one with the lowest shortest value.

Слайд 36

Dijkstra’s algorithm
Simple array implementation
Once we find this vertex, deleting it is

easy: just move the vertex in the last position into the position of the deleted vertex and then decrement the count.
The n EXTRACT-MIN calls take O(n2) time.
Although the calls to RELAX take O(m) time, recall that m <= n2.
With this implementation of the priority queue therefore, Dijkstra’s algorithm takes O(n2) time, with the time dominated by the time spent in EXTRACT-MIN.

Слайд 37

Dijkstra’s algorithm
Binary heap implementation
A binary heap organizes data as a binary

tree stored in an array.
A binary tree is a type of graph.
Its vertices are named nodes.
The edges are undirected.
Each node has 0, 1, or 2 nodes below it, which are its children.

Слайд 38

Dijkstra’s algorithm

Слайд 39

Dijkstra’s algorithm
Nodes with no children, such as nodes 6 through 10,

are leaves.
A binary heap is a binary tree with three additional properties.
First, the tree is completely filled on all levels, but possibly the lowest, which is filled from the left up to a point.
Second, each node contains a key, shown inside each node.
Third, the key of each node is less than or equal to the keys of its children.

Слайд 40

Dijkstra’s algorithm
The node with the minimum key must always be at

position 1. The children of the node at position i are at positions 2i and 2i + 1. Its parent is at position [i/2].
A binary heap has one other important characteristic: if it consists of n nodes, then its height – the number of edges from the root down to the farthest leaf – is only [lgn].

Слайд 41

Dijkstra’s algorithm
Therefore, we can traverse a path from the root down

to a leaf, or from a leaf up to the root, in only O(lgn) time.
So, when Dijkstra’s algorithm uses the binary-heap implementation of a priority queue, it spends O(nlgn) time inserting vertices,
O(nlgn) time in EXTRACT-MIN operations, and O(mlgn) time in DECREASE-KEY operations.

Shortest Paths

Содержание

Dijkstra’s algorithmare given:source vertex s;the weight weight (u, v) of each

Dijkstra’s algorithm

Dijkstra’s algorithmthe situation at time 0shortest[s]= 0

Dijkstra’s algorithmat time 4shortest[y]= 4, pred[y]= s

Dijkstra’s algorithmat time 5shortest[t]=5, pred[t]= y

Dijkstra’s algorithmat time 7shortest[z]=7, pred[z]= y

Dijkstra’s algorithmat time 8shortest[x]=8, pred[x]=t

Dijkstra’s algorithmDijkstra’s algorithm works a little differently. It treats all edges

Dijkstra’s algorithmA set Q is a set of vertices for which

Dijkstra’s algorithmA set Q is a set of vertices for which

Dijkstra’s algorithmQuestion 1: How does the algorithm find new paths and

Dijkstra’s algorithm

Dijkstra’s algorithmAnswer to Question 1: How does the algorithm find new

Dijkstra’s algorithmRemaid: The Algorithm for Relaxing an Edge.Relax(u, v){ If (shortest[u] +

Dijkstra’s algorithmIdea of Dijkstra’s Algorithm: Repeated RelaxationDijkstra’s algorithm operates by maintaining

Dijkstra’s algorithmIdea of Dijkstra’s Algorithm: Repeated RelaxationInitially Q=NULL, the empty set,

Dijkstra’s algorithmIdea of Dijkstra’s Algorithm: Repeated RelaxationThe set Q can be

Dijkstra’s algorithmThe Selection in Dijkstra’s AlgorithmRecall Question 2: What is the

Dijkstra’s algorithmQuestion 2: How does the algorithm select which vertex among

Dijkstra’s algorithmQuestion: How do we implement this selection of vertices efficiently?Answer:

Dijkstra’s algorithmReview of Priority QueuesA Priority Queue is a data structure

Dijkstra’s algorithmEXTRACT-MIN (Q) removes the vertex in Q with the minimum

Dijkstra’s algorithmExample.

Dijkstra’s algorithmStep 0: Initialization.Priority Queue.

Dijkstra’s algorithmStep 1: As Adjacent[s]={a,b},work on a and b and update

Dijkstra’s algorithmStep 2: After Step 1, a has the minimum key

Dijkstra’s algorithmStep 3: After Step 2, b has the minimum key

Dijkstra’s algorithmStep 4: After Step 3, c has the minimum key

Dijkstra’s algorithmStep 5: After Step 4, d has the minimum key

Dijkstra’s algorithmShortest Path Tree: T=(V,A), where A={(pred[v],v)|v from V\{s}}.The array pred[v]

Dijkstra’s algorithm

Dijkstra’s algorithmSimple array implementationThe simplest way to implement the priority queue

Dijkstra’s algorithmSimple array implementationThe INSERT operation is easy: just add the

Dijkstra’s algorithmSimple array implementationOnce we find this vertex, deleting it is

Dijkstra’s algorithmBinary heap implementationA binary heap organizes data as a binary

Dijkstra’s algorithm

Dijkstra’s algorithmNodes with no children, such as nodes 6 through 10,

Dijkstra’s algorithmThe node with the minimum key must always be at

Dijkstra’s algorithmTherefore, we can traverse a path from the root down

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

Dijkstra’s algorithm
are given:
source vertex s;
the weight weight (u, v) of each

Dijkstra’s algorithm
the situation at time 0
shortest[s]= 0

Dijkstra’s algorithm
at time 4
shortest[y]= 4, pred[y]= s

Dijkstra’s algorithm
at time 5
shortest[t]=5, pred[t]= y

Dijkstra’s algorithm
at time 7
shortest[z]=7, pred[z]= y

Dijkstra’s algorithm
at time 8
shortest[x]=8, pred[x]=t

Dijkstra’s algorithm
Dijkstra’s algorithm works a little differently. It treats all edges

Dijkstra’s algorithm
A set Q is a set of vertices for which

Dijkstra’s algorithm
A set Q is a set of vertices for which

Dijkstra’s algorithm
Question 1: How does the algorithm find new paths and

Dijkstra’s algorithm
Answer to Question 1: How does the algorithm find new

Dijkstra’s algorithm
Remaid: The Algorithm for Relaxing an Edge.
Relax(u, v)
{
If (shortest[u] +

Dijkstra’s algorithm
Idea of Dijkstra’s Algorithm: Repeated Relaxation
Dijkstra’s algorithm operates by maintaining

Dijkstra’s algorithm
Idea of Dijkstra’s Algorithm: Repeated Relaxation
Initially Q=NULL, the empty set,

Dijkstra’s algorithm
Idea of Dijkstra’s Algorithm: Repeated Relaxation
The set Q can be

Dijkstra’s algorithm
The Selection in Dijkstra’s Algorithm
Recall Question 2: What is the

Dijkstra’s algorithm
Question 2: How does the algorithm select which vertex among

Dijkstra’s algorithm
Question: How do we implement this selection of vertices efficiently?
Answer:

Dijkstra’s algorithm
Review of Priority Queues
A Priority Queue is a data structure

Dijkstra’s algorithm
EXTRACT-MIN (Q) removes the vertex in Q with the minimum

Dijkstra’s algorithm
Example.

Dijkstra’s algorithm
Step 0: Initialization.
Priority Queue.

Dijkstra’s algorithm
Step 1: As Adjacent[s]={a,b},
work on a and b and update

Dijkstra’s algorithm
Step 2: After Step 1, a has the minimum key

Dijkstra’s algorithm
Step 3: After Step 2, b has the minimum key

Dijkstra’s algorithm
Step 4: After Step 3, c has the minimum key

Dijkstra’s algorithm
Step 5: After Step 4, d has the minimum key

Dijkstra’s algorithm
Shortest Path Tree: T=(V,A),
where A={(pred[v],v)|v from V\{s}}.
The array pred[v]

Dijkstra’s algorithm
Simple array implementation
The simplest way to implement the priority queue

Dijkstra’s algorithm
Simple array implementation
The INSERT operation is easy: just add the

Dijkstra’s algorithm
Simple array implementation
Once we find this vertex, deleting it is

Dijkstra’s algorithm
Binary heap implementation
A binary heap organizes data as a binary

Dijkstra’s algorithm
Nodes with no children, such as nodes 6 through 10,

Dijkstra’s algorithm
The node with the minimum key must always be at

Dijkstra’s algorithm
Therefore, we can traverse a path from the root down