CS 302 UNLV Bellman Ford Algorithm Programming Assignment

CS 302 Programming Project.

Using the Bellman-Ford Algorithm to Solve the Single Source Shortest Path Problem

Updated Wed Feb 28 06:36:53 PST 2018

You will solve the single source shortest path problem for a directed weighted graph using the Bellman-Ford Algorithm.
- Read a directed weighted graph G from an input file.
- Here is a small graph.
- The first line of the file contains n, the number of vertices of G. The names of the vertices are the integers from 1 to n. (Yes, I know you would rather it be 0 to n-1. But you need to be able to handle that.)
- Each remaining line of the graph is a list of integers separated by spaces, and represents the list of outneighbors of one vertex.
- The first number in the line is the name of the vertex.
- After that, there is a sequence of pairs, consisting of a vertex name and a weight.
- These lines are not in order. That should not bother you.
- For example, the third line of the file,
  8 5 3 7 3 4 -2
  indicates that there is an edge from 8 to 5 of weight 3, an edge from 8 to 7 of weight 3, an edge from 8 to 4 of weight -2, and no other edges from 8.
- The source will be vertex 1.
- You are to print a shortest path from the source to each other vertex.
- Possible output if the input is the small graph.
- Your program should detect whether there is a negative cycle. If so, do not write any paths, but simply an error message.
- There will be no more than 1000 vertices in the graph.
- The graph will be sparse.
- Here is a graph with a negative cycle.
- Here is a larger graph.
Write all your own code. Do not use "off the shelf" code from any source. However, you may look at available code to get ideas. Be sure not to just copy it, however.
Here are some additional graphs to test your program on.
4 vertices
10 vertices
10 vertices
My program, run again on the small graph, but showing the arrays at each iteration of the main loop.
After t iterations of the main loop, all paths of length at most t have been considered. However, note that one path of length 3 has been chosen after only two steps.
My program, run again on the small graph, but showing the arrays at each iteration of the main loop. But, this time, I relaxed the edges in a different order. Note that the final result is the same.