程序填空题：最短路径（弗洛伊德算法）
最短路径（弗洛伊德算法）。
```c++
#include
using namespace std;
#define MaxInt 32767
#define MVNum 100
typedef char VerTexType;
typedef int ArcType;
int Path[MVNum][MVNum];
int D[MVNum][MVNum];
typedef struct{
VerTexType vexs[MVNum];
ArcType arcs[MVNum][MVNum];
int vexnum,arcnum;
}AMGraph;
int LocateVex(AMGraph G , VerTexType v);//实现细节隐藏
void CreateUDN(AMGraph &G);//实现细节隐藏
void ShortestPath_Floyed(AMGraph G){
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]](2);
if(D[i][j] < MaxInt && i != j) @@[Path[i][j]=i](2);
else Path [i][j] = -1;
}
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]](2) < D[i][j]){
D[i][j] = @@[D[i][k]+D[k][j]](1);
Path[i][j] =@@[Path[k][j]](2);
}
}
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]] << "->";
}
}
int main(){
AMGraph G;
char start , destination;
int num_start , num_destination;
CreateUDN(G);
ShortestPath_Floyed(G);
cin >> start >> destination;
num_start = LocateVex(G , start);
num_destination = LocateVex(G , destination);
DisplayPath(G , num_start , num_destination);
cout << G.vexs[num_destination]< cout << D[num_start][num_destination];
return 0;
}
```
答案：
第1空：G.arcs[i][j]
第2空：Path[i][j]=i
第3空：D[i][k] + D[k][j]
第4空：D[i][k]+D[k][j]
第5空：Path[k][j]
```c++
#include
using namespace std;
#define MaxInt 32767
#define MVNum 100
typedef char VerTexType;
typedef int ArcType;
int Path[MVNum][MVNum];
int D[MVNum][MVNum];
typedef struct{
VerTexType vexs[MVNum];
ArcType arcs[MVNum][MVNum];
int vexnum,arcnum;
}AMGraph;
int LocateVex(AMGraph G , VerTexType v);//实现细节隐藏
void CreateUDN(AMGraph &G);//实现细节隐藏
void ShortestPath_Floyed(AMGraph G){
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]](2);
if(D[i][j] < MaxInt && i != j) @@[Path[i][j]=i](2);
else Path [i][j] = -1;
}
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]](2) < D[i][j]){
D[i][j] = @@[D[i][k]+D[k][j]](1);
Path[i][j] =@@[Path[k][j]](2);
}
}
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]] << "->";
}
}
int main(){
AMGraph G;
char start , destination;
int num_start , num_destination;
CreateUDN(G);
ShortestPath_Floyed(G);
cin >> start >> destination;
num_start = LocateVex(G , start);
num_destination = LocateVex(G , destination);
DisplayPath(G , num_start , num_destination);
cout << G.vexs[num_destination]<
return 0;
}
```
答案：
第1空：G.arcs[i][j]
第2空：Path[i][j]=i
第3空：D[i][k] + D[k][j]
第4空：D[i][k]+D[k][j]
第5空：Path[k][j]
