Monday, July 11, 2011

Dijkstra Algorithm

Here is the program of Dijkstra algorithm done in Tubo C++



 // Program to find the shortest path to all the nodes

// From the given SOURCE NODE.

// Using DIJKSTRA ALGORITHM.

#include<stdio.h>

#include<conio.h>

int main()

{

int path[10][10]={0}; // this matrix will store the shortes path to all notes

int edge[10][10]={0}; // this matrix will hold the weights of edges in a graph

int distance[10]={0}; // this matrix will hold the shortest distance to all

// nodes from the given source node

int visited[10]={0}; // this matrix will holds the status of visited nodes in the algorithm

int a=1;

int n,i,j;

clrscr();

printf("Enter number of nodes:");

scanf("%d",&n);

// Initialise Path matrix

for(i=0;i<n;i++) {

path[i][0]=999;

}

printf("Enter the adjacency matrix:\n \n");

// Get the adjacency matrix Input

for(i=1;i<n;i++)

{

for(j=0;j<i;j++)

{

printf(" Distance from %c to %c ",65+i,65+j);

scanf("%d",&edge[i][j]);

edge[j][i]=edge[i][j];

}

}

// Print the adjacency table

printf("\n Adjacency matrix\n");

for(i=0;i<n;i++) {

for(j=0;j<n;j++) {

printf(" %d\t",edge[i][j]);

}

printf("\n");

}

// Get the source and destination node

fflush(stdin);

char source,dest;

printf("Enter the source:");

scanf("%c",&source);

fflush(stdin);

printf("Enter the destination:");

scanf("%c",&dest);

int from=source-65;

int to=dest-65;

printf("\n Source : %d destination:%d\n",from,to);

// Initialise the distance table

// Set the distance to very hight value(in algo infinity)

// except the from node

for(i=0;i<n;i++) {

if(i!=from) {

distance[i]=1000;

}else {

distance[i]=0;

}

}

//////////////////////////////////////////////////////

// DIJKSTRA ALGORITHM

/////////////////////////////////////////////////////

int k;

for(k=0;k<n;k++) {

// Search the node which is closest to the source node

int short_index=0;

int found=0;

int short_value=1000;

for(i=0;i<n;i++)

{

if(visited[i]==0)

{

// Node is not visited

if(distance[i]<short_value) {

short_index=i;

short_value=distance[i];

found=1;

}

}

}

printf("\n visited : %c",65+short_index);

// Mark the node visited

visited[short_index]=1;

// printf("\n\n distance table :");

// print the distance table

// for(i=0;i<n;i++) {

// printf(" %c: %d\t",65+i,distance[i]);

// }

// Update the distance table

// Check if the current distance is larger than the distance

// via shorted node and if YES update the distance table

// and add the node to the shortes path

int p;

for(p=0;p<n;p++)

{

int via_short = distance[short_index]+edge[short_index][p];

if(distance[p]>via_short) {

distance[p]= via_short;

// Add the current node in the path

int h=0;

while(path[p][h]!=999) {

h++;

}

path[p][h]=short_index;

path[p][h+1]=999;

}

}

}

printf("\n\n FINAL TABLE \n");

// print the distance table

for(i=0;i<n;i++) {

printf(" %c: %d\t",65+i,distance[i]);

}

// Print shorted paths to all nodes

printf("\n\n SHORTEST PATHS TO ALL NODES from source node :\n");

for(i=0;i<n;i++) {

int h=0;

printf(" %c :",65+i);

while(path[i][h]!=999) {

printf("%c->",65+path[i][h]);

h++;

}

printf("%c\n",i+65);

}

getch();

return 0;

}

No comments:

Post a Comment