Dijkstra’s Algorithm

Dijkstra’s algorithm works on the principle that the shortest possible path from the source has to come from one of the shortest paths already discovered. A way to think about this is the “explorer” model–starting from the source, we can send out explorers each travelling at a constant speed and crossing each edge in time proportional to the weight of the edge being traversed. Whenever an explorer reaches a vertex, it checks to see if it was the first visitor to that vertex: if so, it marks down the path it took to get to that vertex. This explorer must have taken the shortest path possible to reach the vertex. Then it sends out explorers along each edge connecting the vertex to its neighbors.

It is useful for each vertex of the graph to store a “prev” pointer that stores the vertice from which the “explorer” came from. This is the vertex that directly precedes the current vertex on the path from the source to the current vertex.

Algorithm:

function Dijkstra(Graph, source):
    dist[source] := 0                     // Initializations
    for each vertex v in Graph:           
        if vsource
            dist[v] := infinity           // Unknown distance from source to v
            previous[v] := undefined      // Predecessor of v
        end if
        Q.add_with_priority(v,dist[v])
    end for 

    while Q is not empty:                 // The main loop
        u := Q.extract_min()              // Remove and return best vertex
        mark u as scanned
        for each neighbor v of u:
            if v is not yet scanned:
                alt = dist[u] + length(u, v) 
                if alt < dist[v]
                    dist[v] := alt
                    previous[v] := u
                    Q.decrease_priority(v,alt)
                end if
            end if
        end for
    end while
    return previous[]

Implementation

Data like min-distance, previous node, neighbors, are kept in separate data structures instead of part of the vertex. We number the vertexes starting from 0, and represent the graph using an adjacency list (vector whose i’th element is the vector of neighbors that vertex i has edges to) for simplicity.

For the priority queue of vertexes, we use a self-balancing binary search tree (set), which should bound time complexity by O(E log V). Although C++ has heaps, without knowing the index of an element it would take linear time to find it to re-order it for a changed weight. It is not easy to keep the index of vertexes in the heap because the heap operations are opaque without callbacks. On the other hand, using a self-balancing binary search tree is efficient because it has the same log(n) complexity for insertion and removal of the head element as a binary heap. In addition, a self-balancing binary search tree also allows us to find and remove any other element in log(n) time, allowing us to perform the decrease-key step in logarithmic time by removing and re-inserting.

We do not need to keep track of whether a vertex is “done” (“visited”), since re-reaching such a vertex will always fail the relaxation condition (when re-reaching a “done” vertex, the new distance will never be less than it was originally), so it will be skipped anyway.

#include <iostream>
#include <vector>
#include <string>
#include <list>
 
#include <limits> // for numeric_limits
 
#include <set>
#include <utility> // for pair
#include <algorithm>
#include <iterator>
using namespace std;
 
typedef int vertex_t;
typedef double weight_t;
 
const weight_t max_weight = numeric_limits<double>::infinity();
 
struct neighbor {
    vertex_t target;
    weight_t weight;
    neighbor(vertex_t arg_target, weight_t arg_weight)
        : target(arg_target), weight(arg_weight) { }
};
 
typedef std::vector<std::vector<neighbor> > adjacency_list_t;
 
 
void DijkstraComputePaths(vertex_t source,
                          const adjacency_list_t &adjacency_list,
                          vector<weight_t> &min_distance,
                          vector<vertex_t> &previous)
{
    int n = adjacency_list.size();
    min_distance.clear();
    min_distance.resize(n, max_weight);
    min_distance[source] = 0;
    previous.clear();
    previous.resize(n, -1);
    set<pair<weight_t, vertex_t> > vertex_queue;
    vertex_queue.insert(make_pair(min_distance[source], source));
 
    while (!vertex_queue.empty()) 
    {
        weight_t dist = vertex_queue.begin()->first;
        vertex_t u = vertex_queue.begin()->second;
        vertex_queue.erase(vertex_queue.begin());
 
        // Visit each edge exiting u
	const vector<neighbor> &neighbors = adjacency_list[u];
        for (vector<neighbor>::const_iterator neighbor_iter = neighbors.begin();
             neighbor_iter != neighbors.end();
             neighbor_iter++)
        {
            vertex_t v = neighbor_iter->target;
            weight_t weight = neighbor_iter->weight;
            weight_t distance_through_u = dist + weight;
	    if (distance_through_u < min_distance[v]) {
	        vertex_queue.erase(make_pair(min_distance[v], v));
 
	        min_distance[v] = distance_through_u;
	        previous[v] = u;
	        vertex_queue.insert(make_pair(min_distance[v], v));
 
	    }
 
        }
    }
}
 
 
list<vertex_t> DijkstraGetShortestPathTo(
    vertex_t vertex, const vector<vertex_t> &previous)
{
    list<vertex_t> path;
    for ( ; vertex != -1; vertex = previous[vertex])
        path.push_front(vertex);
    return path;
}
 
 
int main()
{
    // remember to insert edges both ways for an undirected graph
    adjacency_list_t adjacency_list(6);
    // 0 = a
    adjacency_list[0].push_back(neighbor(1, 7));
    adjacency_list[0].push_back(neighbor(2, 9));
    adjacency_list[0].push_back(neighbor(5, 14));
    // 1 = b
    adjacency_list[1].push_back(neighbor(0, 7));
    adjacency_list[1].push_back(neighbor(2, 10));
    adjacency_list[1].push_back(neighbor(3, 15));
    // 2 = c
    adjacency_list[2].push_back(neighbor(0, 9));
    adjacency_list[2].push_back(neighbor(1, 10));
    adjacency_list[2].push_back(neighbor(3, 11));
    adjacency_list[2].push_back(neighbor(5, 2));
    // 3 = d
    adjacency_list[3].push_back(neighbor(1, 15));
    adjacency_list[3].push_back(neighbor(2, 11));
    adjacency_list[3].push_back(neighbor(4, 6));
    // 4 = e
    adjacency_list[4].push_back(neighbor(3, 6));
    adjacency_list[4].push_back(neighbor(5, 9));
    // 5 = f
    adjacency_list[5].push_back(neighbor(0, 14));
    adjacency_list[5].push_back(neighbor(2, 2));
    adjacency_list[5].push_back(neighbor(4, 9));
 
    vector<weight_t> min_distance;
    vector<vertex_t> previous;
    DijkstraComputePaths(0, adjacency_list, min_distance, previous);
    cout << "Distance from 0 to 4: " << min_distance[4] << endl;
    list<vertex_t> path = DijkstraGetShortestPathTo(4, previous);
    cout << "Path : ";
    copy(path.begin(), path.end(), ostream_iterator<vertex_t>(cout, " "));
    cout << endl;
 
    return 0;
}

Limitations

One thing we haven’t looked at is the problem of finding shortest paths that must go through certain points. This is a hard problem and is reducible to the Travelling Salesman problem–what this means in practice is that it can take a very long time to solve the problem even for very small inputs.

Applications

  • Maps
  • Robot Navigation
  • Texture Mapping
  • Typesetting in TeX
  • Urban Traffic Planning
  • Optimal pipelining of VLSI chip
  • Subroutine in advanced algorithms
  • Telemarketer operator scheduling
  • Routing of telecommunication messages
  • Approximating piecewise linear functions
  • Network routing protocols (OSPF, BGP, RIP)
  • Exploiting arbitrage opportunities in currency exchange
  • Optimal truck routing through given traffic congestion pattern