floyed算法c++

Floyd算法，也称为Floyd-Warshall算法，是一种用于寻找加权图中多源最短路径的算法。该算法的时间复杂度为O(n^3)，其中n表示图中节点的数量。

下面是Floyd算法的C语言实现：

#include <stdio.h> 
#define INF 99999 

void floyd(int graph[][4], int n) 
{ 
    int dist[n][n], i, j, k; 
    
    // 初始化距离矩阵
    for (i = 0; i < n; i++) 
        for (j = 0; j < n; j++) 
            dist[i][j] = graph[i][j]; 
    
    // 通过中间节点k更新距离矩阵
    for (k = 0; k < n; k++) 
    { 
        for (i = 0; i < n; i++) 
        { 
            for (j = 0; j < n; j++) 
            { 
                if (dist[i][k] + dist[k][j] < dist[i][j]) 
                    dist[i][j] = dist[i][k] + dist[k][j]; 
            } 
        } 
    } 
    
    // 输出结果
    printf ("最短路径如下所示:\n"); 
    for (i = 0; i < n; i++) 
    { 
        for (j = 0; j < n; j++) 
        { 
            if (dist[i][j] == INF) 
                printf("%7s", "INF"); 
            else
                printf ("%7d", dist[i][j]); 
        } 
        printf("\n"); 
    } 
} 

int main() 
{ 
    int graph[][4] = { {0, 5, INF, 10}, 
                       {INF, 0, 3, INF}, 
                       {INF, INF, 0, 1}, 
                       {INF, INF, INF, 0} }; 
    int n = 4; 
    floyd(graph, n); 
    return 0; 
}

这段代码实现了一个4个节点的图的Floyd算法，输出结果如下：

最短路径如下所示:
      0      5      8      9
    INF      0      3      4
    INF    INF      0      1
    INF    INF    INF      0

这表明从节点i到节点j的最短路径长度为dist[i][j]。如果dist[i][j]的值为INF，则表示从节点i到节点j不存在路径。