Homework SourseWrite CC a program that inputs a weighted undirected graph a
Write C/C++ a program that inputs a weighted undirected graph and finds the shortest path between two vertices using Dijkstra’s algorithm, using indices to order the branching. The program should take three command-line arguments: the name of the graph file, followed by a source vertex, followed by a destination vertex. It should output to standard output the vertices in a shortest path in order, including both the source and destination vertices, as well as the total weight of the path. You may assume that any input graphs will have no negative-weight edges. A user should see something very similar to the following when invoking your program.
> ./dijkstra graph.txt 2 3
2 5 6 1 0 3
3.51
>
Graph.txt:
7 9 //Represents number of vertices and edges, respectively.
Solution
main.cpp
#include \"Dij.h\"
#include <iostream>
/*---------------------------------------------------------
* Name: main
* Purpose: driver module for testing Dij.h
* Param: filename, source vertex id, destination vertex id
*---------------------------------------------------------*/
int main(int argc, char **argv)
{
string filename;
if ( 1 < argc ) filename.assign( argv[1] );
Graph testGraph; // create Graph object
//string filename = argv[1]; // get filename
testGraph.createGraph(filename); // populate Graph
int source; // source index
int destination; // destination index
// convert strings to integers
stringstream s1(argv[2]);
s1 >> source;
stringstream s2(argv[3]);
s2 >> destination;
// find the shortest path
testGraph.findPath(source,destination);
// print the shortest path
testGraph.outputPath();
std::cout << std::endl;
}
Dij.h
#include <iostream>
#include <vector>
#include <string>
#include <fstream>
#include <sstream>
#include <map>
#include <stack>
#include <algorithm>
#include <float.h>
#include <iomanip>
#include \"Vertex.h\"
#define infinity DBL_MAX
using namespace std;
/*-----------------------------------------------------------
* Name: Graph
* Purpose: Represent a graph G{V,E} alongside implementation
* of Dijkstra\'s algorithm
*-----------------------------------------------------------*/
class Graph
{
public:
Graph();
~Graph();
void createGraph(std::string);
void findPath(int, int);
void outputPath();
void relaxVertex(Vertex*);
// set the vertex of which the shortest path is being found
void setDestination(Vertex* destination){mDestination = destination;}
// get the vertex of which the shortest path is being found
Vertex* getDestination(){return mDestination;}
// set the vertex that is the starting point of the search
void setSource(Vertex* source){mSource = source;}
// get the vertex that is the starting point of the search
Vertex* getSource(){return mSource;}
private:
std::vector<Vertex*> mVertices; //vector of vertices
std::map<int, Vertex*> mWeights; //table of shortest path weights
Vertex* mDestination; //destination vertex
Vertex* mSource; //source vertex
};
/*---------------------------------------------------------
* Name: Default Constructor
*---------------------------------------------------------*/
Graph::Graph()
{
mDestination = NULL;
mSource = NULL;
}
/*---------------------------------------------------------
* Name: Destructor
*---------------------------------------------------------*/
Graph::~Graph()
{
//Free memory
if(!mVertices.empty())
{
while(mVertices.size())
{
Vertex * vertex = mVertices.back();
delete vertex;
mVertices.pop_back();
}
}
}
/*----------------------------------------------------------
* Name: createGraph
* Purpose: parse text file and construct graph
* Param: string - name of file to parse
*----------------------------------------------------------*/
void Graph::createGraph(std::string filename)
{
std::ifstream myfile; // ifstream object for opening file
myfile.open(filename.c_str(), ios::in); // open file
// if file does not exist or failed to open, return
if(!myfile.is_open())
{
cout << \"File failed to open\" << endl;
return;
}
// get lines from file for parsing
for(std::string line; std::getline(myfile, line);)
{
std::istringstream ss(line);
int index, value; //first node and node pointed at
double weight; //edge weight betweeen first and second nodes
// Get values from stream
ss >> index;
ss >> value;
ss >> weight;
// Add vertex to vertices list if not present
if(!mWeights.count(index))
{
Vertex * vertex = new Vertex(index);
vertex->addEdge(value, weight);
mVertices.push_back(vertex);
mWeights[index] = vertex; //record vertex in weight map
vertex->setWeight(infinity); //intialize weight to infinity
}
// Otherwise the vertice is present - add another edge
else
{
(mWeights[index])->addEdge(value, weight);
}
// If vertex has no edges, add to graph
if(!mWeights.count(value))
{
Vertex * vertex = new Vertex(value);
mVertices.push_back(vertex);
mWeights[value] = vertex; //record vertex in weight map
vertex->setWeight(infinity); //initialize weight to infinity
}
}
// close the file
myfile.close();
}
/*------------------------------------------------------------
* Name: findPath
* Purpose: Implements Dijkstra\'s algorithm with minHeap
* Param: ID of source and destination vertices
*------------------------------------------------------------*/
void Graph::findPath(int source, int destination)
{
// lambda functor for comparing vertices
auto compare = [](Vertex*lhs,Vertex*rhs)
{
return lhs->getWeight() > rhs->getWeight();
};
// index to minimum weight vertex
int index = 0;
// if the source of destination does not exist, there is no path
if(mWeights.count(source) && mWeights.count(destination))
{
// initialize source vertex to weight of zero
(mWeights[source])->setWeight(0);
// heapify
std::make_heap(mVertices.begin(), mVertices.end(), compare);
// set source node
this->setSource(mWeights[source]);
// search the graph and update shortest paths
while(index+1 != mVertices.size())
{
Vertex * vertex = mVertices[index]; //vertex of min weight with edges to search
// shortest path found if it has correct id and has been updated
if(vertex->getId() == destination && vertex->getWeight() != infinity)
{
this->setDestination(vertex); //set the destination node
break;
}
// shortest path has not been found, relax edges
else
{
this->relaxVertex(vertex);
}
//Heapify everything apart from extracted value
index+=1;
std::make_heap(mVertices.begin() + index, mVertices.end(), compare);
}
}
}
/*--------------------------------------------------------------
* Name: relaxVertex
* Purpose: update total path weight of a vertex in the graph
* Param: vertex whose edges are being searched
*-------------------------------------------------------------*/
void Graph::relaxVertex(Vertex* vertex)
{
std::map<int, double>* edges = vertex->getEdges();
// search edges of current min vertex
for(auto iter = edges->begin(); iter != edges->end(); iter++)
{
// if the edges have not been seen, update weight
if((mWeights[iter->first])->getWeight() == infinity)
{
// weight is updated to current path weight + edge weight
(mWeights[iter->first])->setWeight((mWeights[vertex->getId()])->getWeight() +
iter->second);
(mWeights[iter->first])->setParent(vertex);
}
// if the vertex has been updated already, compare current path
// if new path is now minimal, update path
else if((mWeights[iter->first])->getWeight() > iter->second +
(mWeights[vertex->getId()])->getWeight())
{
(mWeights[iter->first])->setWeight((mWeights[vertex->getId()])->getWeight() +
iter->second);
(mWeights[iter->first])->setParent(vertex);
}
}
}
/*-----------------------------------------------------------------
* Name: outputPath
* Purpose: output shortest path for destination node
*-----------------------------------------------------------------*/
void Graph::outputPath()
{
Vertex* vertex = this->getDestination(); // destination node
// if the node has a shortest path, output it
if(vertex != NULL)
{
// if id and vertex are the same, output zero weight
if(vertex->getId() == this->getSource()->getId())
{
std::cout << vertex->getId() << \"->\" << vertex->getId() << \" \";
}
// create stack using parent vertices
else
{
std::stack<int> path;
while(vertex != this->getSource())
{
path.push(vertex->getId());
vertex = vertex->getParent();
}
if(vertex == this->getSource())
{
path.push(vertex->getId());
}
// pop elements from stack and print
while(path.size())
{
int id = path.top();
path.pop();
if(id == this->getDestination()->getId())
{
std::cout << id << \" \";
}
else
{
std::cout << id << \"->\";
}
}
}
// print out weight to two degrees of precision
double weight = (mWeights[this->getDestination()->getId()])->getWeight();
std::cout << std::fixed << std::setprecision(2) << weight << std::endl;
}
else
{
std::cout << \"NO PATH FOUND\" << std::endl;
}
}
Vertex.h
/*-----------------------------------------------------------
* Name: Vertex
* Purpose: Represent vertex in a graph
*-----------------------------------------------------------*/
class Vertex
{
public:
// default constructor
Vertex(){mParent = NULL;}
// constructor with defined id
Vertex(int id){mId = id; mParent = NULL;}
~Vertex(){}
// set the vertex id
void setId(int id){mId = id;}
// get the vertex id
int getId() const {return mId;}
// set the total current path weight for a vertex
void setWeight(double weight){mWeight = weight;}
// get the total current path weight for a vertex
double getWeight()const{return mWeight;}
// set a vertex that points to the current vertex
void setParent(Vertex* parent){mParent = parent;}
//get the vertex that points at the current vertex
Vertex* getParent(){return mParent;}
// add an edge to the current vertex
void addEdge(int, double);
// return the map of edges that the current vertex contains
std::map<int, double>* getEdges(){return &mEdges;}
private:
int mId; //unique id of vertex
double mWeight; //current path weight of vertex
std::map<int, double> mEdges; //edges from current vertex
Vertex* mParent; //parent vertex
};
/*--------------------------------------------------------
* Name: addEdge
* Purpose: add edge to list of edges to given vertex
*-------------------------------------------------------*/
void Vertex::addEdge(int index, double weight)
{
mEdges.insert(std::make_pair(index,weight));
}
graph.txt
0 3 1
0 1 .51
5 0 3.0
2 5 0.2
5 6 0.8
1 6 1.0
2 4 1.30
4 3 3
3 1 3
