BU CAS CS 113
Introduction to Computer Science II with Intensive C

Spring 1996

Assignment 9, due Thursday April 18 at 2PM

Write a program that uses Dijkstra's algorithm to determine the shortest path from the first vertex in a di-graph to all other vertices in the graph.

As input, your program will read a graph's adjacency matrix from an input file using redirected standard input.

Here is an example input file based on the example in Standish 10.6. The first line of the file gives the number of vertices in the graph. Subsequent lines describe the graph's adjacency matrix with integer weights. Vertices with edges between them have positive weights. Vertices with no edge between them are denoted with a special negative weight: -1.

As output, your program should print the length of the shortest path between the first vertex and each other vertex in the graph. If there is no path, your program should print "Infinity" as the shortest path length. In addition to shortest path length, your program should print out the list of intermediate vertices passed through for the shortest path between the two vertices.

Here is what your program output should look like for the example input file:

Shortest path between:

(1,1) = 0, via none
(1,2) = 3, via none
(1,3) = 10, via 2
(1,4) = 7, via 6
(1,5) = 11, via 2,3
(1,6) = 5, via none

You will submit one file for this assignment: a9.c.

Your source file is to be electronically submitted by using the submit program on csa. The code you submit should conform with the program assignment guidelines.

Programming assignments are due before class on the assignment due date.

Late assignments will be levied a late penalty of 10% per day. Late assignments will only be accepted up to 4 days late.

Academic Honesty and Collaboration

It is reasonable to discuss with others possible general approaches to problems. It is unreasonable to work together on a detailed solution, to copy a solution, or to give away a solution. If your common discussion can be detected by looking at the solutions, then there is too much collaboration. Such instances of academic dishonesty will result in a course grade of F or expulsion from Boston University.

Do not allow your work to be used by others:

Warning: If someone cheats by using your work, you will also be penalized


Page Created: March 11, 1996      
Maintained by: Stan Sclaroff