dijkstra.c

#include<iostream.h>
#include<conio.h>
#include<stdio.h>
int w[10][10],n,ner[10],visit[10],dist[10],source;
void dijkstra()
{
  for(int i=1;i<n-1;i++)
  {
   int min=1234,u=0;
   for(int j=1;j<=n;j++)
    if(!visit[j] && dist[j]<min) { min=dist[j];u=j;}
    visit[u]=1;
   for(int k=1;k<=n;k++)
    if((dist[k]>(dist[u]+w[u][k]))&& !visit[k])
      {
       dist[k]=dist[u]+w[u][k];
       ner[k]=u;
     }
  }
}

void main()
{
 clrscr();
 int i,j;
 cout<<"\n Enter the value of n ,(i.e.), no of vertices:\t";cin>>n;
 for(i=1;i<=n;i++)
 for(j=1;j<=n;j++)
  {
   scanf("%d",&w[i][j]);
   if(w[i][j]==0) w[i][j]=1234;
 }
 cout<<"\n Enter the source vertex:( 1-"<<n<<" )\t";cin>>source;
 visit[source]=1;
 for(i=1;i<=n;i++)
   {
    dist[i]=w[source][i];
    ner[i]=source;
   }
 dist[source]=0;
 dijkstra();
 for(i=1;i<=n;i++)
 {
   if(ner[i]&& i!=source)
   {
    int temp=i;
    cout<<"\n Path :\t";
    while(temp!=source)
    {
     cout<<temp<<"-";
     temp=ner[temp];
    }
    cout<<source<<"\t Length :\t"<<dist[i];
   }
 }
 getch();
}