3. Consider the following network of computers:

E

3

The numbers labelling each edge indicate the number of Macquariecoin it costs to send a message

along that network connection. We wish to minimise the costs of sending messages by finding paths of

minimal length in this weighted graph.

Use Dijkstra's algorithm to construct a shortest-path spanning tree rooted at computer C. In your an-

swer, you should:

(a) [3 marks]. Draw the graph and illustrate the spanning tree you construct within it.

(b) [5 marks]. Show your working by displaying, at each step of execution, the contents of the fringe

list, clearly identifying the edge which will be added to the tree next.

(c) [3 marks]. List the length of each shortest path starting from the chosen root computer C to each

of the other computers in the network.