Shortest Path Algorithm

Design and implement a Graph class using one of the frameworks discussed in class. Your graph must be able to load in files: graph1.txt, graph2.txt, and graph3.txt and represent the graphs contained within them. The files give you first a list of all nodes in the graph, one node per line, an empty line, then the list of edges. Each edge is represented as A B X, where A and B are the nodes, and X is the weight attached to them. The graphs that are being passed in are UNDIRECTED (that is, if you have and edge (A, B), you have the edge (B, A) as well. Your graph representation must be able to do the following:

  • Insert new nodes and edges into the graph, and account for the undirected nature of the graph.
  • Determine if the graph is connected.
  • Given a node that is in the graph, output the shortest path to all other nodes in the graph (if one exists). (Prompt the user for input, determine if the node is in the graph, and then print out the shortest path to every other node in the graph).
Academic Honesty!
It is not our intention to break the school's academic policy. Posted solutions are meant to be used as a reference and should not be submitted as is. We are not held liable for any misuse of the solutions. Please see the frequently asked questions page for further questions and inquiries.
Kindly complete the form. Please provide a valid email address and we will get back to you within 24 hours. Payment is through PayPal, Buy me a Coffee or Cryptocurrency. We are a nonprofit organization however we need funds to keep this organization operating and to be able to complete our research and development projects.