弗洛伊德演算法
求最短路徑
#include <iostream>
using namespace std;
#define MaxInt 32767 //表示極大值，即∞
#define MVNum 100 //最大頂點數
typedef char VerTexType; //假設頂點的資料型別為字符型
typedef int ArcType; //假設邊的權值型別為整型
int Path[MVNum][MVNum]; //最短路徑上頂點vj的前一頂點的序號
int D[MVNum][MVNum]; //記錄頂點vi和vj之間的最短路徑長度
//------------圖的鄰接矩陣---------------
typedef struct{
VerTexType vexs[MVNum]; //頂點表
ArcType arcs[MVNum][MVNum]; //鄰接矩陣
int vexnum,arcnum; //圖的當前點數和邊數
}AMGraph;
int LocateVex(AMGraph G , VerTexType v){
//確定點v在G中的位置
for(int i = 0; i < G.vexnum; ++i)
if(G.vexs[i] == v)
return i;
return -1;
}//LocateVex
void CreateUDN(AMGraph &G){
//采用鄰接矩陣表示法，創建有向網G
int i , j , k;
cout <<"請輸入總頂點數，總邊數，以空格隔開:";
cin >> G.vexnum >> G.arcnum; //輸入總頂點數，總邊數
cout << endl;
cout << "輸入點的名稱，如a" << endl;
for(i = 0; i < G.vexnum; ++i){
cout << "請輸入第" << (i+1) << "個點的名稱:";
cin >> G.vexs[i]; //依次輸入點的資訊
}
cout << endl;
for(i = 0; i < G.vexnum; ++i){ //初始化鄰接矩陣，邊的權值均置為極大值MaxInt
for(j = 0; j < G.vexnum; ++j){
if(j != i)
G.arcs[i][j] = MaxInt;
else
G.arcs[i][j] = 0;
}//for
}//for
cout << "輸入邊依附的頂點及權值，如a b 3" << endl;
for(k = 0; k < G.arcnum;++k){ //構造鄰接矩陣
VerTexType v1 , v2;
ArcType w;
cout << "請輸入第" << (k + 1) << "條邊依附的頂點及權值:";
cin >> v1 >> v2 >> w; //輸入一條邊依附的頂點及權值
i = LocateVex(G, v1); j = LocateVex(G, v2); //確定v1和v2在G中的位置，即頂點陣列的下標
G.arcs[i][j] = w; //邊<v1, v2>的權值置為w
}//for
}//CreateUDN
void ShortestPath_Floyed(AMGraph G){
//用Floyd演算法求有向網G中各對頂點i和j之間的最短路徑
int i , j , k ;
for (i = 0; i < G.vexnum; ++i) //各對結點之間初始已知路徑及距離
for(j = 0; j < G.vexnum; ++j){
D[i][j] = G.arcs[i][j];
if(D[i][j] < MaxInt && i != j) Path[i][j]=i; //如果i和j之間有弧，則將j的前驅置為i
else Path [i][j] = -1; //如果i和j之間無弧，則將j的前驅置為-1
}//for
for(k = 0; k < G.vexnum; ++k)
for(i = 0; i < G.vexnum; ++i)
for(j = 0; j < G.vexnum; ++j)
if(D[i][k] + D[k][j] < D[i][j]){ //從i經k到j的一條路徑更短
D[i][j] = D[i][k]+D[k][j]; //更新D[i][j]
Path[i][j] = Path[k][j]; //更改j的前驅為k
}//if
}//ShortestPath_Floyed
void DisplayPath(AMGraph G , int begin ,int temp ){
//顯示最短路徑
if(Path[begin][temp] != -1){
DisplayPath(G , begin ,Path[begin][temp]);
cout << G.vexs[Path[begin][temp]] << "-->";
}
}//DisplayPath
int main(){
cout << "************演算法6.11 弗洛伊德演算法**************" << endl << endl;
AMGraph G;
char start , destination;
int num_start , num_destination;
CreateUDN(G);
cout <<endl;
cout << "有向網G創建完成！" << endl;
ShortestPath_Floyed(G);
cout << "請依次輸入路徑的起點與終點的名稱：";
cin >> start >> destination;
num_start = LocateVex(G , start);
num_destination = LocateVex(G , destination);
DisplayPath(G , num_start , num_destination);
cout << G.vexs[num_destination] << endl;
cout << "最短路徑的長度為：" << D[num_start][num_destination] << endl;
cout <<endl;
}//main
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/115734.html
標籤：其他
下一篇：實作有序表二分查找