floyd算法求最短路径

Floyd算法是一种经典的动态规划算法，用于求解所有节点对之间的最短路径。其基本思想是利用动态规划的思想，对于任意两个节点i和j，考虑它们之间是否存在中转节点k，如果存在，那么可以通过k来缩短i和j之间的距离，否则，i和j之间的距离就是它们之间的直接距离。

具体实现过程如下：

1. 初始化距离矩阵D：D[i][j]表示节点i到节点j的最短距离，如果i和j之间没有边相连，则D[i][j]=INF(无穷大)，否则等于边的权值。

2. 对于每一个节点k，遍历所有节点对(i,j)，如果D[i][j]>D[i][k]+D[k][j]，则更新D[i][j]=D[i][k]+D[k][j]。

3. 最终得到的D矩阵即为任意两个节点之间的最短距离。

以下是Floyd算法的C++实现代码：

const int INF=0x3f3f3f3f;
const int MAXN=1005;
int D[MAXN][MAXN];

void floyd(int n)
{
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                D[i][j]=min(D[i][j],D[i][k]+D[k][j]);
}

其中n表示节点的个数，D[i][j]表示节点i到节点j的最短距离。

相关问题

floyd算法求最短路径c

以下是使用C语言实现Floyd算法求最短路径的示例代码：

#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];
        }
    }
    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("INF ");
            } else {
                printf("%d ", dist[i][j]);
            }
        }
        printf("\n");
    }
}

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

输出结果为：

最短路径矩阵：
0 5 8 9 
INF 0 3 4 
INF INF 0 1 
INF INF INF 0 

floyd算法求最短路径c语言

以下是使用C语言实现Floyd算法求最短路径的示例代码：

#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];
        }
    }
    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("INF ");
            } else {
                printf("%d ", dist[i][j]);
            }
        }
        printf("\n");
    }
}

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