1) 首先我們定義 


struct map{　　　　　　 


 int num;　　　　　　　 //存放結點數 


 int weight[30][30];} g;　//存放結點之間的權重 


int *d;　//用d[i]表示結點i到源結點的最短路徑的總權重 


int *r;　//用r[i]表示最短路徑中i的前一個結點 


用上面的類型存放圖的信息 




2)然后定義一個函數（也是程序的核心） 


void shortpath(){　　  //計算最短路徑 


 int final[30];　　　  //當結點I到源結點的最短路徑被算出后final[i]=true； 


//表示結點被刪除 


 int min; 


 int w,v; 


 int v0=1; //起始結點 


 int i; 


 for(v=1;v<=g.num;++v){　　//初始化 


　final[v]=false; 


　d[v]=g.weight[v0][v]; 


　if(d[v]<max)r[v]=v0; 


　} 




  d[v0]=0;final[v0]=true;　　　 //刪除源結點 




　for(i=1;i<=g.num;++i){ 


　min=max; 




　　for(w=1;w<g.num;++w){　//選擇最小的d[ ] 


　　　if(!final[w]) 


　　　  if(d[w]<min){v=w;min=d[w];} 


　　}/ 


final[v]=true ;　　 //刪除結點v 


for(w=1;w<=g.num;++w){　 //最短路徑的選擇 


if(!final[w] && min+g.weight[v][w]<d[w]){ 


　d[w]=min+g.weight[v][w]; 


　r[w]=v;} 


　　　　　　　　　　　 } 


} 


　　　 } 


3）編寫main（）主函數 


 main(){ 


scanf(圖片信息) 


shortpath（）　//調用2）中的函數 


printf(輸出需要的路徑信息 


} 


這部分不是主要部分，也比較簡單，所以請讀者自行添加。 


再次強調步驟2）是程序的核心，真個算法包含其中，需要研究體會。