Floyd-Warshall算法--求任意两点最短距离

本文主要是介绍Floyd-Warshall算法--求任意两点最短距离，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Floyd-Warshall算法

要求

求任意两点之间最短的路径？

思路

使用之前学习的广度优先搜索或深度优先搜索对每两个点都进行一次搜索，共进行n^2次。

本次使用方法：引入中转点k，如果i到k的距离 + k到j的距离 < i到j的距离，更新i到j的最短距离，将每个点做为中转点更新距离后就可以得到任意两点最短距离。

代码

#include <stdio.h>#define N 5
#define M 5#define X 99999999int a[N][M] = {{ 0,  0,  0,  0,  0},{ 0,  0,  2,  6,  4},     { 0,  X,  0,  3,  X},     { 0,  7,  X,  0,  1},     { 0,  5,  X, 12,  0}    };void print_a() {for (int i = 0; i < N; ++i){for (int j = 0; j < M; ++j){printf("%3d ", a[i][j]);}printf("\n");}printf("\n");
}int main() {for (int k = 1; k < M; ++k){for (int i = 1; i < N; ++i){for (int j = 1; j < M; ++j){if (a[i][k] + a[k][j] < a[i][j]) {a[i][j] = a[i][k] + a[k][j];print_a();}}}}return 0;
}

时间复杂度

时间复杂度是O(N^3)

这篇关于Floyd-Warshall算法--求任意两点最短距离的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---