dijkstra1.txt

dijkstra算法实现最短路径的求法

#include <stdio.h> 

#define n 100

void main()

{

      int s,i,j,oper,min,k,p;               

      printf("Please input the start vertex:\n");               

      scanf("%d",&s);

      int w[n][n],d[n],con[n],sig[n];     

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

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

           {

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

           }

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

           w[i][i]=0;

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

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

                 w[j][i]=w[i][j]; 

  

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

           d[i]=-1;

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

           sig[i]=0;



      d[s]=0;                   

      con[s]=-1;                  

      sig[s]=-1;                 

      oper=s;                   
      while(1)

 {

      k=oper;                 

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

           if(w[oper][i]!=0 && sig[i]==0)

           { 

                 if(d[i]==-1 || d[oper]+w[oper][i] < d[i])

                 {

                    d[i]=w[oper][i]+d[oper];

                    con[i]=oper;

                 }

           }

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

           if(w[oper][i]!=0 && sig[i]==0)

           { 

                 if(d[i]==-1 || d[oper]+w[oper][i]<d[i])

                 {

                   d[i]=w[oper][i]+d[oper];

                   con[i]=oper;

                 }

           }

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

           if(d[i]!=-1 && sig[i]==0)

           {

                 min=d[i];

                 oper=i;

                 break;

           }

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

           if(sig[i]==0 && d[i]!=-1 && d[i]<min)

           { 
		min=d[i];

            	oper=i;

           }       

      if(oper==k)             
                                   

           break;

      else

           sig[oper]=-1;             

 }

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

      {

           if(d[i]!=-1)              
           {

              printf("%d",i);

              p=con[i];

              while(p!=-1)           

              {

                 printf("%d",p);

                 p=con[p];

              }

              printf(" ");

              printf("%d\n",d[i]);

           }

           else printf("There is no route between vertex %d and vertex %d.\n",s,i);

      }

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

      {

           if(d[i]!=-1)

           {

              printf("%d",i);

           p=con[i];

              while(p!=-1)

              {

                 printf("%d",p);

                 p=con[p];

              }

              printf(" ");

              printf("%d\n",d[i]);

           }

           else printf("There is no route between vertex %d and vertex %d.\n",s,i);

      }

}