?typedef?int?VRType;
?typedef?char?InfoType;
?#define?MAX_NAME?5?//?頂點(diǎn)字符串的最大長度+1
?#define?MAX_INFO?20?//?相關(guān)信息字符串的最大長度+1
?typedef?char?VertexType[MAX_NAME];
?#include“Graph_Matrix.h“
?#include“Graph.h“
?typedef?int?PathMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];?//?路徑矩陣，二維數(shù)組MAX_VERTEX_NUM的定義在Graph_Matrix中
?typedef?int?ShortPathTable[MAX_VERTEX_NUM];?//?最短距離表，一維數(shù)組

?void?ShortestPath_DIJ（MGraph?Gint?v0int?v1PathMatrix?PShortPathTable?D）
?{?//?用Dijkstra算法求有向網(wǎng)G的v0頂點(diǎn)到其余頂點(diǎn)v的最短路徑P[v]及帶權(quán)長度
???//?D[v]。若P[v][w]為TRUE，則w是從v0到v當(dāng)前求得最短路徑上的頂點(diǎn)。
???//?final[v]為TRUE當(dāng)且僅當(dāng)v∈S，即已經(jīng)求得從v0到v的最短路徑?算法7.15
???int?vwijmin;
???int?flag=0;
???Status?final[MAX_VERTEX_NUM];?//?輔助矩陣，為真表示該頂點(diǎn)到v0的最短距離已求出，初值為假
???for（v=0;v???{
?????final[v]=FALSE;?//?設(shè)初值
?????D[v]=G.arcs[v0][v].adj;?//?D[]存放v0到v的最短距離，初值為v0到v的直接距離
?????for（w=0;w???????P[v][w]=FALSE;?//?設(shè)P[][]初值為FALSE，沒有路徑
?????if（D[v]???????P[v][v0]=P[v][v]=TRUE;?//?一維數(shù)組p[v][]表示源點(diǎn)v0到v最短路徑通過的頂點(diǎn)
???}
???D[v0]=0;?//?v0到v0距離為0
???final[v0]=TRUE;?//?v0頂點(diǎn)并入S集
???printf（“%s->“G.vexs[v0]）;//經(jīng)過路徑的起始頂點(diǎn)
???for（i=1;i???{?//?開始主循環(huán)，每次求得v0到某個(gè)頂點(diǎn)v的最短路徑，并將v并入S集
?????min=INFINITY;?//?當(dāng)前所知離v0頂點(diǎn)的最近距離，設(shè)初值為∞
?????for（w=0;w???????if（!final[w]&&D[w]???????{
	?v=w;
	?if（v==v1）
		?flag=1;
	?min=D[w];
???????}
?????final[v]=TRUE;?//?將v并入S集
//下面語句輸出了經(jīng)過的路徑，剔除了不需要的頂點(diǎn)
	?if（flag==0）
	?printf（“%s->“G.vexs[v]）;
	?else?if（v==v1）
		?printf（“%s“G.vexs[v]）;//結(jié)束頂點(diǎn)

?????for（w=0;w???????if（!final[w]&&min???????{?//?w不屬于S集且v0→v→w的距離＜目前v0→w的距離
?????????D[w]=min+G.arcs[v][w].adj;?//?更新D[w]
	?for（j=0;j	???P[w][j]=P[v][j];
	?P[w][w]=TRUE;
???????}
???}
?}

?void?main（）
?{
???int?ijv0v1;
???int?stopflag=0;
???VertexType?ab;
???MGraph?g;
???PathMatrix?p;?//?二維數(shù)組，路徑矩陣
???ShortPathTable?d;?//?一維數(shù)組，最短距離表???
???printf（“輸入頂點(diǎn)信息時(shí)使用學(xué)校地點(diǎn)的代碼：\n“）;
???printf（“v0:前門；v1：后門；v2：圖書館；v3:教一樓\n“）;
???printf（“\n“）;
???printf（“v4:食堂；v5：操場；v6：實(shí)驗(yàn)樓；v7:學(xué)一樓\n“）;
???printf（“\n“）;
???printf（“v8:水房；v9：學(xué)二；va：學(xué)三樓；vb:學(xué)四樓\n“）;
???printf（“\n“）;
???CreateUDN（g）;?//?構(gòu)造無向網(wǎng)g
???Display（g）;?//?輸出無向網(wǎng)g
??????do
???{
???printf（“輸入要查詢的兩個(gè)點(diǎn)（以空格隔開）：\n“）;
???scanf（“%s%s%*c“ab）;?//%*c吃掉回車符
??for（i=0;i???{
	???if（strcmp（g.vexs[i]a）==0）
		???v0=i;
	???if（strcmp（g.vexs[i]b）==0）
		???v1=i;
???}
??printf（“經(jīng)過的路徑為：“）;
???ShortestPath_DIJ（gv0v1pd）;//以g中位置為0的頂點(diǎn)為源點(diǎn)，球其到其余各頂點(diǎn)的最短距離。存于d中
???printf（“\n“）;
????printf（“%s到頂點(diǎn)%s的最短路徑長度為（若是-1，則表示沒有通路）：\n“ab）;
???for（i=0;i?????if（i!=0&&strcmp（g.vexs[i]b）==0）
	?{
		?if（d[i]>=INFINITY）
			?d[i]=-1;//若兩點(diǎn)間沒有通路，用“-1”表示
		?printf（“%s-%s:%d“g.vexs[v0]g.vexs[i]d[i]）;
	?}
	?printf（“\n“）;
	?printf（“輸入stopflag‘1‘為結(jié)束程序，‘0‘為繼續(xù)查詢：\n“）;
	?stopfla

?屬性????????????大小?????日期????時(shí)間???名稱
-----------?---------??----------?-----??----

?????文件????2223104??2009-04-23?16:58??5-daohang\daohang.ncb

?????文件????????887??2009-04-15?18:54??5-daohang\daohang.sln

????..A..H.?????18432??2009-04-23?16:58??5-daohang\daohang.suo

?????文件??????33280??2009-04-23?16:52??5-daohang\Debug\daohang.exe

?????文件?????335988??2009-04-23?16:52??5-daohang\Debug\daohang.ilk

?????文件?????510976??2009-04-23?16:52??5-daohang\Debug\daohang.pdb

?????文件??????31744??2009-04-22?19:08??5-daohang\Debug\tongxin.exe

?????文件?????330948??2009-04-22?19:08??5-daohang\Debug\tongxin.ilk

?????文件?????519168??2009-04-22?19:08??5-daohang\Debug\tongxin.pdb

?????文件??????11772??2009-04-23?16:52??5-daohang\tongxin\Debug\BuildLog.htm

?????文件????????621??2009-04-23?16:52??5-daohang\tongxin\Debug\daohang.exe.intermediate.manifest

?????文件??????39892??2009-04-23?16:52??5-daohang\tongxin\Debug\Main.obj

?????文件?????????65??2009-04-23?16:52??5-daohang\tongxin\Debug\mt.dep

?????文件????????621??2009-04-22?19:08??5-daohang\tongxin\Debug\tongxin.exe.intermediate.manifest

?????文件?????257024??2009-04-23?16:52??5-daohang\tongxin\Debug\vc90.idb

?????文件?????217088??2009-04-23?16:52??5-daohang\tongxin\Debug\vc90.pdb

?????文件???????2290??2009-04-23?14:52??5-daohang\tongxin\Graph.h

?????文件????????601??2009-04-15?19:09??5-daohang\tongxin\Graph_Matrix.h

?????文件???????4103??2009-04-23?16:52??5-daohang\tongxin\Main.cpp

?????文件???????3783??2009-04-22?19:14??5-daohang\tongxin\tongxin.vcproj

?????文件???????1411??2009-04-23?16:58??5-daohang\tongxin\tongxin.vcproj.Dave-PC.文刀.user

?????文件????1174528??2009-04-22?20:22??5-daohang\tongxin.ncb

?????文件?????122880??2009-05-13?17:07??5-校園導(dǎo)航.doc

?????目錄??????????0??2009-04-23?18:10??5-daohang\tongxin\Debug

?????目錄??????????0??2009-04-23?18:10??5-daohang\Debug

?????目錄??????????0??2009-04-23?18:10??5-daohang\tongxin

?????目錄??????????0??2009-04-23?18:10??5-daohang

-----------?---------??----------?-----??----

??????????????5841206????????????????????27



............此處省略0個(gè)文件信息