本文目錄一覽：
用堆來實現計算單源最短路的迪杰斯特拉(Djisktra)算法
//最近剛寫了這個程序，希望對你有幫助
#includestdafx.h
#includestdio.h
#includestdlib.h
#define MAXNODE 30 //定義最大節點數
#define MAXCOST 1000 //如果兩點間無路勁，則設MAXCOST
int dist[MAXNODE],cost[MAXNODE][MAXNODE],n=6; //為實際節點數
//dijkstra算法求單源最短路徑，這個函數就沒加注釋正遲了，需要自己理解。
void dijkstra(int v0) //v0為起始節點
{
int s[MAXNODE];
int mindis,dis,i,j,u;
for(i=1;i=n;i++)
{
dist[i]=cost[v0][i];
s[i]=0;
}
s[v0]=1;
for(i=1;i=n;i++)
{
mindis=MAXCOST;
for(j=1;j=n;j++)
{
if(s[j]==0 dist[j]mindis)
{
u=j;
mindis=dist[j];
}
}
s[u]=1;
for(j=1;j=n;j++)
if(s[j]==0)
{
dis=dist[u]+cost[u][j];
dist[j]=(dist[j]dis)?dist[j]:dis;
}
}
}
//自定義display_path函數，輸出各頂點最短路徑正尺
void display_path(int v0)
{
int i;
printf("\n頂點 %d 到各頂點的最短路舉清李徑長度如下:\n",v0);
for(i=1;i=n;i++)
{
printf(" (v%d-v%d):",v0,i);
if(dist[i]==MAXCOST)
printf("無路徑");
else
printf("%d\n",dist[i]);
}
}
//主函數中各個定點的cost值可以根據實際路勁修改
void main()
{
int i,j,v0=1;
for(i=1;i=n;i++)
for(j=1;j=n;j++)
cost[i][j]=((i==j)?0:MAXCOST);
cost[1][2]=10;
cost[1][4]=30;
cost[1][5]=100;
cost[1][6]=20;
cost[2][3]=50;
cost[3][5]=10;
cost[4][3]=20;
cost[4][5]=60;
cost[5][6]=30;
dijkstra(v0);
display_path(v0);
}
