＃i nclude "stdio.h"
#define BIG 9999 //無窮大
//Dijkstra算法函數(shù)，求給定頂點(diǎn)到其余各點(diǎn)的最短路徑
//參數(shù)：鄰接矩陣、頂點(diǎn)數(shù)、出發(fā)點(diǎn)的下標(biāo)、結(jié)果數(shù)組
void Dijkstra(int Cost[][6],int n,int v0,int Distance[])
{
int s[6];
int mindis,dis;
int i,j,u;
//初始化
for(i=0;i
Distance[i]=Cost[v0][i];
s[i]=0;
}
s[v0]=1; /*標(biāo)記v0*/
//在當(dāng)前還未找到最短路徑的頂點(diǎn)中，
//尋找具有最短距離的頂點(diǎn)
for(i=1;i mindis=BIG;
for(j=0;j if(s[j]==0&&Distance[j] mindis=Distance[j];
u=j;
} // if語句體結(jié)束，j循環(huán)結(jié)束
for(j=0;j if(s[j]==0) { //對還未求得最短路徑的頂點(diǎn)
//求出由最近的頂點(diǎn)直達(dá)各頂點(diǎn)的距離
dis=Distance[u]+Cost[u][j];
//如果新的路徑更短，就替換掉原路徑
Distance[j]=(Distance[j]
Distance[j]:dis;
} // if語句體結(jié)束，，j循環(huán)結(jié)束
s[u]=1; /* 標(biāo)記最短路徑已經(jīng)求得*/
} // i循環(huán)結(jié)束
}
//主函數(shù)
void main()
{
//給出有向網(wǎng)的頂點(diǎn)數(shù)組
char *Vertex[6]={"V1","V2","V3","V4","V5","V6"};
//給出有向網(wǎng)的鄰接矩陣
int Cost[6][6]={{0,BIG,5,30,BIG,BIG},
{2,0,BIG,BIG,8,BIG},
{BIG,15,0,BIG,BIG,7},
{BIG,BIG,BIG,0,BIG,BIG},
{BIG,BIG,BIG,4,0,BIG},
{BIG,BIG,BIG,10,18,0},
};
int Distance[6]; //存放求得的最短路徑
int i;
//調(diào)用Dijkstra算法函數(shù)，求頂點(diǎn)V1到其余各點(diǎn)的最短路徑
//參數(shù)：鄰接矩陣、頂點(diǎn)數(shù)、出發(fā)點(diǎn)的下標(biāo)、結(jié)果數(shù)組
Dijkstra(Cost,6,0,Distance);
for(i=0;i<6;i++)
printf("%s---->%s %d\n",
Vertex[0],Vertex[i],Distance[i]);
}