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

CSE2304

Repeatedly until end-of-input (ctrl-D), read two vertices, v₁ and v₂, from standard-input (stdin) and then either print the minimum distance from v₁ to v₂ 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...

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.

• Initially the priority-queue contains only those vertices that are adjacent (i.e. directly connected) to the start vertex.
• A vertex, v, in V-done and not yet in the priority-queue is added to the queue when it is adjacent to the current "closest" vertex being added to the set done.
• If v is in the priority-queue, its priority may "improve" thus promoting v in the queue/ heap when v is adjacent to "closest" vertex. Therefore the algorithm needs to be able to find the position of each vertex in the priority-queue quickly.

CSE2040

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.

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 v₁ and v₂ (read from stdin).
What is its worst-case time-complexity? Give example graphs that cause this behaviour.

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