C++ Dijkstra

Dijkstra’s algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1956 and published in 1959, is a graph search algorithm that solves the single-source shortest path problem for a graph with nonnegative edge path costs, producing a shortest path tree. This algorithm is often used in routing and as a subroutine in other graph algorithms. For a given source vertex (node) in the graph, the algorithm finds the path with lowest cost (i.e. the shortest path) between that vertex and every other vertex. It can also be used for finding costs of shortest paths from a single vertex to a single destination vertex by stopping the algorithm once the shortest path to the destination vertex has been determined. For example, if the vertices of the graph represent cities and edge path costs represent driving distances between pairs of cities connected by a direct road, Dijkstra’s algorithm can be used to find the shortest route between one city and all other cities. As a result, the shortest path first is widely used in network routing protocols, most notably IS-IS and OSPF (Open Shortest Path First).

Dijkstra’s original algorithm does not use a min-priority queue and runs in O(|V|2). The idea of this algorithm is also given in (Leyzorek et al. 1957). The implementation based on a min-priority queue implemented by a Fibonacci heap and running in O(|E| + |V| log |V|) is due to (Fredman & Tarjan 1984). This is asymptotically the fastest known single-source shortest-path algorithm for arbitrary directed graphs with unbounded nonnegative weights. (For an overview of earlier shortest path algorithms and later improvements and adaptations, see: Single-source shortest-paths algorithms for directed graphs with nonnegative weights.)

Dijkstra’s Algorithm Youtube Video

Dijkstra in C++

(This explanation is similar to my previous post Prim’s algorithm)

So now let’s do it in C++. In this tutorial I used an graph class which is created by wijnand schepens (a lecturer on my school). The graph class can read out a file and creates connections between the different nodes. We will use an expansion of this class because we need a “Weighted Graph” to calculate the minimal spanning tree. This class is also created by wijnand schepens and inherits the regular graph class. So we can just work with the weight graph class “ggraph.cpp”.

You can download the (weighted)graph classes here:

Weighted graph

The graph

Solution

If we solve this (with starting node = 2) we will find:
(My graph looks different but the structure is the same, you can read the result in the top left corner)

The file

If you will check out the lees(read) function of the graph class. You will see how we need to build our txt file. First we need to define if its a ongerichte (undirected) graph or a gerichte (directed graph). In this example we make use of an undirected graph. Then we need to write how many nodes there are in our graph. Next the number of the connections and finally all the connections “from, to and their weight”.

The txt file will look like this:


ongericht
8
12
0 2 20
0 1 40
0 5 80
0 6 50
0 7 30
1 7 50
3 5 10
3 4 10
4 5 20
4 7 70
4 6 100
6 7 60

Reading the file

We can open this txt file with an ifstream and pass it to a graph object like this.


GewogenGraaf g;

ifstream fileReader;
string file = "graaf.txt";
fileReader.open(file.c_str());

// check if file exists (try opening it)
if(!fileReader.is_open()){
    cout << "Can't open: " << file << endl;
    return 1;
}

// pass file to lees method of class ggraph.ccp
// this method reads out the file and creates a graph structure
try {
    g.lees(fileReader);
} catch (GraafExceptie ge) {
    cout << ge << endl;
    return 1;
}

Connection

We will use this struct to keep the from node, to node and their cost together. This will make everything easier (you will see).


// connection (struct)
// to keep from node, to node and the cost between
// 1 object, this will make everything easier
struct connection {
    int from;
    int to;
    double cost;
    connection(int f,int t,int c){
        from = f;
        to = t;
        cost = c;
    }
    // we need to overload this method because
    // we will use a priority queue that will contain
    // connection objects
    bool operator<(const connection & c) const{
        // we want a min priority queue (or heap)
        // thats why we say false
        // if 15 > 18 => return true;
        if(c.cost>cost)
            return false;
        else 
            return true;
    }
};

The Dijkstra Class

We have 2 vectors: one (connected) to check which nodes are visited already and one to save the lowest costs. The var “start” will be used as our starting point, so the costs vector will show the costs from every other point with respect to the starting point.


template
class Dijkstra{
    private:
        // Starting node
        int start;
        // TRUE if we looped a node his neighbors
        // if v[5] == true => means we discovered (node 5) all his neighbors
        vector connected;
        // Represents the cost to every node from
        // the starting node
        vector costs;
        // priority queue to get the connection with
        // the lowest cost
        priority_queue pq;
    public:
        Dijkstra(GewogenGraaf &):start(0){}
        Dijkstra(GewogenGraaf &,int);
        void discover_neighbors(GewogenGraaf &,int);

};

Dijkstra’s algorithm


template
Dijkstra::Dijkstra(GewogenGraaf &g,int s){
    start = s;
    // initialize both vectors, with the amount of nodes
    // that the graph contains
    connected.resize(g.aantal_knopen());
    costs.resize(g.aantal_knopen());

    // Increase costs to MAX
    for(unsigned int i = 0; i < costs.size(); i++)
        costs[i] = 99999999;
    // All connected are false
    for(unsigned int i = 0; i < connected.size();i++)
        connected[i] = false;

    // The cost to himself is zero (0) => DUUh!
    costs[s]=0;

    discover_neighbors(g,s);

    while(!pq.empty())
    {
        connection c = pq.top();
        // if this neighbor isn't connected
        // get all his neighbors
        if(!connected[c.to])
            discover_neighbors(g,c.to);
        pq.pop();
    }

    for(unsigned int i = 0; i < costs.size(); i++)
    {
        cout << "From ("<< s <<") To ("<< i <<"): " << costs[i] << endl;
    }
}

Discover Neighbors


template
void Dijkstra::discover_neighbors(GewogenGraaf &g,int node_id){
    // we discovered this node
    connected[node_id]=true;

    // get the current cost of this node
    // look in the costs vector
    double current_cost = costs[node_id];

    // Get all neighbors from this node
    // we can call the [] operator from the graph class
    // this methode will return all connections from this node
    // This will be stored in an object Knoop => this is just a map object
    // The map contains the neighbor_id and the connection_id (connection_id we will need to get the cost from a specific connection)
    Knoop connections = g[node_id];
    // we will loop this map or Knoop object with an iterator

    int cost_neighbor;
    int total_cost;
    int neighbor;
    for(Knoop::iterator itr = connections.begin(); itr != connections.end();itr++){
        // get the neighbor id from the map
        neighbor = itr->first;
        // check if this neighbor is allready connected
        if(!connected[neighbor])
        {
            // get the cost from the current node to this neighbor
            cost_neighbor = g.gewicht(itr->second);
            // sum the current cost and the cost of the neighbor
            total_cost = current_cost + cost_neighbor;
            // check is this cost is smaller than the original cost in the costs vector
            // if so change his cost and push it on the priority queue
            if(total_cost < costs[neighbor])
            {
                connection c(node_id,neighbor,total_cost);
                pq.push(c);
                // change the NEW (lower) cost
                costs[neighbor]=total_cost;
            }

        }
    }
}

Complete source



Download

Below the rar with all code (the example graaf.txt included).

Hey, I'm Cédric a motivated M. Sc. in Engineering, always ready to broaden my horizon and to discover and learn new methodologies. With a huge interest in math, physics, digital image processing, artificial intelligence and bioinformatics, I try to understand our mountainous world a little bit better. I defended my dissertation with honors for world's largest steel company, ArcelorMittal: Development of algorithms for label recognition. These days I'm functioning as a R&D Software Engineer at NV Michel Van de Wiele.