Graph Algorithm – Implementing Dijkstra’s Algorithm

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. 🙂

Advertisements

About Avi Dullu
Jaako rakhe saiyan, maar sake na koi!

4 Responses to Graph Algorithm – Implementing Dijkstra’s Algorithm

  1. Neet says:

    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.

  2. Neet says:

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

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: