数据结构_图的应用_最短路径2（弗洛伊德算法）

#include<stdio.h>
#define MNUM 10
#define Arcnum 11
typedef struct
{
    int vexs[MNUM];
    int arcs[MNUM][MNUM];
    int vexnum, arcnum;
}Graph;
void Creat_graph(Graph * G)
{
    int i, j, m, n, q;
    scanf("%d %d", &G->vexnum, &G->arcnum);
    for(i = 0; i < G->vexnum; i++){
        G->vexs[i] = i;
    }
    for(i = 0; i < G->vexnum; i++){
        for(j = 0; j < G->vexnum; j++){
            if(i == j) G->arcs[i][j] = 0;
            else G->arcs[i][j] = 99;
        }
    }
    for(i = 0; i < G->arcnum; i++){
        scanf("%d %d %d", &m, &n, &q);
        G->arcs[m][n] = q;
        //G->arcs[n][m] = q;
    }
}
Graph G;

int (*ShortestPath_Floyd(Graph G))[2]
{
    int i, j, k;
    int Path[G.vexnum][G.vexnum];
    int Length[G.vexnum][G.vexnum];
    for(i = 0; i < G.vexnum; i++){
        for(j = 0; j < G.vexnum; j++){
            Length[i][j] = G.arcs[i][j];
            if(Length[i][j] < 99 && i != j) Path[i][j] = i;
            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(Length[i][k] + Length[k][j] < Length[i][j]){
                    Length[i][j] = Length[i][k] + Length[k][j];
                    Path[i][j] = Path[k][j];
                }
            }
        }
    }
    return Path;
}
void Print_Shortest_Path(int a, int b, int (*Path)[2])
{
    int i = 0, j, k;
    int path[10];
    path[i++] = b;
    while(a != Path[a][b]){
        b = Path[a][b];
        path[i++] = b;
    }
    path[i++] = a;
    while(i--){
        printf("%d ", path[i]);
    }

}

int main()
{
    Creat_graph(&G);
    int (*Path)[2];
    int i, j;
    for(i = 0; i < G.vexnum; i++){
        for(j = 0; j < G.vexnum; j++){
            if(G.arcs[i][j] < 10)
                printf("%d      ", G.arcs[i][j]);
            else
                printf("%d     ", G.arcs[i][j]);
        }
        putchar('\n');
    } //Êä³ö
    //MiniSpanTree_Kruskal(G);
    Path = ShortestPath_Floyd(G);
    Print_Shortest_Path(0, 3, Path);
    return 0;
}