[Solved] Micro Assignment Dijkstras Algorithm

For this micro assignment, you must implement the function that executes Dijkstras shortest path algorithm inside Graph.h. The function is called dijkstra( int startingID ). Its found at the very end of the file.Ive left in a timesaver test on dijkstras that only re-runs the algorithm if its from a new starting point than you ran it last time. This comes into play when you query for paths in the graph since they first call dijkstras to make sure they have a valid data path to test.Youll find that all of the vertices have ID numbers for their names. These are integers and they match the bucket they live in inside of graph._vertices. This is a total time saver and simplifying approach that I used for this implementation. They *should* be kept in an unordered_map<string, Vertex* instead of a simple vector, but I dont have time to re-do everything this term.The graph were testing with is the same one from the book in Chapter 9 (page 394). Ive added a single node with ID #0 thats disconnected from the graph to show that you cant reach the node. Im using a library to provide a path weight of infinity and it shows up in the double type as inf.When you run make bigtest youll see it takes a while to run the Mouse Brain test. Thats a second graph in MouseBrainGraph.dot with about 216 vertices and 21k edges (give or take). It takes about 15 seconds to run with my implementation and computer. It takes about 30 seconds on ssh7.eecs.wsu.edu.

5/5 – (3 votes)