http://www.filedropper.com/graph_1

http://www.filedropper.com/graph_2

http://www.filedropper.com/main_4

Write a c++ function to implement Dijkstra's algorithm on a graph. The graph implementation is the 3 files above.The function takes two parameters: starting vertex and destination vertex. Print the shortest path and the shortest distance from the starting vertex to the destination vertex.

void Graph::Dijkstra(string starting, string destination);

The vertex structure has been changed to include "visited", "distance" and "previous".

struct adjVertex{ vertex *v; int weight; }; 

struct vertex{ std::string name;  bool visited; int distance; vertex *previous; std::vector adj; }; 

Here is the definition of the Graph class: class Graph { public: Graph(); ~Graph(); void addEdge(std::string v1, std::string v2, int weight); void addVertex(std::string name); void displayEdges(); void Dijkstra(string sourceVertex, string destinationVertex); protected: private: std::vector vertices; }; 

Here is the main function that is used to build the tree: int main() { Graph g; g.addVertex("O"); g.addVertex("A"); g.addVertex("B"); g.addVertex("C"); g.addVertex("D"); g.addVertex("E"); g.addVertex("F"); g.addVertex("T"); //edge written to be undirected g.addEdge("O", "A", 2); g.addEdge("O", "B", 5); g.addEdge("O", "C", 4); g.addEdge("A", "B", 2); g.addEdge("A", "D", 7); g.addEdge("A", "F", 12); g.addEdge("B", "C", 1); g.addEdge("B", "D", 4); g.addEdge("B", "E", 3); g.addEdge("C", "E", 4); g.addEdge("D", "E", 1); g.addEdge("D", "T", 5); g.addEdge("E", "T", 7); g.addEdge("F", "T", 3); return 0; }