Interactive practice questions
In the following graph, we want to find the paths of lowest weight between the vertex $A$A and each of the other vertices. To do this, we will use Dijkstra's algorithm.
Perform the first step of the algorithm at the first working vertex, $A$A, by filling in the labels of all its adjacent vertices.
|
|||||||||
 |
|||||||||
|
|
||||||||
|
|||||||||
Perform the second step of the algorithm by choosing the next working vertex.
Vertex $A$A
Vertex $B$B
Vertex $C$C
Vertex $D$D
Perform the first step of the algorithm again at the new working vertex by updating the labels of all its adjacent vertices, where appropriate.
To update a label add a comma after the current label number, then write the new label number to form a list.
|
|||||||||
|
|||||||||
|
|
||||||||
|
|||||||||
Perform the second step of the algorithm again by choosing the next working vertex.
Vertex $A$A
Vertex $B$B
Vertex $C$C
Vertex $D$D
Perform the first step of the algorithm again at the new working vertex by updating the labels of all its adjacent vertices, where appropriate.
To update a label add a comma after the current label number, then write the new label number to form a list.
|
|||||||||
|
|||||||||
|
|
||||||||
|
|||||||||
For each vertex, enter the least weight between itself and vertex $A$A.
| $0$0 | ||||
|
||||
| $\editable{}$ | $\editable{}$ | |||
| $\editable{}$ | ||||
In the following graph, we want to find the paths of lowest weight between the vertex $A$A and each of the other vertices. To do this, we will use Dijkstra's algorithm.
In the following directed graph, we want to find the paths of lowest weight which start at vertex $A$A and end at each of the other vertices. To do this, we will use Dijkstra's algorithm.
Danielle has used Dijkstra's algorithm to help her find the paths of lowest weight between one of the vertices and each of the other vertices in the graph shown below.
By using the algorithm, Danielle has written down a list of labels next to each vertex.