You will implement Dijkstra's shortest path algoritm to find the cost of the shortest path from a given node of a directed weighted graph to all other nodes.
The adjacency list will be implemented with an adjacency "object"
in the file adjacency.c which
contains the publically accessible functions given in
adjacency.h:
int init(int num); int addadjacency(int source, int dest, int cost); int findcost(int source, int dest); void printall(void);init will do whatever initialization is necessary for a list of num nodes. It returns true on success and false on failure.
addadjacency adds an edge from source to dest with cost cost.
findcost returns the cost of the edge from source to dest or -1 if there is no such edge.
printall prints a descriptive message on a separate line indicating the number of nodes followed by one line for each node giving the node number and all adjacent nodes with their corresponding cost.
You will use a linked adjacency list representation of the graph as discussed in class. The nodes of the graph are numbered 0 to n-1. For each node there is a linked list of adjacencies. An adjacenciy consists of two integer values, the number of the adjacent node and the cost of the corresponding edge.
Use the folowing typedefs for your lists:
typedef struct {
int node;
int cost;
} edge;
typedef struct entry {
edge e;
struct entry *next;
} entry;
typedef entry **adjacencies;
Note that these typedefs refer only to the implementation and should appear only in the file adjacency.c.
Your main program should be in the file shortest.c. The main program will read in the data and call a function (also in the same file) to perform the algorithm. The data for the graph will be read from standard input as a list of integers in free format. The first integer will be the number of nodes in the graph. This will be followed by triples of three integers: the source node, the destination node, and the weight of the corresponding arc.
Your program should start by printing a line in the form:
This program was written by ...followed by a descriptive line containing the number of nodes. As you read in the adjacencies and wieghts, print them out one per line and insert them in the adjacency object. When everything has been read in, call printall to show that they have been entered correctly.
Your program will then perform the algorithm and display the results. After initialization and after each step, display the step number, the node to be used next, the set nodes and the distances. This should be all on one line in some reasonable format. When the algorithm is complete, for each node in the graph the shortest distance should be displayed, one per line.
Here is some sample output to illustrate what your output might look like. This was run on the example from class:
This program was written by Steven Robbins The number of nodes is 8 Source:0, Destination:1 Cost:5 Source:0, Destination:4 Cost:2 Source:0, Destination:5 Cost:10 Source:1, Destination:2 Cost:15 Source:1, Destination:4 Cost:6 Source:1, Destination:6 Cost:1 Source:2, Destination:6 Cost:8 Source:2, Destination:7 Cost:6 Source:3, Destination:2 Cost:25 Source:5, Destination:2 Cost:4 Source:6, Destination:3 Cost:3 Source:7, Destination:3 Cost:1 Source:7, Destination:6 Cost:14 Showing adjacencies, number of nodes is 8 0: (1,5) (4,2) (5,10) 1: (2,15) (4,6) (6,1) 2: (6,8) (7,6) 3: (2,25) 4: 5: (2,4) 6: (3,3) 7: (3,1) (6,14) Initial arrays: 0 0 (1, 2, 3, 4, 5, 6, 7) (5,-1,-1,2,10,-1,-1) Starting Algorithm 0 4 (1, 2, 3, 5, 6, 7) (5,-1,-1,2,10,-1,-1) 1 1 (2, 3, 5, 6, 7) (5,20,-1,2,10,6,-1) 2 6 (2, 3, 5, 7) (5,20,9,2,10,6,-1) 3 3 (2, 5, 7) (5,20,9,2,10,6,-1) 4 5 (2, 7) (5,14,9,2,10,6,-1) 5 2 (7) (5,14,9,2,10,6,20) Distances to each node follows: 0: 0 1: 5 2: 14 3: 9 4: 2 5: 10 6: 6 7: 20
Your program should do error checking at each point at which an error can occur. If should print an appropriate message and exit if an error is found.
Test your program with your own input and then with the all of the 3 input files in /usr/local/courses/cs2213/fall2000/prog3/.
Print out a copy of the
cover page:
lp /usr/local/courses/cs2213/fall2000/cover3.ps
The cover page tells you what needs to be handed in.
Hand in everything in class on the due date.
Note: You must do this with a linked list implementation of the adjacencies as described with the functions in adjacency.h being the only public ones.
This assignment involves reading integers from standard input. The
simplest way to do this is with scanf.
If x is an integer variable,
scanf("%d",&x);
reads the next integer from standard input and puts the result in the
variable x.
If you want to read three integers with one statement, you can do:
scanf("%d%d%d",&x1,&x2,&x3);
scanf returns the number of items read so it you want to read
sets of three integers in a loop until an end of file, you can do:
while (scanf("%d%d%d",&x1,&x2,&x3) == 3) { ... }
Extra Credit After all of the output described above, for each node display the shortest path from node 0. This should start with a descriptive line indicating that that shortest paths will be given, followed by one path per line for each node starting with node 0. Each path will consist of a sequence of nodes starting with node 0 and ending with the given node, for example:
Shortest paths follow: 0: 0 1: 0 1 2: 0 5 2 3: 0 1 6 3 4: 0 4 5: 0 5 6: 0 1 6 7: 0 5 2 7