Dijkstra’s Algorithm

This graph class uses Dijkstra’s algorithm to find and display the lowest cost paths from every vertex to every other vertex. Vertices and their connecting edges are stored in an adjacency list using a static array of vertex nodes where each vertex node contains pointers to an edge linked list and GraphData information containing the vertex name. Running the findShortestPath() function will populate a 2D static array containing path information constructed using Dijkstra’s algorithm.

Features:

  • Uses an adjacency list to store edges.
  • A copy constructor allows for deep copy duplication of a graph.
  • Includes the following public methods: buildGraph(ifstream &), insertEdge(int, int, int), removeEdge(int, int), findShortestPath(), displayAll(), display(int, int).
  • insertEdge will replace any previous edge that existed between the two vertices.
  • Path information is only updated when findShortestPath() is called.

View code on GitHub

Advertisements