Standard 9: Graph Traversal 3: Shortest Paths
Short description: Apply BFS and Dijkstra’s algorithm; identify complexity and failure points.
Relevant notes: Topic C: Graph Traversal.
Full description
Given a graph, simulate the execution of BFS and Dijkstra's shortest-paths algorithms. Identify the computational complexity of the algorithms and its dependence on the properties of the queue data structure. Identify failures of the algorithms when their assumptions fail.
Example problem
Given the below graph, simulate the execution of Dijkstra's algorithm starting from u. Report, at the beginning of each iteration of the while loop, the state of the priority queue and the distance table, and which vertex is popped from the queue.
Sample solution
Sample solution.
| Round | dist[u] | dist[v] | dist[w] | dist[x] | dist[y] | queue | vertex popped |
|---|---|---|---|---|---|---|---|
| 1 | 0 | $\infty$ | $\infty$ | $\infty$ | $\infty$ | u, v, w, x, y | u |
| 2 | 0 | 3 | 7 | $\infty$ | $\infty$ | v, w, x, y | v |
| 3 | 0 | 3 | 7 | 5 | $\infty$ | x, w, y | x |
| 4 | 0 | 3 | 7 | 5 | 14 | w, y | w |
| 5 | 0 | 3 | 7 | 5 | 14 | y | y |
| 6 | 0 | 3 | 7 | 5 | 14 | $\quad$ | |
Rubric
Rubric.
To pass, a solution must follow the course requirements for writing.
To pass, the solution must be clear, easy to read, and correct at each stage.
The numerical rubric for this problem is:
- 4 (Pass, Near-Perfect): correct, clear.
- 3 (Pass, Proficient): correct, possibly not well displayed or a bit harder to read. May have a slightly different convention for e.g. numbering rounds.
- 2 (Fail, Progress): may have a mistake in the algorithm execution. May give the answer in a very difficult to read or unclear format.
- 1 (Fail, Wrong Track): Does not appear to follow Dijkstra's algorithm, or a significant mistake in the algorithm.