Modern C++ implementation of Djkstra's algorithm. Runs in O(Elog(V)), supports negative weights, but not negative weight cycles.

djikstra.cpp

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <utility>
#include <limits>
#include <functional>

using namespace std;

#define START_VERTEX        2
#define DESTINATION_VERTEX  4

using ii = pair<int, int>;
using AdjacencyList = vector<vector<ii>>;

/**
    \brief Performs Djikstra's algorithm on a graph. Runtime is O(Elog(V)).

    \param graph The graph stored as an adjacency list.
    \param source The starting vertex.

    \return a vector containing the parent to a node as
            determined by the algorithm. Use print_path()
            to view the shortest path.
*/
vector<int> djikstra(const AdjacencyList& graph, int source)
{
    // state holds the least cost paved to the node at the index
    vector<int> state(graph.size(), 1'000'000'000);
    state[source] = 0;
    // pq holds <weight, id> so that the least costly traversal is at the top
    priority_queue<ii, vector<ii>, greater<ii> > pq;
    pq.push(make_pair(0, source));
    // used to reconstruct path
    vector<int> parent(graph.size());

    while(!pq.empty())
    {
        auto ii = pq.top();
        pq.pop();
        int currentWeight = ii.first;
        int id = ii.second;

        // check if another, shorter path was already found for vertex id
        if(currentWeight > state[id])
            continue;

        for(const auto& neighbor : graph[id])
        {
            // recall that neighbor is a <id, weight>
            if(state[id] + neighbor.second < state[neighbor.first])
            {
                state[neighbor.first] = state[id] + neighbor.second;
                parent[neighbor.first] = id;
                pq.push(make_pair(state[neighbor.first], neighbor.first));
            }
        }
    }

    return parent;
}

/**
    \brief Prints the shortest path from the start vertex to
           the end vertex to standard output.

    NOTE: changing the starting vertex requires running djikstra()
          again.
*/
void print_path(vector<int> parents, int start, int end)
{
    int current = end;
    stack<int> path;
    while(current != start)
    {
        path.push(current);
        current = parents[current];
    }
    path.push(start);
    // pop the stack
    while(!path.empty())
        cout << path.top() << endl, path.pop();
}

int main()
{
    // Graph[0] represents all of the adjacent vertices to vertex 0.
    // Each ii() here is a pair of (vertex id, edge weight)
    AdjacencyList graph = {
                            { ii(4, 1) },
                            { ii(3, 3), ii(4, 6) },
                            { ii(1, 2), ii(3, 7), ii(0, 6) },
                            { ii(4, 5) },
                            { }
                          };

    vector<int> parents = djikstra(graph, START_VERTEX); // start at vertex 2

    cout << "Shortest path to vertex "
         << DESTINATION_VERTEX
         << " starting from vertex "
         << START_VERTEX << ":" << endl;

         print_path(parents, START_VERTEX, DESTINATION_VERTEX);
}