Clicker Questions - 18-Dijkstra
Below is an adjacency matrix for a weighted, undirected graph.
A B C D E F G H I J
A - - 5 - - - 4 9 3 4
B - - - - - - 5 - - 5
C 5 - - - - - 5 - - 5
D - - - - - - 7 - - -
E - - - - - 2 - - 5 -
F - - 1 - 2 - 1 8 - 5
G 4 5 - 7 - 1 - - - -
H 9 - - - - 8 - - 4 -
I 3 - - - 5 - - 4 - -
J 4 5 - - - 5 - - - -
Question 1: After one pass of Dijkstra’s algorithm starting with node A, give me the order of the nodes on the multimap, as a single string (if there are multiple possible answers, just give me one of them).
Answer
These are simply the nodes connected to A, ordered by their distance to A. The multimap will be:[3,I] [4,G] -- The order of G and J may be reversed. [4,J] [5,C] [9,H]Thus, the answer is IGJCHJ or IJGCH.
Question 2: After the second pass of Dijkstra’s algorithm starting with node A, give me the order of the nodes on the multimap, as a single string (if there are multiple possible answers, just give me one of them).
Answer
Now, we remove Node I from the multimap, and process it. That adds Node E with a distance of 8, and replaces Node H, because it has a shorter distance of 7. The multimap is now:[4,G] -- The order of G and J may be reversed. [4,J] [5,C] [7,H] [8,E]Thus, the answer is CJCHE or JGCHE.