Dijkstra

Dijkstra's algorithm is a method to compute the shortest path between two nodes in a graph. One possible use could be for calculating the best driving route in a road network (vertices are intersections and edges weights are the time needed to travel a road).

The basic algorithm requires:

• An array to which nodes have been visited
• A priority queue to choose which node to visit next
• A structure to store the graph

The method of determining priority is by shortest known distance from the initial node. At the start of the algorithm we only know that the initial node is 0 distance away from itself, all other nodes are an initially known to be an infinite distance away. Therefore the first node to come off the queue will be our starting node, at which point we mark it visited and update the shortest paths (and thus the priority queue) to all its neighbors. As each node is visited the known shortest distance to it's neighbor nodes are updated. Since all other paths are larger than the one that comes off the priority queue at each iteration, it is guaranteed that when a node comes of the queue its shortest path is known. This means that when our target node comes off the queue the algorithm is completed.

The complexity of the algorithm depends largely on what data structures are chosen to represent the graph and the priority queue. If the distances are stored in a normal array and a linear search is performed to find the next minimum the complexity is $O(V^2 + E)$(see Big O notation). If a binary heap is used for the priority queue the complexity is $O((E+V)\log(V))$. A fibonacci heap will improve this to $O(E + V\log V)$ as pushing values onto the heap is $O(1)$.

Here are a number of implementations of the algorithm. The assumed input format is:
V E
v v w
…
where V is # of vertices, E is # of edges, followed by E lines where v are vertex numbers and w is the associated edge weight.

Java

import java.io.*;
import java.util.StringTokenizer;
public class dij
{
    static boolean visited[]=new boolean[1000]; // 1000 would be the max number of nodes
    static long adj[][]=new long[1000][1000]; // to store the graph in an adjacency matrix (see graph storage)
    static long best[]=new long[1000];
    public static void main(String[] args) throws Exception
    {
        BufferedReader in=new BufferedReader(new FileReader("dij.in"));
        PrintWriter out=new PrintWriter(new BufferedWriter(new FileWriter("dij.out")));
        StringTokenizer token=new StringTokenizer(in.readLine());
        int V=Integer.parseInt(token.nextToken()); // Number of vertices
        int E=Integer.parseInt(token.nextToken()); // Number of edges
        long MAX=555555555; // setting our "infinity" value
        for(int i=0; i<V; i++) // Let's set all the entire graph to inf.
            for(int j=0; j<V; j++)
                adj[i][j]=MAX;
        for(int i=0; i<E; i++)
        {
            token=new StringTokenizer(in.readLine());
            int v1=Integer.parseInt(token.nextToken())-1;
            int v2=Integer.parseInt(token.nextToken())-1;
            int len=Integer.parseInt(token.nextToken());
            // Let's protect ourselves from overwriting good paths. Example: 1 2 5, then 1 2 7.
            // A normal read would overwrite the length 5 with 7, which would not preserve
            // the "shortest" path. The statement is also one of those wacked up if-else statements
            // that to preserve space, jumbles everything up. It wants to say, if adj[v1][v2]<len, then
            // adj[v1][v2] = adj[v1][v2]. Else, if adj[v1][v2] > len, then make adj[v1][v2] = len.
            adj[v1][v2]=adj[v1][v2]<len?adj[v1][v2]:len;
            adj[v2][v1]=adj[v1][v2];
        }
        for(int i=0; i<V; i++)
        {
            best[i]=MAX; // The 'best' array is the shortest path to the node.
            visited[i]=false; // The visited array is pretty self-explanatory
        }
        best[0]=0; // We are starting at node '0', so the best is 0 (we're already there)
        for(int i=0; i<V; i++)
        {
            long min=MAX;
            int curnode=0; // This is our current node
            for(int j=0; j<V;j++) // 
                if(!visited[j]&&best[j]<min)
                {
                    curnode=j;
                    min=best[j];
                                }
            visited[curnode]=true;
            for(int j=0; j<V; j++)
                if(adj[curnode][j]<MAX&&best[curnode]+adj[curnode][j]<best[j])
                    best[j]=best[curnode]+adj[curnode][j];
        }
    out.println(best[V-1]); //We wanted the best path to the last node.
    out.close();
    }
}

1st C++

This is a basic implementation of the algorithm using an adjacency matrix.

#include <iostream>
#include <fstream>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
 
using namespace std;
 
#define VMAX (1001)
#define EMAX (30001)
#define INTMAX (9223372036854775807LL) //2^63-1 also LL so compiler knows its long long
 
ifstream fin("dij.in");
ofstream fout("dij.out");
 
int visited[VMAX]; //if visited[i] is 0 we haven't been to node i yet
long long adjmat[VMAX][VMAX]; //adjacency matrix for our graph
long long priolist[VMAX]; //priolist[i] tells us best known distance to node i from node 1
 
int main()
{
        int V,E,cur;
 
        fin >> V; fin >> E; //read in parameters
 
        //set all edges to infinity initially
        for(int i=1; i<=V; i++)
                for(int j=1; j<=V; j++)
                        adjmat[i][j]=INTMAX;
 
        //read in edges keeping only the minimum
        for(int i=0; i<E; i++) {
                int v1,v2,tmp;
                fin >> v1; fin >> v2;
                fin >> tmp;
                adjmat[v1][v2]<?=tmp; // <?= sets left to min(left,right)
                adjmat[v2][v1]<?=tmp;
        }
 
        //set all distances to infinity to start
        for(int i=1; i<=V; i++)
                priolist[i]=INTMAX;
        //start at node 1 and set distance to 0
        cur=1; priolist[1]=0;
 
        //keep going until we get the node we want
        while(cur!=V) {
                long long tempmin = INTMAX; //we need him later
                visited[cur]=1; //mark current node as visited
 
                //update distances for each vertex connected to current
                for(int i=1; i<=V; i++) {
                        if(adjmat[cur][i] != INTMAX) //to prevent adding to infinity
                                priolist[i]<?=priolist[cur] + adjmat[cur][i];
                }
 
                //look for the next node to visit (the one with min distance)
                for(int i=1; i<=V; i++) {
                        if(visited[i]==0 && priolist[i] < tempmin) {
                                cur=i;
                                tempmin = priolist[i];
                        }
                }
        }
 
        fout << priolist[V] << endl;
        exit(0);
}

2nd C++

This implementation uses an adjacency list instead of an adjacency matrix.

#include <iostream>
#include <fstream>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
 
using namespace std;
 
#define VMAX (1001)
#define EMAX (30001)
#define INTMAX (9223372036854775807LL)
 
ifstream fin("dij.in");
ofstream fout("dij.out");
 
int visited[VMAX];
vector< pair<long long,int> > adjlist[VMAX]; //adjacency list this time
//adjlist[i] holds a list (vector) of pairs (distance,node)
long long priolist[VMAX];
 
int main()
{
        int V,E,cur;
 
        fin >> V; fin >> E;
 
        //the min edge will automatically be chosen during loop later
        //thus we read all edges in which comes in handy in some problems (HINT)
        for(int i=0; i<E; i++) {
                int v1,v2,tmp;
                fin >> v1; fin >> v2;
                fin >> tmp;
                adjlist[v1].push_back(pair<long long, int>(tmp,v2));
                adjlist[v2].push_back(pair<long long, int>(tmp,v1));
        }
 
        for(int i=1; i<=V; i++)
                priolist[i]=INTMAX;
        cur=1; priolist[1]=0;
 
        while(cur!=V) {
                long long tempmin = INTMAX;
                visited[cur]=1;
 
                //looks a little different with vectors and pairs
                for(int i=0; i<adjlist[cur].size(); i++) {
                        priolist[adjlist[cur][i].second]<?=\
                        priolist[cur] + adjlist[cur][i].first;
                }
 
                for(int i=1; i<=V; i++) {
                        if(visited[i]==0 && priolist[i] < tempmin) {
                                cur=i;
                                tempmin = priolist[i];
                        }
                }
        }
 
        fout << priolist[V] << endl;
        exit(0);
}

3rd C++

This implementation uses an adjacency list and a heap. But in order to save coding work, this implementation is $O((E+V)log(E))$ because multiple paths to one node are permitted in the heap.

#include <iostream>
#include <fstream>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
 
using namespace std;
 
#define VMAX (1001)
#define EMAX (30001)
#define INTMAX (9223372036854775807LL)
 
ifstream fin("dij.in");
ofstream fout("dij.out");
 
int visited[VMAX];
vector< pair<long long,int> > adjlist[VMAX];
vector< pair<long long,int> > priolist; //distance list will be a heap now
 
int main()
{
        int V,E;
 
        fin >> V; fin >> E;
 
        for(int i=0; i<E; i++) {
                int v1,v2,tmp;
                fin >> v1; fin >> v2;
                fin >> tmp;
                adjlist[v1].push_back(pair<long long, int>(tmp,v2));
                adjlist[v2].push_back(pair<long long, int>(tmp,v1));
        }
 
        //the distance list is set up as usual
        priolist.push_back(pair<long long, int>(0LL,1));
 
        //pulling the minimum off is auotmatically covered by the heap
        while(!priolist.empty()) {
                int cur=priolist[0].second; //min resides on front
                int curdist=priolist[0].first;
 
                //pop_heap takes the head of the heap and puts it on the
                //end of the vector, then we take it off.
                //also we use greater to make a min heap (default heap is max)
                pop_heap(priolist.begin(),priolist.end(),\
                greater< pair<long long, int> >());
                priolist.pop_back();
 
                //if we hit the desired node, stop.
                //also some nodes can come off the heap twice
                if(cur==V){fout << curdist << endl; break;}
                if(visited[cur]!=0){continue;}
 
                visited[cur]=1;
 
                //this is where some nodes get on the heap more than once
                //we allow this because it is more expensive to find and update
                //a node once it is on the heap than it is to allow the heap
                //to contain more than one possible distance to a node
                for(int i=0; i<adjlist[cur].size(); i++) {
                        if(visited[adjlist[cur][i].second]==0) {
                                //first we put the desired item on the back of
                                //the vector for heaping
                                priolist.push_back(pair<long long,int>(curdist\
                                +adjlist[cur][i].first,adjlist[cur][i].second));
                                //then we do the heaping
                                push_heap(priolist.begin(),priolist.end(),\
                                greater< pair<long long, int> >());
                        }
                }
        }
 
        exit(0);
}