#include "stdio.h"
#define BIG 9999 //無(wú)窮大
//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<n;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<n;i++) {//每循環(huán)一次，求得一個(gè)最短路徑
           mindis=BIG;
           for (j=0;j<n;j++) //求離出發(fā)點(diǎn)最近的頂點(diǎn)
                 if(s [j]==0&&Distance[j]<mindis) {
                       mindis=Distance [j];
                       u=j;
                 } // if語(yǔ)句體結(jié)束，j循環(huán)結(jié)束
           for(j=0;j<n;j++) //修改遞增路徑序列（集合）
                 if(s[j]==0) { //對(duì)還未求得最短路徑的頂點(diǎn)
                       //求出由最近的頂點(diǎn) 直達(dá)各頂點(diǎn)的距離
                       dis=Distance[u] +Cost[u][j];
                       // 如果新的路徑更短，就替換掉原路徑
                       Distance[j]= (Distance[j]<dis)?
                          & nbsp;  Distance[j]:dis;
                 } // if 語(yǔ)句體結(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},
                          & nbsp;  {2,0,BIG,BIG,8,BIG},
                          & nbsp;  {BIG,15,0,BIG,BIG,7},
                          & nbsp;  {BIG,BIG,BIG,0,BIG,BIG},
                          & nbsp;  {BIG,BIG,BIG,4,0,BIG},
                          & nbsp;  {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]);
}