/*輸入數(shù)據(jù)注意事項(xiàng)：
1，不要重復(fù)輸入相同結(jié)點(diǎn)之間但是不同的權(quán)重值。
2，權(quán)重值不要設(shè)為0
3，結(jié)點(diǎn)數(shù)不要小于4
//注意，程序求最短路徑的算法來自書本上的P181迪杰斯特拉算法
*/
#include?
#include?
#include?
#define?Max?8//改變一下這個(gè)值就可以
#define?MAXINIT?1000000//這代表一個(gè)足夠大的數(shù)，也可以成其他更大的數(shù)，不要超過32位系統(tǒng)的整型最大數(shù)即可
enum?boolean{FALSETRUE};
//首先定義一個(gè)圖的鄰接矩陣儲(chǔ)存結(jié)構(gòu)的類型
typedef?struct{
???int?vexs[Max];//頂點(diǎn)數(shù)組，
	int?arcs[Max][Max];//鄰接矩陣
	int?vexnumarcnum;//頂點(diǎn)數(shù)，邊數(shù)
}AdjMatrix;
//下面是實(shí)現(xiàn)求最短路徑的函數(shù)
//?s[Max];標(biāo)記那些已經(jīng)找到最短路徑的頂點(diǎn)集合，若s[i]=1則表示已經(jīng)找到源點(diǎn)到v[i]的最短路徑，若s[i]=0則表示尚未找到
//Dist[Max]用于記錄源點(diǎn)到其他頂點(diǎn)的當(dāng)前的最短距離即路徑長(zhǎng)度
//Path[Max]表示源點(diǎn)到v[i]的最短路徑的前驅(qū)頂點(diǎn)，若沒有路徑，則Path[i]=-1，
//path[v]表示從v0到v的最短路徑上v的前驅(qū)頂點(diǎn)
void?Dijkstra（AdjMatrix?gint?v0int?path[]int?dist[]）//vo是源點(diǎn)
{?
/*求有向圖g的從源點(diǎn)到其他頂點(diǎn)的最短路徑*/
	int?s[Max]viw1jmin;
	for（v=0;v	{s[v]=0;
	dist[v]=g.arcs[v0][v];
	if（dist[v]	??path[v]=v0;
	else
		path[v]=-1;
	}
	dist[v0]=0;s[v0]=1;//最開始時(shí)，s中只有v0這一個(gè)頂點(diǎn)
	/*循環(huán)求v0到某個(gè)頂點(diǎn)v的最短路徑，并將v加入s集*/
	for（i=0;i	{min=MAXINIT;
	?v=-1;//記錄找到的最小距離的定點(diǎn)序號(hào)
	?for（w1=0;w1	?if（!s[w1]&&dist[w1]	?{v=w1;
	??min=dist[w1];
	??
	?}
	?if（v!=-1）
	?{
	?s[v]=1;//將頂點(diǎn)v并入s中
	?for?（j=0;j