CS 302 Programming Project.
Using Dijkstra's Algorithm to Solve the Single Source Shortest Path Problem
-
You will solve the single source shortest path problem for a directed
weighted graph, with no negative edges, using Dijkstra's 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.
-
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.
-
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.
-
There will be no more than 1000 vertices in the graph.
-
The graph will be sparse.
-
Here is a larger graph.
If you write Dijkstra's algorithm properly, your computer will
solve that graph in "no time."
-
If you try to solve that large graph using the Bellman-Ford algorithm,
it will take a long time.
If you try to solve it using the Floyd-Warshall algorithm,
you could starve to death waiting for it to finish.
-
Some additional graphs to test your program on:
100 vertices.
100 vertices.
-
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.
-
In lieu of my usual lecture, I created a power point presentation on
Dijkstra's algorithm.
