Dijkstra shortest path

dijkstra.cpp

#include <iostream>
#include <vector>
#include <math.h>
#include <unordered_map>
#include <string>
#include <fstream>
#include <stack>
#include <unordered_set>
#include <queue>
#include <stack>
#include <limits>
using namespace std;

struct Vertex {
  Vertex(int value) : value(value), minDistance(numeric_limits<int>::max()), prev(nullptr) {}
  int value;
  int minDistance = numeric_limits<int>::max();
  Vertex* prev;
};

struct Edge {
  Vertex* start;
  Vertex* end;
  int weight;
};

class Comparator {
public:
  bool operator()(Vertex* e1, Vertex* e2) const {
    return e1->minDistance > e2->minDistance;
  }
};

void dijkstraAll(unordered_map<int, vector<Edge*>>& g, unordered_map<int, Vertex*>& vertices) {
  unordered_set<int> vis;
  vector<Vertex*> pq;

  for (auto& pair : vertices) {
    pq.push_back(pair.second);
  }

  make_heap(pq.begin(), pq.end(), Comparator());
  
  while (!pq.empty()) {
    pop_heap(pq.begin(), pq.end(), Comparator());
    Vertex* current = pq.back(); pq.pop_back();

    // Going over all neighbors of the current vertex
    for (Edge* edge : g[current->value]) {
      // Update the distance to the neighbor if it's lower than the one it has so far.
      int currentDistance = current->minDistance + edge->weight;

      if (currentDistance < edge->end->minDistance) {
        // Yes, the distance we calculated now is smaller than the one previously found. Update!
        edge->end->minDistance = currentDistance;
        edge->end->prev = current;
      }
    }

    make_heap(pq.begin(), pq.end(), Comparator());
  }
}

list<Vertex*> tracebackPath(Vertex* end) {
  list<Vertex*> path;

  Vertex* current = end;

  while (current != nullptr) {
    path.push_front(current);
    current = current->prev;
  }

  return path;
}

int main() {
  Vertex zero(0);
  Vertex one(1);
  Vertex two(2);
  Vertex three{ 3 };
  Vertex four{ 4 };
  Vertex five{ 5 };
  Vertex six{ 6 };
  Vertex seven{ 7 };
  Vertex eight{ 8 };

  unordered_map<int, Vertex*> vertices = {
    { 0, &zero },
    { 1, &one },
    { 2, &two },
    { 3, &three },
    { 4, &four },
    { 5, &five },
    { 6, &six },
    { 7, &seven },
    { 8, &eight },
  };

  unordered_map<int, vector<Edge*>> graph;

  int start, end;
  cin >> start >> end;

  // Setting the value of the starting vertex to 0 so that dijkstra starts from there.
  vertices[start]->minDistance = 0;

  graph[0].push_back(new Edge{ &zero, &one, 1 });
  graph[0].push_back(new Edge{ &zero, &two, 8 });

  graph[1].push_back(new Edge{ &one, &four, 2 });
  graph[1].push_back(new Edge{ &one, &three, 1 });

  graph[2].push_back(new Edge{ &two, &three, 2 });
  graph[2].push_back(new Edge{ &two, &six, 4 });

  graph[3].push_back(new Edge{ &three, &five, 9 });

  graph[4].push_back(new Edge{ &four, &eight, 3 });

  graph[5].push_back(new Edge{ &five, &eight, 7 });
  graph[5].push_back(new Edge{ &five, &seven, 3 });

  graph[6].push_back(new Edge{ &six, &seven, 1 });

  dijkstraAll(graph, vertices);
  
  cout << "Shortest path from start: " << start << " to " << end << " is " << vertices[end]->minDistance << endl;


  for (Vertex* v : tracebackPath(vertices[end])) {
    cout << v->value << " ";
  }
  cout << endl;
}