Name: Title:

 Name:
ONLINE COMPILERS
LIBRARY
MANUAL PAGES & DOCS
CONTACT

User Submitted Source Code!

Description:
prog
Language: C/C++
Code:
#include<stdio.h>

#include<conio.h>

#include<ctype.h>

#define MAX_NODES 4

int d[MAX_NODES][MAX_NODES];

int INFINITY=1000;

char node[MAX_NODES]={'A','B','C','D'};

void display(); void set_cost(); void dijikstra(); void main()
{

int i,j,s,t; clrscr(); set_cost();

printf("\nnetwork topology is represented by a graph of N nodes");

display();

printf("\ndijkstra's algorithm to find shortest path");

dijikstra();

getch();

}

void display()

{

int i,j; printf("\n................................"); printf("\n\t"); for(j=0;j<MAX_NODES;j++);
printf("%c\t",node[j]); printf("\n.................................."); for(i=0;i<MAX_NODES;i++)
{          printf("\n%c\t",node[i]);

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

{          if(d[i][j]==INFINITY)

printf("-\t");

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

}

}

printf("\n.....................................");

}

void set_cost()

{

int i,j;

printf("\n\nenter the values:");

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

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

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

if(d[i][j]<0)

d[i][j]=INFINITY;

}

}}

void dijikstra()

{

int permanent,tentative;

struct state

{

int pred,length;

enum{permanent,tentative}label;

}state[MAX_NODES];

int i,k,s,t,j,min,temp,path[MAX_NODES];

struct state *p;

int n=MAX_NODES;

printf("\nenter the source and destination nodes:");

scanf("%d%d",&s,&t); for(p=&state[0];p<&state[n];p++)

{          p->pred=-1;

p->length=INFINITY;

p->label=tentative;

} state[t].length=0; state[t].label=permanent; k=t; do
{for(i=0;i<n;i++)

if(d[k][i]!=0&&state[i].label==tentative)

{   if(state[k].length+d[k][i]<state[i].length)

{

}

k=0;
state[i].pred=k;
state[i].length=state[k].length+d[k][i];

}

min=INFINITY;

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

if(state[i].label==tentative&&state[i].length<min)

{          min=state[i].length;

k=i;

}

state[k].label=permanent;

}
while(k!=s); temp=s; j=0; for(i=0;i<n;i
++)

{          if(temp!=t)

{          path[j++]=state[temp].pred;

temp=state[temp].pred;

}

}

printf("\nthe shortest path to node %c from %c is:%d\n",node[t],node[s],min);

for(i=j-1;i>=0;i--)

printf("%c->",node[path[i]]);

printf("%c\n",node[s]);

}