/*
??Name:?Floyd算法
??Copyright:?
??Author:冰人
??Date:?22-11-08?13:42
??Description:實(shí)現(xiàn)Floyd算法，并求出有向圖中各頂點(diǎn)之間的最短路徑及其長(zhǎng)度?
*/

#include?
#include?

using?namespace?std;

//函數(shù)結(jié)果狀態(tài)碼
#define?OK????1
#define?ERROR?0

//常量定義?
#define?INFINITY?65535?//最大值?
#define?MAXSIZE?????20?//最大頂點(diǎn)個(gè)數(shù)
#define?MAX????????100

//Status是函數(shù)的類(lèi)型，其值是函數(shù)結(jié)果狀態(tài)代碼
typedef?int?Status;

//-----?有向無(wú)環(huán)圖的鄰接矩陣表示法?-----
typedef?struct?{
????char?vexs?[MAXSIZE];????????????//頂點(diǎn)向量?
????int?weight?[MAXSIZE][MAXSIZE];??//鄰接矩陣：用權(quán)值表示?
????int?vexnum?arcnum;?????????????//圖當(dāng)前的頂點(diǎn)數(shù)和弧數(shù)?
}?Graph;

//-----?最短路徑存儲(chǔ)結(jié)構(gòu)?-----
typedef?struct?Path?{
????int?element;????//在頭結(jié)點(diǎn)表示最短路徑的長(zhǎng)度，其他結(jié)點(diǎn)中表示最短路徑中對(duì)應(yīng)頂點(diǎn)的下標(biāo)?
????struct?Path?*next;??
}?Path;????

//函數(shù)功能：找到頂點(diǎn)在頂點(diǎn)向量中的下標(biāo)
//返回值：若找到則返回此頂點(diǎn)在頂點(diǎn)向量中的下標(biāo)，若沒(méi)找到則返回-1?
int?LocateVex?（Graph?G?char?v）
{
????int?i;
????
????for?（i?=?0;?i?????????if?（G.vexs?[i]?==?v）???
????????????return?i;??????????//若找到此頂點(diǎn)，則返回頂點(diǎn)對(duì)應(yīng)的下標(biāo)?
????
????return?-1;?????????????????//若沒(méi)找到此頂點(diǎn)，則返回-1
}

//函數(shù)功能：?計(jì)算輸入序列的長(zhǎng)度并判斷有沒(méi)有頂點(diǎn)重復(fù)?
int?countVexs?（char?*?vertices）
{
	int?i?j;
	//先判斷有輸入的頂點(diǎn)沒(méi)有重復(fù)??
	for?（i?=?0;i?	????for?（j?=?i?+?1;j?	????????if?（vertices?[i]?==?vertices?[j]）
	????????????return?ERROR;?????//若重復(fù)返回錯(cuò)誤?
	
????for?（i?=?0;i?	return?i;
}

//函數(shù)功能：用鄰接矩陣表示法生成有向無(wú)環(huán)圖?
Status?CreateGraph?（Graph?&G）
{
????int?i?j?k?len;
????char?v1?v2;
????char?vertices?[MAX];?????????????????//儲(chǔ)存輸入的頂點(diǎn)?
????int?occupy?[MAXSIZE][MAXSIZE];???????//標(biāo)記鄰接矩陣一條邊是否已經(jīng)存在
????
????do?{
????????cout?<????????cin??>>?G.vexnum?>>?G.arcnum;
????????if?（G.vexnum?<=?0?||?G.vexnum?>?MAXSIZE?||?G.arcnum??G.vexnum*（G.vexnum-1））
????????????cout?<????}?while?（G.vexnum?<=?0?||?G.vexnum?>?MAXSIZE?||?G.arcnum??G.vexnum*（G.vexnum-1））;
????
????//構(gòu)造頂點(diǎn)向量
????do?{
????????cout?<????????cin??>>?vertices;????????????????//頂點(diǎn)向量先用一維數(shù)組vertices儲(chǔ)存?
????????len?=?countVexs?（vertices）;??????//計(jì)算輸入的頂點(diǎn)向量的長(zhǎng)度，并判斷有沒(méi)有輸入的頂點(diǎn)重復(fù)?
????????if?（len?!=?G.vexnum）?????????????//若輸入不符合要求，提示重新輸入?
????????????cout?<????????else?{???????????????????????????//若輸入符合要求，將這些頂點(diǎn)賦值給頂點(diǎn)向量?
????????????for?（i?=?0;?i?????????????????G.vexs?[i]?=?vertices?[i];
????????}
????}?while?（len?!=?G.vexnum）;????
????
????//初始化鄰接矩陣?
????for?（i?=?0;?i?????????for?（j?=?0;?j?????????????G.weight?[i][j]?=?INFINITY;??//弧的權(quán)值都賦值為無(wú)窮大
????????????occupy?[i][j]?=?0;???????????//弧的標(biāo)記值都賦值為0?
????????}
????
????//輸入每一條弧依附的起點(diǎn)、終點(diǎn)和權(quán)值?
????for?（k?=?0;?k?????????do?{
????????????cout?<????????????cin??>>?v1?>>?v2;
????????????i?=?LocateVex?（G?v1）;
????????????j?=?LocateVex?（G?v2）;????????????
????????????if?（i?==?-1?||?j

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

?????文件???????8563??2009-09-30?14:20??Floyd.cpp

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

?????????????????8563????????????????????1