用Floyd算法求解下图各个顶点的最短距离

1. 问题

2.解析

Floyd算法：
设顶点集为v,边集为u
初始化：D[u,v]=A[u,v]
For k:=1 to n
For i:=1 to n
For j:=1 to n
If D[i,j]>D[i,k]+D[k,j] Then
D[i,j]:=D[i,k]+D[k,j];
c)　算法结束：D即为所有点对的最短距离矩阵

3.设计

Floyd算法：

#include<stdio.h>
#include<stdlib.h>
#define max 1000000000

int d[1000][1000], path[1000][1000];
int main()
{
    int i, j, k, m, n;
    int x, y, z;
    scanf_s("%d%d", &n, &m);         //输入点和边数

    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++) {
            d[i][j] = max;
            path[i][j] = j;
        }

    for (i = 1; i <= m; i++) {
        scanf_s("%d%d%d", &x, &y, &z);       //输入每两个点之间的带权路径
        d[x][y] = z;
        d[y][x] = z;
    }

    for (k = 1; k <= n; k++)
        for (i = 1; i <= n; i++)
            for (j = 1; j <= n; j++) {
                if (d[i][k] + d[k][j] < d[i][j]) {
                    d[i][j] = d[i][k] + d[k][j];
                    path[i][j] = path[i][k];
                }
            }
    for (i = 1; i <= n; i++)
        for (j = 1; j <= i; j++)
            if (i != j) printf("%d->%d:%d\n", i, j, d[i][j]);
    int f, en;
    scanf_s("%d%d", &f, &en);                 //输入想求路径的两个端点
    while (f != en) {
        printf("%d->", f);
        f = path[f][en];
    }
    printf("%d\n", en);
return 0;

4.分析

Floyd算法：
时间复杂度:O(n^3)；
空间复杂度:O(n^2)