6-3 最短路径（弗洛伊德算法）

6-3 最短路径（弗洛伊德算法） (15 分)
试实现弗洛伊德最短路径算法。

函数接口定义：

void ShortestPath_Floyed(AMGraph G);

其中 G 是基于邻接矩阵存储表示的有向图。

裁判测试程序样例：

#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;

void CreateUDN(AMGraph &G);//实现细节隐藏
void ShortestPath_Floyed(AMGraph G);

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]< 
输入样例：
 第1行输入结点数vexnum和边数arcnum。第2行输入vexnum个字符表示结点的值，接下来依次输入arcnum行，每行输入3个值，前两个字符表示结点，后一个数表示两个结点之间边的权值。最后一行输入源点及终点。
 
6 8
 012345
 0 5 100
 0 2 10
 0 4 30
 1 2 5
 2 3 50
 3 5 10
 4 3 20
 4 5 60
 0 5
 结尾无空行
 输出样例：
 第一行输出源点到终点的最短路径，第二行输出源点到终点的最短路径距离。
 
0->4->3->5
 60
 结尾无空行
 
 
C++（g++）
 
void ShortestPath_Floyed(AMGraph G)
{
	int i,j,k,n=G.vexnum;
	for(i=0;i