[A+DS] <<<prac 5<<<

CSE2304, Final Prac' 6, week 12 and 13, 24 May - 4 June 1999

Your program must first satisfy the basic requirement of [prac' 5]:
Read in a graph from a named file specified by a command-line parameter.

(or see prac 5 [sample solution] after 00.01 hrs 22 May.)

This prac


Repeatedly until end-of-input (ctrl-D), read two vertices, v1 and v2, from standard-input (stdin) and then either print the minimum distance from v1 to v2 in the graph and print the path, or print ``no path'', as appropriate.

Use [Dijkstra's] single-source shortest-paths algorithm. Implemented on an adjacency-matrix...

[6 marks, or...]

For more marks: Instead modify the algorithm to operate on sparse graphs by using a priority-queue, implemented by a heap, to find the ``closest vertex in V-done to the source'' in the algorithm's central loop.

[8 marks]


Repeatedly until end-of-input (ctrl-D), read a vertex from standard-input (stdin) and perform a depth-first traversal of the graph, printing the vertices as they are encountered during the traversal. Also print the distance of each vertex from the starting vertex along the current path in the traversal.

[6 marks]

Optional: Implement a back-tracking traversal (i.e. it may revisit vertices, but not in the one path) to find the minimum distance between two vertices v1 and v2 (read from stdin).
What is its worst-case time-complexity? Give example graphs that cause this behaviour.

[+2 marks]

L.Allison, Comp. Sci. and S.W.E., Monash University, Australia.