# Graph Algorithm – Implementing Dijkstra’s Algorithm

March 7, 2010 4 Comments

This was on my mind for quiet a long time and today I finally did it :). All of us ( CS folks) are taught about **Dijkstra’s Shortest Path Algorithm**. Also we are asked to program it. Now, until we participate in some programming contests or be active at some online programming portal we don’t really would be inclined to program a graph algorithm. So, I’ve took up this and provided it for you :). When anybody is asked about the run-time of Dijkstra, one gives an instantaneous answer as O(nlogn) in edges. It’s true, but when we implemented it in our lab, almost all of us wrote the array based O(n^2) version just because the O(nlogn) is not an easy job to code. So, after spending quiet some time debugging my code :(, I was able to complete both the versions :D.

**Array based O(n^2) implementation**

/* Dijkstra's Shortest Path Algorithm O(n^2) implementation */ #include<iostream> #include<vector> #include<cctype> #include<climits> #include<cstdio> using namespace std; int main(int argc, char *argv[]) { int numVertices, Source, select, visited; printf(" Nodes are numbered from 1 .. n. If there os no edge between 2 nodes, enter (i,j) as 0 \n"); scanf("%d",&numVertices); // Vertices are numbered from 0..numVertices - 1 int Adjacency[numVertices+1][numVertices+1]; //Scan the adjacency matrix for (int i = 1; i <= numVertices ; i++) for (int j = 1 ; j <= numVertices ; j++) scanf("%d", &Adjacency[i][j]); int Distance[numVertices+1][3]; for (int i = 1; i <= numVertices ; i++) { Distance[i][0] = 0; //0 if NOT visited, 1 if Visited Distance[i][1] = INT_MAX; // INT_MAX if not visited Distance[i][2] = -1 ; // -1 if has no parent, >= 0 if has a predecessor } scanf("%d",&Source); // Source Vertex, numbers from 0 .. numVertices-1 Distance[Source][1] = 0; Distance[Source][2] = -1; visited = 0; while (visited < numVertices ) { // Find the vertex with minimum value of Distance[n][1] i.e. lowest weight for (int i = 1, min = INT_MAX; i <= numVertices ; i++) { if (Distance[i][0] == 0 && Distance[i][1] < min ){ min = Distance[i][1]; select = i; } } Distance[select][0] = 1; // Mark this as visited // 'select' is the index of the vertex whose neighbours have to be relaxed now for (int i = 1; i <= numVertices; i++) { if (Adjacency[select][i] > 0 && Adjacency[select][i] + Distance[select][1] < Distance[i][1] ) { Distance[i][1] = Adjacency[select][i] + Distance[select][1]; Distance[i][2] = select; } } visited++; } // Print the shortest distance to all vertices for (int i=1; i <= numVertices ; i++) { printf( "Path Distance form %d to %d is %d\n",Source, i, Distance[i][1]); } return 0; }

**Heap based O(nlogn) **

/* Dijkstra's Shortest Path Algorithm O(n * log(n)) implementation */ #include<iostream> #include<cstdio> #include<vector> #include<stack> #include<queue> #include<algorithm> #include<climits> #include<cctype> using namespace std; #define Root 1 #define Parent(a) ((a)/2) #define RC(a) ((a)*2 + 1) #define LC(a) ((a)*2 ) bool cmp( pair<int,int> a, pair<int,int> b) { if ( a.second > b.second ) return true; return false; } int main(int argc, char *argv[]) { int numVertices, Source, select, visited, entry_min_heap; printf(" Nodes are numbered from 1 .. n. If there os no edge between 2 nodes, enter (i,j) as 0 \n"); scanf("%d",&numVertices); // Vertices are numbered from 0..numVertices - 1 int Adjacency[numVertices + 1 ][numVertices + 1]; //Scan the adjacency matrix for (int i = 1; i <= numVertices ; i++) for (int j = 1 ; j <= numVertices ; j++) scanf("%d", &Adjacency[i][j]); // Adjacency entry is 0 at (i,j) if there is no edge between i and j // Create a graph with linked representation vector< pair< vector<pair<int, int> > , int > > Graph(numVertices + 1); for (int i = 1; i <= numVertices; i++) { for ( int j = 1 ; j <= numVertices ; j++ ) { if (Adjacency[i][j] > 0 ) { Graph[i].first.push_back(make_pair<int,int>(j,Adjacency[i][j])); // ID, weight } } Graph[i].second = -1; // Pointer to location of this vertex in heap } vector< pair<int, int> > min_heap(numVertices + 1); for (int i = 1 ; i <= numVertices ; i++ ) { min_heap[i].first = i ; min_heap[i].second = INT_MAX; } scanf("%d",&Source); min_heap[Source].second = 0; make_heap(min_heap.begin() + 1, min_heap.end(), cmp);// Make the heap based on second value in pair i.e. the min distance // Update the entries in Graph for (int i = 1; i <= numVertices ; i++) { Graph[min_heap[i].first].second = i; } visited = 0; while ( visited < numVertices ) { for (vector<pair<int,int> >::iterator it = Graph[min_heap[Root].first].first.begin();it != Graph[min_heap[Root].first].first.end();it++) { if ( min_heap[Root].second + (*it).second < min_heap[Graph[(*it).first].second].second ) { entry_min_heap = Graph[(*it).first].second; min_heap[entry_min_heap].second = min_heap[Root].second + (*it).second; // Update distance while ( entry_min_heap > Root && (min_heap[Parent(entry_min_heap)].second > min_heap[entry_min_heap].second )) { swap(Graph[min_heap[Parent(entry_min_heap)].first].second, Graph[min_heap[entry_min_heap].first].second); swap(min_heap[Parent(entry_min_heap)], min_heap[entry_min_heap]); entry_min_heap = Parent(entry_min_heap); } } } // Pop heap and update Graph.second swap(min_heap[Root], min_heap[min_heap.size()-1-visited]); swap(Graph[min_heap[Root].first].second, Graph[min_heap[min_heap.size()-1-visited].first].second); visited++; int replace = entry_min_heap = Root; while ( entry_min_heap < numVertices - visited ) { if (min_heap[entry_min_heap].second > min_heap[LC(entry_min_heap)].second) { replace = LC(entry_min_heap); } if (min_heap[replace].second > min_heap[RC(entry_min_heap)].second) { replace = RC(entry_min_heap); } if (replace != entry_min_heap) { swap(min_heap[entry_min_heap],min_heap[replace]); swap(Graph[min_heap[entry_min_heap].first].second, Graph[min_heap[replace].first].second); entry_min_heap = replace; } else break; } } // Print the output for (int i = 1 ; i <= numVertices ; i++) { cout << " Distance of " << min_heap[i].first << " vertex from Source ("<<Source<<") : " << min_heap[i].second << "\n"; } return 0; }

The input to both the codes is ‘n’ i.e. the number of nodes in graph, then a n x n adjacency matrix (having an entry as 0 at Adj[i][j], if there is no edge between i and j) and a ‘source’ vertex (From which shortest distance will be calculated).

4 0 3 4 8 2 0 3 3 3 1 0 2 2 5 4 0 4

is a sample input file. Now PLEASE don’t expect me to write the one which uses Fibonacci heap.

Will think of some other program to implement now 🙂

And BTW, for people who want to test their implementation skills of Dijkstra’s Algorithm, there’s a very nice ( and intriguing) problem on SPOJ for you. Here is the link to the problem. DO have a shot if you are free. 🙂

Have a question for you.

given an array of n elements, find if there is a subset of 3 elements sum up to value T with time complexity O(nlgn).

is this possible in nlog n? I could not find one.

I can devise a O(n^2) solution. But I don’t think it’s possible in O(n logn).

http://en.wikipedia.org/wiki/3SUM .

So you sort the array? tryng to think of n^2,

ya .. sorting the array and having a O(n^2) loop inside it.