shortest.c

来自「本程序编写了一个dijkstra算法求解最短路问题」· C语言 代码 · 共 34 行

/* Note:Your choice is C IDE */
#include "stdio.h"
main()
{/*变量申明部分*/
	
 /*最短路函数调用部分*/
	int Dijkstra(int dist[SIZE][SIZE],int s,int t, int path[])/*dijkstra算法寻找s-t的最短路长和最短路径*/
      {
          int i,j,n,w,minc,d[SIZE],mark[SIZE];
          n=SIZE;
          for (i=0;i<n;i++) mark[i]=0;
          for (i=0;i<n;i++)
              { d[i]=dist[s][i];
              path[i]=s; }
          mark[s]=1;path[s]=0;d[s]=0;
          for (i=1;i<n;i++)
              {
              minc=30000;
              w=0;
              for (j=0;j<n;j++)
                  if ((mark[j]==0)&&(minc>=d[j])) {minc=d[j];w=j;}
              mark[w]=1;
              for (j=0;j<n;j++)
              if ((mark[j]==0)&&(dist[w][j]!=30000)&&(d[j]>d[w]+dist[w][j]))
                  { d[j]=d[w]+dist[w][j];
                  path[j]=w;
                  }
              }
           return d[t];
      }
 /*输出部分*/
    
}