Trace Dijkstra's algorithm (shortest path in weighted graphs) by specifying the values in auxiliary data structures.
Exercise Find the weighted shortest path from vertex 3 to vertex 5 in the digraph (directed graph) below.
The following parts will guide you through the process.
Fill out the table below with each vertex and its corresponding outgoing vertices.
Vertex
Outgoing
0
1
2
3
4
5
Solution
Vertex
Outgoing
0
1, 2, 4, 5
1
4, 5
2
3, 4
3
2
4
0, 1, 5
5
none
Start with the following default values in Table 1 below (fill out the answers from part-1 in the "Outgoing" column). How would these values change after exploring vertex 3? Next, fill out Table 2 with your response. What is now the unexplored vertex with the smallest distance from vertex 3?
Table 1: Default values
Vertex
Outgoing
Distance from 3
Previous
Explored
0
INFINITY
null
no
1
INFINITY
null
no
2
INFINITY
null
no
3
INFINITY
null
no
4
INFINITY
null
no
5
INFINITY
null
no
Table 2: After exploring vertex 3
Vertex
Outgoing
Distance from 3
Previous
Explored
0
1
2
3
4
5
Solution
Unexplored vertex with the smallest distance: 2
Table 1: Default values
Vertex
Outgoing
Distance from 3
Previous
Explored
0
1, 2, 4, 5
INFINITY
null
no
1
4, 5
INFINITY
null
no
2
3, 4
INFINITY
null
no
3
2
INFINITY
null
no
4
0, 1, 5
INFINITY
null
no
5
none
INFINITY
null
no
Table 2: After exploring vertex 3
Vertex
Outgoing
Distance from 3
Previous
Explored
0
1, 2, 4, 5
INFINITY
null
no
1
4, 5
INFINITY
null
no
2
3, 4
10
3
no
3
2
0
null
yes
4
0, 1, 5
INFINITY
null
no
5
none
INFINITY
null
no
How would these values change after exploring vertex 2? Fill out Table 3 with your response. What is now the unexplored vertex with the smallest distance from vertex 3?
Table 3: After exploring vertex 2
Vertex
Outgoing
Distance from 3
Previous
Explored
0
1
2
3
4
5
Solution
Unexplored vertex with the smallest distance: 4
Table 3: After exploring vertex 2
Vertex
Outgoing
Distance from 3
Previous
Explored
0
1, 2, 4, 5
INFINITY
null
no
1
4, 5
INFINITY
null
no
2
3, 4
10
3
yes
3
2
0
null
yes
4
0, 1, 5
22
2
no
5
none
INFINITY
null
no
How would these values change after exploring vertex 4? Fill out Table 4 with your response. What is now the unexplored vertex with the smallest distance from vertex 3?
Table 4: After exploring vertex 4
Vertex
Outgoing
Distance from 3
Previous
Explored
0
1
2
3
4
5
Solution
Unexplored vertex with the smallest distance: 0
Table 4: After exploring vertex 4
Vertex
Outgoing
Distance from 3
Previous
Explored
0
1, 2, 4, 5
34
4
no
1
4, 5
52
4
no
2
3, 4
10
3
yes
3
2
0
null
yes
4
0, 1, 5
22
2
yes
5
none
50
4
no
How would these values change after exploring vertex 0? Fill out Table 5 with your response. What is now the unexplored vertex with the smallest distance from vertex 3?
Table 5: After exploring vertex 0
Vertex
Outgoing
Distance from 3
Previous
Explored
0
1
2
3
4
5
Solution
Unexplored vertex with the smallest distance: 1
Table 5: After exploring vertex 0
Vertex
Outgoing
Distance from 3
Previous
Explored
0
1, 2, 4, 5
34
4
yes
1
4, 5
44
0
no
2
3, 4
10
3
yes
3
2
0
null
yes
4
0, 1, 5
22
2
yes
5
none
49
0
no
How would these values change after exploring vertex 1? Fill out Table 6 with your response. What is now the unexplored vertex with the smallest distance from vertex 3?
Table 6: After exploring vertex 1
Vertex
Outgoing
Distance from 3
Previous
Explored
0
1
2
3
4
5
Solution
Unexplored vertex with the smallest distance: 5
Table 6: After exploring vertex 1
Vertex
Outgoing
Distance from 3
Previous
Explored
0
1, 2, 4, 5
34
4
yes
1
4, 5
44
0
yes
2
3, 4
10
3
yes
3
2
0
null
yes
4
0, 1, 5
22
2
yes
5
none
49
0
no
How would these values change after exploring vertex 5? Fill out Table 7 with your response.
Table 7: After exploring vertex 5
Vertex
Outgoing
Distance from 3
Previous
Explored
0
1
2
3
4
5
Solution
Table 7: After exploring vertex 5
Vertex
Outgoing
Distance from 3
Previous
Explored
0
1, 2, 4, 5
34
4
yes
1
4, 5
44
0
yes
2
3, 4
10
3
yes
3
2
0
null
yes
4
0, 1, 5
22
2
yes
5
none
49
0
yes
What is the weighted shortest path from vertex 3 to 5? What is the total distance of this path?
Solution
The weighted shortest path from vertex 3 to vertex 5 is:
