Assignment VI

Due date April 22

1. From text: R-7.11. Explain in a few words the graphical conventions used in fig. 7.3 and 7.4. This will be helpful (probably) for next question.

2. From text: R-7.2. modify Dijkstra's algorithm (using the pseudocode of your choice) so that the output is a tree whose root is the source, such that a path from the source to any leaf is the shortest path to that leaf. If you prefer, you can output each path as a sequence of edges, whenever you include a new node in the Known set.

3. From text: C7.3. This is a possible modification of Dijkstra's algorithm. Does it work? If so, explain how it works. If not, give a counterexample i.e. a graph on which it fails.