CIS-3050 Homework #13: Bellman-Ford

Due: Wednesday, December 7, 2016

The attached archive file, Graph.zip, contains skeletal code for graphs. The archive should be unzipped in the ADS folder of your samples solution. You will need to add Graph.h and Graph.cpp to your Visual Studio project. When you are done everthing should continue to build properly.

For this assignment you are to finish the functions in Graph.cpp. In particular, write the bellman_ford function that finds the single-source shortest path through a weighted, directed graph. The Wikipedia page on Bellman-Ford provides an outline of the algorithm, but you'll have to adapt what it says there to the code framework you are working with.

You should also implement the print_path_to function to output a path to the specified destination vertex. You can start by printing the path in reverse, but ideally the function would print the path in the forward direction.

To test your code, use the following main program (perhaps create a new project for it):

#include <stdio.h>
#include <string.h>
#include "Graph.h"

int main( )
{
    Graph g;
    int destination_vertex = 1;

    Graph_construct( &g );
    read_graph( &g, "graph.txt" );
    bellman_ford( &g, 0 );
    print_path_to( &g, destination_vertex );
    Graph_destroy( &g );

    return 0;
}
    

The file graph.txt included in the archive contains a sample graph in a format that read_graph can understand. Feel free to create larger, more interesting graphs to exercise your code.

Submit your modified file Graph.cpp only (put your name in comments). Don't submit the entire project or solution!


Last Revised: 2016-11-20
© Copyright 2016 by Peter C. Chapin <PChapin@vtc.vsc.edu>