COP 3530 Fall 2013
Data Structures and Algorithms
Assignment 7. Due: December 4, 2013, 11:55 p.m. via Sakai
In this assignment you will implement Dijkstra’s Greedy Algorithm to find the shortest path in a given directed, weighted graph. The algorithm finds a shortest path from a given source vertex to each of the vertices (or destinations) in the graph to which there is a path.
The main points we shall be covering are:
● Weighted Graph, Dijkstra’s Greedy Algorithm, Shortest Path Problems
● Continuing use of makefiles, abstract data types in C++, and separate compilation
Shortest Path Problems
In shortest path problems, we are given a directed weighted graph. The path length is sum of weights of edges on path. The vertex at which the path begins is the source vertex. The vertex at which the path ends is the destination vertex.
Dijkstra’s Greedy Algorithm
The algorithm by Dijkstra is a greedy algorithm. In a greedy algorithm, we attempt to construct an optimal solution in stages. At each stage a decision is made that appears to be the best (using some criterion) at the time. In Dijkstra’s algorithm, the shortest path in a graph is generated in stages. In each stage a shortest path to a new destination vertex is generated.
Weighted Graph
Problem
1] Implement Dijkstra’s Greedy algorithm using the figure above as the test data. The source vertex is vertex 1. The shortest paths for this weighted graph are:
0: 1 à 1
10: 1 à 2
30: 1 à 4
45: 1à 4à 6
50: 1à 4à 3
60: 1à 4à 3à 5
Previously provided files you can use
· myException.cpp and myException.h. Same as in previous Assignments.
Files you must develop
· You may develop your own files, but create main.cpp so it uses your files. You may use any data structures you wish, but still no templates. You may hardcode the graph data.
· Makefile. Each .cpp file must compiled separately. Be sure to provide “clean” and ‘tar” targets in the make file.
Some sample output is as follows, yours need not look identical as long as it’s readable:
thunder:8% ./main
0: 1 à 1
10: 1 à 2
30: 1 à 4
45: 1à 4à 6
50: 1à 4à 3
60: 1à 4à 3à 5
• Your submission MUST run on thunder.cise.ufl.edu. That is where it will be run and graded.
The simplest syntax of the tar command is as follows.
tar cvf (tar_file_name) (file 1) (file 2) (file 3)...
To extract the contents of a tar file:
tar xvf (tar_file_name)
As before, use the Makefile to create the tarfile.
It is STRONGLY recommended you verify your submission is successful by downloading it from Sakai (into a separate directory), untarring it, and running make.