dijkstra.c

Dijkstra最短路径算法 Dijkstra最短路径算法

/* 标准文档模板 */

#include "Stdio.h"
#include "Conio.h"
#define N 5        /*N为结点总数*/
int main(void)
{
   int dis[N]; int path[N]; int k=0,i,mark,max,a,j;int b[N];
 int q[100];int z; int M[N][N];


   FILE *fp;
    fp=fopen("data.txt","r");
    for(i=0;i<N;i++)
      for(j=0;j<N;j++)
       {fscanf(fp,"%d",&M[i][j]);}
    fclose(fp);




 for(i=0;i<N;i++)        /*设定k源点，path，dis的初值*/
 { if(i!=k) M[i][i]=0;        /*k为源点*/
   else M[i][i]=1;
   dis[i]=M[k][i];  /*源点到个顶点路径长度*/
   if(dis[i]<32767) path[i]=k;
   else path[i]=0;
  }

 for(i=0;i<N-1;i++)     /*确定源点到各顶点路径，除源点外要处理N-2条路径*/
 { mark=k; max=32767;
   for(a=0;a<N;a++)    /*在未处理的顶点中，确定当前路径中最短路径*/
    {  if(M[a][a]==0&&dis[a]<max)
         {max=dis[a];mark=a;}
     }

 /*  printf("mark=%d",mark);printf("\n");  */

                      /*mark，max中记录路径最短的结点下标和长度*/
       /*所有结点处理完毕，结束*/
    M[mark][mark]=1;     /*将选中顶点送入w集合中*/

   for(j=0;j<N;j++)      /*利用顶点mark调整dis中路径长度*/
    { if(M[j][j]==0&&M[mark][j]<32767&&dis[mark]+M[mark][j]<dis[j])
        {dis[j]=dis[mark]+M[mark][j]; /*  printf("dis[%d]=%d ",j,dis[j]);printf("\n"); */
          path[j]=mark;  /*调整j结点的直接前驱*/
         }
     }
  }

for(i=0;i<N;i++)
 {if(i==k||dis[i]==0)continue;
  printf("%d-%d: ",k,i);
  q[0]=path[i];
  j=0;

  while(q[j]!=k)
  {j++;
   q[j]=path[q[j-1]];

  }

   for(z=j;z>=0;z--)
   { printf("%d-",q[z]);
    }printf("%d",i); printf("    "); printf("dis=%d",dis[i]);   printf("\n");

 }
getch();

}