#include<iostream>

 using namespace std;

 #define MAXVEX 10

 #define INFINITY 65535

 typedef int Patharc[MAXVEX][MAXVEX];

 typedef int ShortPathTable[MAXVEX][MAXVEX];

 typedef struct {

     int vex[MAXVEX];

     int arc[MAXVEX][MAXVEX];

     int numVertexes;

 } MGraph;

 // 构建图

 void CreateMGraph(MGraph *G){

     int i, j, k;

     // 初始化图

     G->numVertexes = ;

     for(i = ; i < G->numVertexes; ++i){

         G->vex[i] = i;

     }

     for(i = ; i < G->numVertexes; ++i){

         for(j = ; j < G->numVertexes; ++j){

             if(i == j)

                 G->arc[i][j] = ;

             else

                 G->arc[i][j] = G->arc[j][i] = INFINITY;

         }

     }

     G->arc[][] = ;

     G->arc[][] = ;

     G->arc[][] = ;

     G->arc[][] = ;

     G->arc[][] = ;

     G->arc[][] = ;

     G->arc[][] = ;

     G->arc[][] = ;

     G->arc[][] = ;

     G->arc[][] = ;

     G->arc[][] = ;

     G->arc[][] = ;

     G->arc[][] = ;

     G->arc[][] = ;

     G->arc[][] = ;

     G->arc[][] = ;

     // 设置对称位置元素值

     for(i = ; i < G->numVertexes; ++i){

         for(j = i; j < G->numVertexes; ++j){

             G->arc[j][i] = G->arc[i][j];

         }

     }

 }

 // Floyd algorithm

 void ShortPath_Floyd(MGraph G, Patharc P, ShortPathTable D){

     int i, j, k;

     // 二重循环，初始化P, D

     for(i = ; i < G.numVertexes; ++i){

         for(j = ; j < G.numVertexes; ++j){

             D[i][j] = G.arc[i][j];

             P[i][j] = j;

         }

     }

     // 三重循环, Floyd algorithm

     for(k = ; k < G.numVertexes; ++k){

         for(i = ; i < G.numVertexes; ++i){

             for(j = ; j < G.numVertexes; ++j){

                 if(D[i][j] > D[i][k]+D[k][j]){

                     D[i][j] = D[i][k]+D[k][j];

                     P[i][j] = P[i][k];

                 }

             }

         }

     }

 }

 // 打印最短路径

 void PrintShortPath(MGraph G, Patharc P, ShortPathTable D){

     int i, j, k;

     cout<<"各顶点之间的最短路径如下: "<<endl;

     for(i = ; i < G.numVertexes; ++i){

         for(j = i+; j < G.numVertexes; ++j){

             cout<<"v"<<i<<"--"<<"v"<<j<<" "<<"weight: "<<D[i][j]<<"  Path: "<<i<<" -> ";

             k = P[i][j];

             while(k != j){

                 cout<<k<<" -> ";

                 k = P[k][j];

             }

             cout<<j<<endl;

         }

         cout<<endl;

     }

 }

 int main(int argc, char const *argv[]) {

     MGraph G;

     Patharc P;

     ShortPathTable D;

     CreateMGraph(&G);

     ShortPath_Floyd(G, P, D);

     PrintShortPath(G, P, D);

     return ;

 }

各顶点之间的最短路径如下:

v0--v1 weight:   Path:  ->

v0--v2 weight:   Path:  ->  ->

v0--v3 weight:   Path:  ->  ->  ->  ->

v0--v4 weight:   Path:  ->  ->  ->

v0--v5 weight:   Path:  ->  ->  ->  ->

v0--v6 weight:   Path:  ->  ->  ->  ->  ->

v0--v7 weight:   Path:  ->  ->  ->  ->  ->  ->

v0--v8 weight:   Path:  ->  ->  ->  ->  ->  ->  -> 

v1--v2 weight:   Path:  ->

v1--v3 weight:   Path:  ->  ->  ->

v1--v4 weight:   Path:  ->  ->

v1--v5 weight:   Path:  ->  ->  ->

v1--v6 weight:   Path:  ->  ->  ->  ->

v1--v7 weight:   Path:  ->  ->  ->  ->  ->

v1--v8 weight:   Path:  ->  ->  ->  ->  ->  -> 

v2--v3 weight:   Path:  ->  ->

v2--v4 weight:   Path:  ->

v2--v5 weight:   Path:  ->  ->

v2--v6 weight:   Path:  ->  ->  ->

v2--v7 weight:   Path:  ->  ->  ->  ->

v2--v8 weight:   Path:  ->  ->  ->  ->  -> 

v3--v4 weight:   Path:  ->

v3--v5 weight:   Path:  ->  ->

v3--v6 weight:   Path:  ->

v3--v7 weight:   Path:  ->  ->

v3--v8 weight:   Path:  ->  ->  -> 

v4--v5 weight:   Path:  ->

v4--v6 weight:   Path:  ->  ->

v4--v7 weight:   Path:  ->  ->  ->

v4--v8 weight:   Path:  ->  ->  ->  -> 

v5--v6 weight:   Path:  ->  ->

v5--v7 weight:   Path:  ->

v5--v8 weight:   Path:  ->  -> 

v6--v7 weight:   Path:  ->

v6--v8 weight:   Path:  ->  -> 

v7--v8 weight:   Path:  -> 

[Finished in .2s]