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

#include?
#include?

using?namespace?std;

//函數結果狀態碼
#define?OK????1
#define?ERROR?0

//常量定義?
#define?INFINITY?65535?//最大值?
#define?MAXSIZE?????20?//最大頂點個數
#define?MAX????????100

//Status是函數的類型，其值是函數結果狀態代碼
typedef?int?Status;

//-----?有向無環圖的鄰接矩陣表示法?-----
typedef?struct?{
????char?vexs?[MAXSIZE];????????????//頂點向量?
????int?weight?[MAXSIZE][MAXSIZE];??//鄰接矩陣：用權值表示?
????int?vexnum?arcnum;?????????????//圖當前的頂點數和弧數?
}?Graph;

//-----?最短路徑存儲結構?-----
typedef?struct?Path?{
????int?element;????//在頭結點表示最短路徑的長度，其他結點中表示最短路徑中對應頂點的下標?
????struct?Path?*next;??
}?Path;????

//函數功能：找到頂點在頂點向量中的下標
//返回值：若找到則返回此頂點在頂點向量中的下標，若沒找到則返回-1?
int?LocateVex?（Graph?G?char?v）
{
????int?i;
????
????for?（i?=?0;?i?????????if?（G.vexs?[i]?==?v）???
????????????return?i;??????????//若找到此頂點，則返回頂點對應的下標?
????
????return?-1;?????????????????//若沒找到此頂點，則返回-1
}

//函數功能：?計算輸入序列的長度并判斷有沒有頂點重復?
int?countVexs?（char?*?vertices）
{
	int?i?j;
	//先判斷有輸入的頂點沒有重復??
	for?（i?=?0;i?	????for?（j?=?i?+?1;j?	????????if?（vertices?[i]?==?vertices?[j]）
	????????????return?ERROR;?????//若重復返回錯誤?
	
????for?（i?=?0;i?	return?i;
}

//函數功能：用鄰接矩陣表示法生成有向無環圖?
Status?CreateGraph?（Graph?&G）
{
????int?i?j?k?len;
????char?v1?v2;
????char?vertices?[MAX];?????????????????//儲存輸入的頂點?
????int?occupy?[MAXSIZE][MAXSIZE];???????//標記鄰接矩陣一條邊是否已經存在
????
????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））;
????
????//構造頂點向量
????do?{
????????cout?<????????cin??>>?vertices;????????????????//頂點向量先用一維數組vertices儲存?
????????len?=?countVexs?（vertices）;??????//計算輸入的頂點向量的長度，并判斷有沒有輸入的頂點重復?
????????if?（len?!=?G.vexnum）?????????????//若輸入不符合要求，提示重新輸入?
????????????cout?<????????else?{???????????????????????????//若輸入符合要求，將這些頂點賦值給頂點向量?
????????????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;??//弧的權值都賦值為無窮大
????????????occupy?[i][j]?=?0;???????????//弧的標記值都賦值為0?
????????}
????
????//輸入每一條弧依附的起點、終點和權值?
????for?（k?=?0;?k?????????do?{
????????????cout?<????????????cin??>>?v1?>>?v2;
????????????i?=?LocateVex?（G?v1）;
????????????j?=?LocateVex?（G?v2）;????????????
????????????if?（i?==?-1?||?j

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

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

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

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