A C++ implementation of DijKstra Algorithm

DijKstra is a very useful algorithm used in graph search for finding single source shortest path. Devils are in details, here is a caninocal implementation of the algorithm in C++.

Like many graph problems, figure out the data structure and the representation of the graph is critical to the implementation of algorithm. Here we use graph’s object-pointer representation which naturally encodes both node relationships and edge weights.

To be able to reconstruct the shortest path we need to keep a vector that stores the ‘previous’ relationship for each vertice while we are figuring out the shortest path.

// [to node index, edge weight] pair.
typedef std::pair<int, int> edge;
// [node index, distance to source] pair.
typedef std::pair<int, int> element;
class compare {
public:
  bool operator()(const element&a, const element &b) {
    return a.second > b.second;
  }
};

int dijkstra(const vector<vector<edge>> &graph, int source, int target,
             vector<int> &path) {
  int size = (int)graph.size();
  if (!size) return -1;
  if (source < 0 || source >= size || target < 0 || target >= size)
    return -1;
  vector<bool> visited(size, false);
  vector<int> distance(size, INT_MAX);
  vector<int> prev(size, -1);
  path = prev;
  distance[source] = 0;

  priority_queue<element, vector<element>, compare> pq;
  pq.emplace(make_pair(source, 0));

  while (!pq.empty()) {
    int v = pq.top().first;
    pq.pop();
    if (v == target) return distance[v];

    if (visited[v]) continue;
    for (auto &edge : graph[v]) {
      int u = edge.first; // vertice u that connects to v.
      int w = edge.second; // weight of edge that connects u and v.
      if (visited[u]) continue;
      if (distance[v] + w < distance[u]) {
        distance[u] = distance[v] + w;
        pq.emplace(make_pair(u, distance[u]));
        path[u] = v;
      }
    }
    visited[v] = true;
  }

  return -1;
}

int main(int argc, const char * argv[]) {
  vector<vector<edge>> graph(7, vector<edge>());
  graph[1].push_back(make_pair(3, 9));
  graph[1].push_back(make_pair(2, 7));
  graph[1].push_back(make_pair(6, 14));
  graph[2].push_back(make_pair(1, 7));
  graph[2].push_back(make_pair(3, 10));
  graph[2].push_back(make_pair(4, 15));
  graph[3].push_back(make_pair(1, 9));
  graph[3].push_back(make_pair(6, 2));
  graph[3].push_back(make_pair(4, 11));
  graph[4].push_back(make_pair(2, 15));
  graph[4].push_back(make_pair(3, 11));
  graph[4].push_back(make_pair(5, 6));
  graph[5].push_back(make_pair(6, 9));
  graph[5].push_back(make_pair(4, 6));
  graph[6].push_back(make_pair(1, 14));
  graph[6].push_back(make_pair(3, 2));
  graph[6].push_back(make_pair(5, 9));

  vector<int> pre;
  int shortestPath = dijkstra(graph, 1, 5, pre);
  cout << "Shortest path from 1 to 5 has length of " << shortestPath << endl;

  // Construct shortest path.
  int u = 5;
  stack<int> path;
  while (pre[u] != -1) {
    path.push(u);
    u = pre[u];
  }
  path.push(u);

  while (!path.empty()) {
    cout << path.top() << " ";
    path.pop();
  }
  return 0;

}