Implementation of dijkstra algorithm in C.

#include <stdio.h>
#define INF 99999
#define YES 1
#define NO 0

struct node
{
int id;      ;
struct node *adjNodes[10];//assuming for simplicity that each node can have at max 10 adjacent nodes. better use adjacency lists
int key;
int edgeWeights[10];//edgeWeight[i] stores the weight of the edge b/w this node and adjNodes[i]
struct node *predecessor;
int conquered; //is YES iff the node is conquered
};

struct node *nodes;
int nofNodes;

int readGraphFromFile()
{
FILE *fin=fopen("graph.dat","r");
if(fin==NULL)
printf("could not open file");
fscanf(fin,"%d",&nofNodes);
printf("no. of nodes in the graph is %d\n",nofNodes);
nodes=calloc((size_t)nofNodes,sizeof(struct node));
int i,temp=0,adjCount,tempwt;
for(i=0;i<nofNodes;i++)
{
nodes[i].id=i;
adjCount=0;
fscanf(fin,"%d %d",&temp,&tempwt);
while(temp!=-1)
{
nodes[i].adjNodes[adjCount]=&nodes[temp];
nodes[i].edgeWeights[adjCount]=tempwt;
fscanf(fin,"%d %d",&temp,&tempwt);
adjCount++;
}
}
}

void printGraph()
{
printf("printing the graph now\n-------------------------------\n");
int i,adjCount;
struct node *temp;
for(i=0;i<nofNodes;i++)
{
adjCount=0;
printf("now printing the nodes adjacent to the node with id %d ...\n",i);
while((temp=nodes[i].adjNodes[adjCount++])!=NULL)
printf("node id %d connected by edge of weight= %d\n",temp->id,nodes[i].edgeWeights[adjCount-1]);
}
printf("-----------------------------\n");
}

void initializeSingleSource(int sourceIndex)
{
int i;
for(i=0;i<nofNodes;i++)
{
nodes[i].key=INF;
nodes[i].predecessor=NULL;
nodes[i].conquered=NO;
}
nodes[sourceIndex].key=0;
}

/** searches the unconquered nodes for the node with the minimum
*key value(which is the min distance
*from the source) and returns its index after setting its conquered field to yes
*/
int conquerMin()
{
int min=INF;
int minIndex=-1;
int i=0;
for(i=0;i<nofNodes;i++)
{
if(nodes[i].conquered==NO)
{
if(nodes[i].key<min)
{
min=nodes[i].key;
minIndex=i;
}
}
}
nodes[minIndex].conquered=YES;
return minIndex;
}

/**after conquering a nodes the key values of all its adjacent nodes are updated.
* This process is called relaxation
*/
void relaxAllAdjacentNodes(struct node *justConqueredNode)
{
int srcKey=justConqueredNode->key;
int adjCount=0,keyIfRelaxed;
struct node *temp;
while((temp=justConqueredNode->adjNodes[adjCount])!=NULL)
{
keyIfRelaxed=justConqueredNode->edgeWeights[adjCount]+srcKey;
if((temp->key)>keyIfRelaxed)// the path via justConqueredNode is better(has less sum of weights of edges in the path)
{
temp->key=keyIfRelaxed;
temp->predecessor=justConqueredNode;// this predecessor value will be used to trace the actual path after the dijkstra algo finishes
}
adjCount++;
}
}

void dijkstra()
{
printf("\n\nrunning Dijkshtra now.....");
int cindex=conquerMin();
while(cindex!=-1)
{
relaxAllAdjacentNodes(&nodes[cindex]);
printf("conquered node with id %d \n",cindex);
cindex=conquerMin();
}
}

void printShortestPathTo(struct node *nd)
{
if(nd!=NULL)
{
printShortestPathTo(nd->predecessor);
printf("node%d->",nd->id);
}
}

int main()
{
int srcIndex;
readGraphFromFile();
printGraph();
printf("\n\nenter the index of the node which is the source of Dijkstra \n shortest path will be found from this node to all other nodes ");
scanf("%d",&srcIndex);
initializeSingleSource(srcIndex);
printf("initialized single source\n");
dijkstra();
printf("finished running dijkshtra...\n\n\n");
printf("now printing the shortest paths...\n");
int i;
for(i=0;i<nofNodes;i++)
{
printf("now printing the shortest path to node %d \n",i);
printShortestPathTo(&nodes[i]);
printf("\n");
}
}
Advertisements

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