CS 302 Programming Project.
Using the Floyd-Warshall Algorithm to Solve the All Pairs Shortest Path
Problem
Updated
Thu Apr 4 06:09:32 PST 2013.
-
You will solve the all pairs shortest path problem for a directed
weighted graph using the Floyd-Warshall Algorithm.
-
Read a directed weighted graph G from an input file.
-
Here is a small graph.
-
Here is a another 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.
-
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.
-
Print the output graph of the Floyd-Warshall algorithm.
-
You are to print a shortest path between each pair of vertices where
there is a path.
-
Possible output if the input is
the second 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 10 vertices in the graph.
-
The graph is not sparse.
-
Here is a larger graph.
-
Here is another larger graph.
-
Here is another 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 is an
output showing the result after each iteration of the main loop,
where the input graph is the
second small graph.
Note that in the 4th and last iteration, we get a new better path
from 3 to 1 .
This is because, for the first time, we are allowed to use
4 as an intermediate vertex for a path.
