DijkstraPQ.cpp

#include "Graph.h"
#include "PriorityQueue.h"

void PrintPath(int start, int end, int *parents, int *distance) {
  cout << end << " (" << distance[end] << "): ";
  int a = start;
  int b = end;
  while (a != b) {
    cout << b << " -> ";
    b = parents[b];
  }
  cout << start << endl;
}

/*
 * 1. Set the distance of the starting node to 0.
 * 2. Fill a priority queue (which will provide O(1) time to lookup the minimum
 *    distance) with all vertices.
 * 3. Until the queue is empty, keep getting the element with the shortest
 *    distance.  Let this shortest distance be known as the parent node.
 * 4. Check all the adjacent nodes and see whether the distance between this
 *    adjacent node and the parent node is shorter than the currently
 *    calculated distance to the adjacent node.
 * 5. If the distance is shorter, update the distance in the priority queue.
 */
void Dijkstra(Graph &g, int source) {
  // The priority queue allows us to get the edge with the minimum distance
  // at constant time, with enqueue operations taking logarithmic time.
  PriorityQueue q;

  int successor, parent, v, weight, potentialDist;
  int n = g.vertices.size();
  int distance[n];
  int parents[n];
  fill_n(distance, n, numeric_limits<int>::max());
  fill_n(parents, n, -1);

  distance[source] = 0;
  for (int i = 0; i < g.vertexIndices.size(); i++)
    q.Insert(i, distance[i]);

  while (!q.Empty()) {
    v = q.Pop().v;
    Node *parent = g.vertices[v];

    for (int i = 0; i < parent->adjacencies.size(); i++) {
      // Get the adjacent successor vertex and weight from the parent to the
      // successor.
      successor = parent->adjacencies[i]->y;
      weight = parent->adjacencies[i]->weight;

      potentialDist = distance[v] + weight;

      // Check if the distance from the parent node to the node being currently
      // processed is shorter than the currently calculated distance to this
      // successor (adjacent to the parent) node.
      if (potentialDist < distance[successor]) {
        q.DecreaseKey(successor, potentialDist);
        distance[successor] = potentialDist;
        parents[successor] = v;
      }
    }
  }

  for (int i = 0; i < g.vertexIndices.size(); i++) {
    int w = g.vertexIndices[i];
    PrintPath(source, w, parents, distance);
  }
}

int main(int argc, char **argv) {
  Graph g(true);
  g.InsertEdge(0, 1, 6);
  g.InsertEdge(1, 4, 11);
  g.InsertEdge(0, 2, 8);
  g.InsertEdge(0, 3, 18);
  g.InsertEdge(4, 5, 3);
  g.InsertEdge(5, 2, 7);
  g.InsertEdge(5, 3, 4);
  g.InsertEdge(2, 3, 9);
  g.Print();

  cout << endl << "Running Dijkstra:" << endl;
  Dijkstra(g, 0);

  return 0;
}

PriorityQueue.cpp

#include "PriorityQueue.h"

bool PriorityQueue::Empty() {
  return heap.empty();
}

int PriorityQueue::LeftChild(int index) {
  return 2 * index + 1;
}

int PriorityQueue::RightChild(int index) {
  return 2 * index + 2;
}

int PriorityQueue::Parent(int index) {
  return (index - 1) / 2;
}

void PriorityQueue::Swap(int a, int b) {
  Data _a = heap[a];
  Data _b = heap[b];
  heap[b] = _a;
  heap[a] = _b;
  vertexToHeap[_a.v] = b;
  vertexToHeap[_b.v] = a;
}

void PriorityQueue::BubbleUp(int index) {
  if (index == 0) return; // Edge case is the root.
  int p = Parent(index);
  if (heap[p].distance > heap[index].distance) {
    Swap(p, index);
    BubbleUp(p);
  }
}

void PriorityQueue::BubbleDown(int index) {
  int n = heap.size();
  int left  = LeftChild(index);
  int right = RightChild(index);
  int min;
  if (right > n)
    if (left > n) return;
    else min = left;
  else
    min = (heap[left].distance > heap[right].distance) ? left : right;

  if (heap[index].distance > heap[min].distance) {
    Swap(index, min);
    BubbleDown(min);
  }
}

void PriorityQueue::DecreaseKey(int vertex, int newDistance) {
  int j = vertexToHeap[vertex];
  if (heap[j].distance <= newDistance) return;
  heap[j].distance = newDistance;
  BubbleUp(j);
}

void PriorityQueue::Insert(int vertex, int distance) {
  Data tmp;
  tmp.v = vertex;
  tmp.distance = distance;
  heap.push_back(tmp);
  vertexToHeap[vertex] = heap.size() - 1;
  BubbleUp(heap.size() - 1);
}

Data PriorityQueue::Front() {
  return heap[0];
}

Data PriorityQueue::Pop() {
  Data tmp = heap[0];
  heap[0] = heap[heap.size() - 1];
  heap.pop_back();
  vertexToHeap[tmp.v] = -1;
  vertexToHeap[heap[0].v] = 0;
  if (heap.size() > 0)
    BubbleDown(0);

  return tmp;
}

PriorityQueue.h

/*
 * Priority Queue implementation which allows for the decreaseKey operation (as
 * std::priority_queue does not).  For use in Dijkstra's algorithm to store a
 * vertex index as well as a distance value (thus making it unqiue from a
 * standard single value binary heap.
 */

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

struct Data {
  int v;
  int distance;
};

class PriorityQueue {
  public:
    vector<Data> heap;
    unordered_map<int, int> vertexToHeap;

    bool Empty();
    int LeftChild(int index);
    int RightChild(int index);
    int Parent(int index);

    void Swap(int a, int b);

    void BubbleUp(int index);
    void BubbleDown(int index);
    void DecreaseKey(int vertex, int newDistance);
    
    void Insert(int vertex, int distance);
    Data Front();
    Data Pop();
};