Dijkstra's algorithm (C Plus Plus)

From LiteratePrograms
Jump to: navigation, search
Other implementations: C++ | Inform 7 | Java

Dijkstra's algorithm is a graph algorithm that simultaneously finds the shortest path from a single vertex in a weighted graph to all other vertices in the graph, called the single-source shortest path problem. It works for directed and undirected graphs, but unlike the Bellman-Ford algorithm, requires nonnegative edge weights.


Contents

[edit] Simple graph representation

The data structures supplied by C++'s Standard Template Library facilitate a straightforward implementation of Dijkstra's algorithm. For simplicity, we start with a simple graph representation where the vertices are numbered by sequential integers (0, 1, 2, ...) and the edge weights are doubles. We define a struct representing an edge that stores its weight and target vertex (the vertex it points to):

<<simple graph types>>=
typedef int vertex_t;
typedef double weight_t;

struct edge {
    vertex_t target;
    weight_t weight;
    edge(vertex_t arg_target, weight_t arg_weight)
        : target(arg_target), weight(arg_weight) { }
};

Because we'll need to iterate over the successors of each vertex, we will find an adjacency list representation most convenient. We will represent this as an adjacency map, a mapping from each vertex to the list of edges exiting that vertex, as defined by the following typedef:

<<simple graph types>>=
typedef std::map<vertex_t, std::list<edge> > adjacency_map_t;

<<simple graph type definition headers>>=
#include <map>
#include <list>

[edit] Main algorithm

We're now prepared to define our method. We separate the computation into two stages:

  1. Compute the minimum distance from the source to each vertex in the graph. Simultaneously, keep track of the previous map, which for each vertex v gives the previous vertex on the shortest path from the source vertex to v. This is the expensive step.
  2. Later, any time we want to find a particular shortest path between the source vertex and a given vertex, we use the previous array to quickly construct it.

For the first part, we write DijkstraComputePaths, which takes two input parameters and two output parameters:

  • source (in): The source vertex from which all shortest paths are found
  • adjacency_map (in): The adjacency map specifying the connection between vertices and edge weights.
  • min_distance (out): Will receive the shortest distance from source to each vertex in the graph.
  • previous (out): Receives a map that can be passed back into DijkstraGetShortestPathTo() later on to quickly get a shortest path from the source vertex to any desired vertex.
<<simple compute paths function>>=
void DijkstraComputePaths(vertex_t source,
                          adjacency_map_t& adjacency_map,
                          std::map<vertex_t, weight_t>& min_distance,
                          std::map<vertex_t, vertex_t>& previous)
{
    initialize output parameters
    min_distance[source] = 0;
    visit each vertex u, always visiting vertex with smallest min_distance first
        // Visit each edge exiting u
        for (std::list<edge>::iterator edge_iter = adjacency_map[u].begin();
             edge_iter != adjacency_map[u].end();
             edge_iter++)
        {
            vertex_t v = edge_iter->target;
            weight_t weight = edge_iter->weight;
            relax the edge (u,v)
        }
    }
}

The outline of how the function works is shown above: we visit each vertex, looping over its out-edges and adjusting min_distance as necessary. The critical operation is relaxing the edges, which is based on the following formula:

if (u, v) is an edge and u is on the shortest path to v, d(u) + w(u,v) = d(v).

In other words, we can reach v by going from the source to u, then following the edge (u,v). Eventually, we will visit every predecessor of v reachable from the source. The shortest path goes through one of these. We keep track of the shortest distance seen so far by setting min_distance and the vertex it went through by setting previous:

<<relax the edge (u,v)>>=
weight_t distance_through_u = min_distance[u] + weight;
if (distance_through_u < min_distance[v]) {
    remove v from queue
    min_distance[v] = distance_through_u;
    previous[v] = u;
    re-add v to queue
}

We also need to initialize the output parameters so that at first all min distances are positive infinity (as large as possible). We can visit all vertices by just iterating over the keys of adjacency_map:

<<initialize output parameters>>=
for (adjacency_map_t::iterator vertex_iter = adjacency_map.begin();
     vertex_iter != adjacency_map.end();
     vertex_iter++)
{
    vertex_t v = vertex_iter->first;
    min_distance[v] = std::numeric_limits< double >::infinity();
}

Finally, we need a way to visit the vertices in order of their minimum distance. Ideally we would do this using an available priority queue data structure, but the STL's basic priority queue does not allow decreasing of keys of elements in the queue, which we need. Instead, we will use a std::set of pairs, where each pair contains a vertex v along with its minimum distance min_distance[v]. The set is ordered by the min_distance component:

<<pair first less comparator>>=
template <typename T1, typename T2>
struct pair_first_less
{
    bool operator()(std::pair<T1,T2> p1, std::pair<T1,T2> p2)
    {
        return p1.first < p2.first;
    }
};

<<visit each vertex u, always visiting vertex with smallest min_distance first>>=
std::set< std::pair<weight_t, vertex_t>,
          pair_first_less<weight_t, vertex_t> > vertex_queue;
for (adjacency_map_t::iterator vertex_iter = adjacency_map.begin();
     vertex_iter != adjacency_map.end();
     vertex_iter++)
{
    vertex_t v = vertex_iter->first;
    vertex_queue.insert(std::pair<weight_t, vertex_t>(min_distance[v], v));
}

while (!vertex_queue.empty()) {
    vertex_t u = vertex_queue.begin()->second;
    vertex_queue.erase(vertex_queue.begin());

<<simple graph type definition headers>>=
#include <set>

We access and remove the smallest element using begin(), which works because the set is ordered by minimum distance. If we change a vertex's minimum distance, we must update its key in the map as well:

<<remove v from queue>>=
vertex_queue.erase(std::pair<weight_t, vertex_t>(min_distance[v], v));

<<re-add v to queue>>=
vertex_queue.insert(std::pair<weight_t, vertex_t>(min_distance[v], v));

This completes DijkstraComputePaths(). DijkstraGetShortestPathTo() is much simpler, just following the linked list in the previous map from the target back to the source:

<<get shortest path function>>=
std::list<vertex_t> DijkstraGetShortestPathTo(
    vertex_t target, std::map<vertex_t, vertex_t>& previous)
{
    std::list<vertex_t> path;
    std::map<vertex_t, vertex_t>::iterator prev;
    vertex_t vertex = target;
    path.push_front(vertex);
    while((prev = previous.find(vertex)) != previous.end())
    {
        vertex = prev->second;
        path.push_front(vertex);
    }
    return path;
}

[edit] Sample code

Here's some code demonstrating how we use the above functions:

<<dijkstra_example.cpp>>=
#include <iostream>
#include <vector>
#include <string>
simple graph type definition headers

simple graph types

pair first less comparator

simple compute paths function

get shortest path function

int main()
{
    adjacency_map_t adjacency_map;
    std::vector<std::string> vertex_names;

    initialize adjacency map

    std::map<vertex_t, weight_t> min_distance;
    std::map<vertex_t, vertex_t> previous;
    DijkstraComputePaths(0, adjacency_map, min_distance, previous);
    print out shortest paths and distances
    return 0;
}

Printing out shortest paths is just a matter of iterating over the vertices and calling DijkstraGetShortestPathTo() on each:

<<print out shortest paths and distances>>=
for (adjacency_map_t::iterator vertex_iter = adjacency_map.begin();
     vertex_iter != adjacency_map.end();
     vertex_iter++)
{
    vertex_t v = vertex_iter->first;
    std::cout << "Distance to " << vertex_names[v] << ": " << min_distance[v] << std::endl;
    std::list<vertex_t> path =
        DijkstraGetShortestPathTo(v, previous);
    std::list<vertex_t>::iterator path_iter = path.begin();
    std::cout << "Path: ";
    for( ; path_iter != path.end(); path_iter++)
    {
        std::cout << vertex_names[*path_iter] << " ";
    }
    std::cout << std::endl;
}

For this example, we choose vertices corresponding to some East Coast U.S. cities. We add edges corresponding to interstate highways, with the edge weight set to the driving distance between the cities in miles as determined by Mapquest:

<<initialize adjacency map>>=
vertex_names.push_back("Harrisburg");   // 0
vertex_names.push_back("Baltimore");    // 1
vertex_names.push_back("Washington");   // 2
vertex_names.push_back("Philadelphia"); // 3
vertex_names.push_back("Binghamton");   // 4
vertex_names.push_back("Allentown");    // 5
vertex_names.push_back("New York");     // 6
adjacency_map[0].push_back(edge(1,  79.83));
adjacency_map[0].push_back(edge(5,  81.15));
adjacency_map[1].push_back(edge(0,  79.75));
adjacency_map[1].push_back(edge(2,  39.42));
adjacency_map[1].push_back(edge(3, 103.00));
adjacency_map[2].push_back(edge(1,  38.65));
adjacency_map[3].push_back(edge(1, 102.53));
adjacency_map[3].push_back(edge(5,  61.44));
adjacency_map[3].push_back(edge(6,  96.79));
adjacency_map[4].push_back(edge(5, 133.04));
adjacency_map[5].push_back(edge(0,  81.77));
adjacency_map[5].push_back(edge(3,  62.05));
adjacency_map[5].push_back(edge(4, 134.47));
adjacency_map[5].push_back(edge(6,  91.63));
adjacency_map[6].push_back(edge(3,  97.24));
adjacency_map[6].push_back(edge(5,  87.94));

[edit] Alternatives

In an application that does a lot of graph manipulation, a good option is the Boost graph library, which includes support for Dijkstra's algorithm.

Download code
hijacker
hijacker
hijacker
hijacker