#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
/*
 * 代码实现<<大话数据结构>>p267 图7-7-13,和dijkstra算法同一张图
 * v0至v8分别用ABCDEFGHI代替
 * 时间复杂度O(n)^3, 虽然比dijkstra O(n)^2慢，但是可以求得任意顶点间的最短路径及开销
 */

#define MAX 9
#define INFINITY 65535
typedef int NextPoint[MAX][MAX]; // 存放v到w的最短路径时要先经过的顶点,非parent关系
typedef int PathMatrix[MAX][MAX]; // 存放各顶点间的最短路径开销, D数组

// 图结构体
typedef struct {
    char vexs[MAX]; // 顶点的数组，顶点类型为了简单使用char
    int arc[MAX][MAX]; // 边表二维数组，值为权
    int numVex;
}GRAPH, *PGRAPH;

void create(PGRAPH);
void gprint(GRAPH);
void addEdge(PGRAPH, int, int, int);
void floyd(GRAPH, PathMatrix *, NextPoint *);

void floyd(GRAPH graph, PathMatrix *D, NextPoint *P)
{
    int v, w, k;

    // 初始化D, P数组
    for (v=0; v<graph.numVex; v++) {
        for (w=0; w<graph.numVex; w++) {
            (*D)[v][w] = graph.arc[v][w];
            (*P)[v][w] = w;
        }
    }

    /* 开始循环查找最短路径，更新D P数组
       k为中转顶点，用于比对是否v经过k到w的开销比D数组中当前更小
       如果更小，则说明k更有可能存在于v到w最短路径上，更新D，及P
    */
    for (k=0; k<graph.numVex; k++) {
        // v行
        for (v=0; v<graph.numVex; v++) {
            // v行所有w列 
            for (w=0; w<graph.numVex; w++) {
                // 判断k是否有可能在v和w的最短路径上
                if ((*D)[v][w] > (*D)[v][k] + (*D)[k][w]) {
                    // 更新两点间的距离和
                    (*D)[v][w] = (*D)[v][k] + (*D)[k][w]; 
                    //因为k存在于v到w的路径上，所以v想要到w需要先经过 v到k要经过的顶点
                    (*P)[v][w] = (*P)[v][k]; 
                }
            }
        }
    }
}
void addEdge(PGRAPH g, int i, int j, int v)
{
    g->arc[i][j] = g->arc[j][i] = v;
}

void create(PGRAPH g)
{
    int i, j;

    g->numVex = 9;
    // 创建顶点
    g->vexs[0] = 'A';
    g->vexs[1] = 'B';
    g->vexs[2] = 'C';
    g->vexs[3] = 'D';
    g->vexs[4] = 'E';
    g->vexs[5] = 'F';
    g->vexs[6] = 'G';
    g->vexs[7] = 'H';
    g->vexs[8] = 'I';
    // 初始化边表矩阵
    for (i=0; i<g->numVex; i++) {
        for (j=0; j<g->numVex; j++) {
            g->arc[i][j] = INFINITY;
            if (j == i)
                g->arc[i][j] = 0; //行列相等时表示自身，标识为0
        }
    }
    // 添加边及权值
    // A v0, B v1, C v2, D v3, E v4, F v5, G v6, H v7, I, v8
    addEdge(g, 0, 1, 1);
    addEdge(g, 0, 2, 5);
    addEdge(g, 1, 2, 3);
    addEdge(g, 1, 4, 5);
    addEdge(g, 1, 3, 7);
    addEdge(g, 2, 4, 1);
    addEdge(g, 2, 5, 7);
    addEdge(g, 3, 4, 2);
    addEdge(g, 3, 6, 3);
    addEdge(g, 4, 5, 3);
    addEdge(g, 4, 7, 9);
    addEdge(g, 4, 6, 6);
    addEdge(g, 5, 7, 5);
    addEdge(g, 6, 7, 2);
    addEdge(g, 6, 8, 7);
    addEdge(g, 7, 8, 4);
}

void gprint(GRAPH graph)
{
    int i, j;
    for (i=0; i<graph.numVex; i++) {
        for (j=0; j<graph.numVex; j++){
            printf("%6d ", graph.arc[i][j]);
        }
        putchar('\n');
    }

}

int main(void)
{
    int i, j, k;
    GRAPH graph;
    NextPoint next_point;
    PathMatrix distance;

    create(&graph);
    gprint(graph);
    floyd(graph, &distance, &next_point);
    printf("D数组(任意顶点间的最短路径开销或者叫距离)\n");
    for (i=0; i<MAX; i++) {
        for (j=0; j<MAX; j++) {
            printf("%6d ", distance[i][j]);
        }
        putchar('\n');
    }
    printf("任意顶点间的最短路径:\n");
    for (i=0; i<MAX; i++) {
        for (j=i+1; j<MAX; j++) {
            printf("%d -> %d distance: %3d, path:", i, j, distance[i][j]);
            printf("%d->", i); // 先打印源点
            k = next_point[i][j];
            while (k != j) {
                printf("%d->", k);
                k = next_point[k][j]; // 相当于递归查找
            }
            printf("%d\n", k);
        }
    }

    return 0;
}

output

# gcc shortestPath_floyd.c && ./a.out
     0      1      5  65535  65535  65535  65535  65535  65535 
     1      0      3      7      5  65535  65535  65535  65535 
     5      3      0  65535      1      7  65535  65535  65535 
 65535      7  65535      0      2  65535      3  65535  65535 
 65535      5      1      2      0      3      6      9  65535 
 65535  65535      7  65535      3      0  65535      5  65535 
 65535  65535  65535      3      6  65535      0      2      7 
 65535  65535  65535  65535      9      5      2      0      4 
 65535  65535  65535  65535  65535  65535      7      4      0 
D数组(任意顶点间的最短路径开销或者叫距离)
     0      1      4      7      5      8     10     12     16 
     1      0      3      6      4      7      9     11     15 
     4      3      0      3      1      4      6      8     12 
     7      6      3      0      2      5      3      5      9 
     5      4      1      2      0      3      5      7     11 
     8      7      4      5      3      0      7      5      9 
    10      9      6      3      5      7      0      2      6 
    12     11      8      5      7      5      2      0      4 
    16     15     12      9     11      9      6      4      0 
任意顶点间的最短路径:
0 -> 1 distance:   1, path:0->1
0 -> 2 distance:   4, path:0->1->2
0 -> 3 distance:   7, path:0->1->2->4->3
0 -> 4 distance:   5, path:0->1->2->4
0 -> 5 distance:   8, path:0->1->2->4->5
0 -> 6 distance:  10, path:0->1->2->4->3->6
0 -> 7 distance:  12, path:0->1->2->4->3->6->7
0 -> 8 distance:  16, path:0->1->2->4->3->6->7->8
1 -> 2 distance:   3, path:1->2
1 -> 3 distance:   6, path:1->2->4->3
1 -> 4 distance:   4, path:1->2->4
1 -> 5 distance:   7, path:1->2->4->5
1 -> 6 distance:   9, path:1->2->4->3->6
1 -> 7 distance:  11, path:1->2->4->3->6->7
1 -> 8 distance:  15, path:1->2->4->3->6->7->8
2 -> 3 distance:   3, path:2->4->3
2 -> 4 distance:   1, path:2->4
2 -> 5 distance:   4, path:2->4->5
2 -> 6 distance:   6, path:2->4->3->6
2 -> 7 distance:   8, path:2->4->3->6->7
2 -> 8 distance:  12, path:2->4->3->6->7->8
3 -> 4 distance:   2, path:3->4
3 -> 5 distance:   5, path:3->4->5
3 -> 6 distance:   3, path:3->6
3 -> 7 distance:   5, path:3->6->7
3 -> 8 distance:   9, path:3->6->7->8
4 -> 5 distance:   3, path:4->5
4 -> 6 distance:   5, path:4->3->6
4 -> 7 distance:   7, path:4->3->6->7
4 -> 8 distance:  11, path:4->3->6->7->8
5 -> 6 distance:   7, path:5->7->6
5 -> 7 distance:   5, path:5->7
5 -> 8 distance:   9, path:5->7->8
6 -> 7 distance:   2, path:6->7
6 -> 8 distance:   6, path:6->7->8
7 -> 8 distance:   4, path:7->8