Question: Need help? I am trying to write a program that reads a map and uses Dijkstra's algorithm to find and display the minimum distance path.

Need help?

I am trying to write a program that reads a map and uses Dijkstra's algorithm to find and display the minimum distance path.

I need the graph.cpp and graoh.h files based on the information below I have the rest.

/*
a structure for a node on the graph
Only has the name of the city
*/
struct Node {
std::string name;
};
/*
an arc represents a connection between two nodes
and stores the distance between them
The values are pointers to the nodes.
The cost is the distance between citites
*/
struct Arc {
Node *start;
Node *finish;
double cost;
};
/***
the Graph class is the set of all of the Nodes and Arcs
and the functions to manipulate them
*/
class Graph {
public:
/***
read a csv file with paths and distance between cities like:
Atlanta,Chicago,599
and create all of the Nodes and Arcs in the graph
I wrote this for you. It is in graph_base.cpp
*/
void readFromFile(const std::string &filename);
/***
* find all of the arcs that connect to a specific node
* return an empty set if there are none
*/
std::set getArcsAtNode(const Node *);
/***
* get pointer to the node with this name
* return NULL if it does not exist
*/
Node *findNodeByName(const std::string &name);
private:
// data sets of pointers to the arcs and nodes
std::set arcs_;
std::set nodes_;
/***
* add a node to the graph.
* Given the names of the start and finish cities and the distance
* between them, add the nodes and arcs to the graph.
* If either city or the arc is already in the graph, you must
* not duplicate it.
* This function is called when reading the file to create the graph.
*/
void addNode(std::string start_city, std::string end_city, double distance);
/***
* insert an arc into the graph, if it already exists then do nothing
* This should be called by the addNode() function to insert an
* arc between two cities.
*/
Arc *insertArc(Node *start, Node * end, double distance);
/***
* insert a node into the graph, if it already exists then do nothing
* This should be called from addNode() to add a city to the graph
*/
Node *insertNode(const std::string &name);
/***
* get pointer to Arc between two nodes, return NULL if it does not exist
* This is
*/
Arc *findArc(Node *start, Node *end);
/***
* stream the graph to the output.
*/
friend std::ostream &operator<<(std::ostream &, const Graph &);
};
/*
stream the graph information
*/
std::ostream &operator<<(std::ostream &, const Graph &);

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer
Step: 1 Unlock blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Databases Questions!