Dijkstra’s algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1956 and published in 1959,[1][2] 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:
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<ONGERICHT, int> 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)
// that's 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<typename T>
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<bool> connected;
// Represents the cost to every node from
// the starting node
vector<double> costs;
// priority queue to get the connection with
// the lowest cost
priority_queue<connection> pq;
public:
Dijkstra(GewogenGraaf<ONGERICHT,T> &):start(0){}
Dijkstra(GewogenGraaf<ONGERICHT,T> &,int);
void discover_neighbors(GewogenGraaf<ONGERICHT,T> &,int);
};
Dijkstra’s algorithm
template<typename T>
Dijkstra<T>::Dijkstra(GewogenGraaf<ONGERICHT,T> &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<typename T>
void Dijkstra<T>::discover_neighbors(GewogenGraaf<ONGERICHT,T> &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<int,int> 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;
}
}
}
}
Everything together
Name this file “dijkstra.h”.
// // // // // // // // // // //
//
//
// Dijkstra's algorithm by
// www.cedricve.me
//
//
// // // // // // // // // // //
#ifndef __DIJKSTRA__
#define __DIJKSTRA
#include "ggraaf.h"
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
// 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)
// that's why we say false
// if 15 > 18 => return true;
if(c.cost>cost)
return false;
else
return true;
}
};
template<typename T>
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<bool> connected;
// Represents the cost to every node from
// the starting node
vector<double> costs;
// priority queue to get the connection with
// the lowest cost
priority_queue<connection> pq;
public:
Dijkstra(GewogenGraaf<ONGERICHT,T> &):start(0){}
Dijkstra(GewogenGraaf<ONGERICHT,T> &,int);
void discover_neighbors(GewogenGraaf<ONGERICHT,T> &,int);
};
template<typename T>
Dijkstra<T>::Dijkstra(GewogenGraaf<ONGERICHT,T> &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;
}
}
template<typename T>
void Dijkstra<T>::discover_neighbors(GewogenGraaf<ONGERICHT,T> &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<int,int> 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;
}
}
}
}
#endif
</pre>
<h3>Run</h3>
<pre lang="php">
#include <iostream>
#include "dijkstra.h"
#include <fstream>
using namespace std;
int main() {
GewogenGraaf<ONGERICHT, int> 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;
}
Dijkstra<int> d(g,2);
return 0;
}
Download
Below the rar with all code (the example graaf.txt included).
Please login
Pingback: Cédric Verstraeten » C++ Find the Longest Path in a directed acyclic graph (DAG)
Pingback: Cédric Verstraeten » C++ Bellman-Ford
Pingback: Cédric Verstraeten » C++ Shortest Path in a DAG (Directed Acyclic Graph)