ulvis.paste.net

Paste Search Dynamic
Recent pastes
dijkstra
  1. #include<stdio.h>
  2.  
  3. #define INFINITY 9999
  4. #define MAX 10
  5.  
  6. void dijkstra(int G[MAX][MAX],int n,int startnode);
  7.  
  8. int main()
  9. {
  10.     int G[MAX][MAX],i,j,n,u;
  11.     printf("Enter no. of vertices:");
  12.     scanf("%d",&n);
  13.     printf("\nEnter the adjacency matrix:\n");
  14.  
  15.     for(i=0;i<n;i++)
  16.         for(j=0;j<n;j++)
  17.             scanf("%d",&G[i][j]);
  18.  
  19.     printf("\nEnter the starting node:");
  20.     scanf("%d",&u);
  21.     dijkstra(G,n,u);
  22.  
  23.     return 0;
  24. }
  25.  
  26. void dijkstra(int G[MAX][MAX],int n,int startnode)
  27. {
  28.  
  29.     int cost[MAX][MAX],distance[MAX],pred[MAX];
  30.     int visited[MAX],count,mindistance,nextnode,i,j;
  31.  
  32.     //pred[] stores the predecessor of each node
  33.     //count gives the number of nodes seen so far
  34.     //create the cost matrix
  35.     for(i=0;i<n;i++)
  36.         for(j=0;j<n;j++)
  37.             if(G[i][j]==0)
  38.                 cost[i][j]=INFINITY;
  39.             else
  40.                 cost[i][j]=G[i][j];
  41.  
  42.     //initialize pred[],distance[] and visited[]
  43.     for(i=0;i<n;i++)
  44.     {
  45.         distance[i]=cost[startnode][i];
  46.         pred[i]=startnode;
  47.         visited[i]=0;
  48.     }
  49.  
  50.     distance[startnode]=0;
  51.     visited[startnode]=1;
  52.     count=1;
  53.  
  54.     while(count<n-1)
  55.     {
  56.         mindistance=INFINITY;
  57.  
  58.         //nextnode gives the node at minimum distance
  59.         for(i=0;i<n;i++)
  60.             if(distance[i]<mindistance&&!visited[i])
  61.             {
  62.                 mindistance=distance[i];
  63.                 nextnode=i;
  64.             }
  65.  
  66.             //check if a better path exists through nextnode            
  67.             visited[nextnode]=1;
  68.             for(i=0;i<n;i++)
  69.                 if(!visited[i])
  70.                     if(mindistance+cost[nextnode][i]<distance[i])
  71.                     {
  72.                         distance[i]=mindistance+cost[nextnode][i];
  73.                         pred[i]=nextnode;
  74.                     }
  75.         count++;
  76.     }
  77.  
  78.     //print the path and distance of each node
  79.     for(i=0;i<n;i++)
  80.         if(i!=startnode)
  81.         {
  82.             printf("\nDistance of node%d=%d",i,distance[i]);
  83.             printf("\nPath=%d",i);
  84.  
  85.             j=i;
  86.             do
  87.             {
  88.                 j=pred[j];
  89.                 printf("<---%d",j);
  90.             }while(j!=startnode);
  91.     }
  92. }
Parsed in 0.013 seconds