赞
踩
Floyd-Warshall 算法最初由 Robert W. Floyd 于 1962 年提出,之后由 Stephen Warshall 在 1962 年再次发现。Floyd 的原始论文标题为“算法97:最短路程问题”,而 Warshall 的文献中将其命名为 Floyd-Warshall 算法。
Floyd-Warshall 算法是用于解决所有节点对之间的最短路径问题的算法。该算法采用动态规划的思想,通过中间节点迭代更新每对节点之间的最短路径,其基本思想是将问题分解成许多子问题,并逐步解决这些子问题,最终得到全局最优解。
Floyd-Warshall 算法具有很高的效率和广泛的应用,是解决最短路径问题的重要算法之一,被广泛用于网络路由、城市交通规划、电路布线、物流配送等领域。同时,弗洛伊德算法也是其他算法(如 Dijkstra 算法)的基础,在一定程度上影响了后来的研究和发展。
下图所示为通过弗洛伊德算法求每对顶点间最短路径步骤:
视频讲解:
弗洛伊德算法
- //弗洛伊德算法
- void Floyd(AMGraph* G) {
- int distance[MVNum][MVNum];
- int i, j, k;
- //初始化距离矩阵
- for (i = 0; i < G->vexnum; i++) {
- for (j = 0; j < G->vexnum; j++) {
- distance[i][j] = G->arcs[i][j];
- }
- }
- //中间节点迭代
- for (k = 0; k < G->vexnum; k++) {
- for (i = 0; i < G->vexnum; i++) {
- for (j = 0; j < G->vexnum; j++) {
-
- if (distance[i][k] + distance[k][j] < distance[i][j]) {
- distance[i][j] = distance[i][k] + distance[k][j];
- }
- }
- }
- }
- //输出
- printf("每对顶点间的最短距离:\n");
- for (i = 0; i < G->vexnum; i++) {
- for (j = 0; j < G->vexnum; j++) {
- if (distance[i][j] == MaxInt) {
- printf("∞ ");
- }
- else {
- printf("%d ", distance[i][j]);
- }
- }
- printf("\n");
- }
- }
运行代码构造上图的无向网的邻接矩阵,输出最短距离矩阵:
- #define _CRT_SECURE_NO_WARNINGS 1
- #include <stdio.h>
- #include <stdbool.h>
- #include <malloc.h>
- #define MVNum 100//最大顶点数
- #define MaxInt 66666//表示极大值
- typedef struct {
- char vexs[MVNum];//顶点表(顶点为字符型)
- int arcs[MVNum][MVNum];//邻接矩阵(权值为整型)
- int vexnum, arcnum;//图的当前点数和边数
- }AMGraph;
-
- //定位
- int LocateVex(AMGraph* G, char v) {
- int i;
- for (i = 0; i < G->vexnum; i++) {
- if (G->vexs[i] == v) {
- return i;
- }
- }
- return -1;
- }
-
- //无向网的建立
- AMGraph* CreateUDN() {
- int i, j, k, w;
- char v1, v2;
- AMGraph* G = malloc(sizeof(AMGraph));
- printf("输入总顶点数,边数\n");
- scanf("%d%d", &G->vexnum, &G->arcnum);
- getchar();//吸收换行符
- printf("依次输入点的信息\n");
- for (i = 0; i < G->vexnum; i++) {
- scanf("%c", &G->vexs[i]);
- }
- getchar();//吸收换行符
- for (i = 0; i < G->vexnum; i++)
- for (j = 0; j < G->vexnum; j++) {
- if (i == j) {
- G->arcs[i][j] = 0;
- }
- else {
- G->arcs[i][j] = MaxInt;
- }
- }
- for (k = 0; k < G->arcnum; k++) {
- printf("输入一条边依附的顶点及权值\n");
- scanf("%c%c", &v1, &v2);
- scanf("%d", &w);
- getchar();//吸收换行符
- i = LocateVex(G, v1), j = LocateVex(G, v2);//确定v1、v2在顶点数组的下标
- G->arcs[i][j] = w;//边<v1,v2>权值置为w
- G->arcs[j][i] = w;//无向网对称边<v2,v2>权值也置为w
- }
- return G;
- }
-
- //输出邻接矩阵
- void print(AMGraph* G) {
- int i, j;
- printf(" ");
- for (i = 0; i < G->vexnum; i++) {
- printf("%c ", G->vexs[i]);
- }
- printf("\n");
- for (i = 0; i < G->vexnum; i++) {
- printf("%c ", G->vexs[i]);
- for (j = 0; j < G->vexnum; j++) {
- if (G->arcs[i][j] == MaxInt)
- printf("∞ ");
- else
- printf("%d ", G->arcs[i][j]);
- }
- printf("\n");
- }
- }
-
- //弗洛伊德算法
- void Floyd(AMGraph* G) {
- int distance[MVNum][MVNum];
- int i, j, k;
- //初始化距离矩阵
- for (i = 0; i < G->vexnum; i++) {
- for (j = 0; j < G->vexnum; j++) {
- distance[i][j] = G->arcs[i][j];
- }
- }
- //中间节点迭代
- for (k = 0; k < G->vexnum; k++) {
- for (i = 0; i < G->vexnum; i++) {
- for (j = 0; j < G->vexnum; j++) {
-
- if (distance[i][k] + distance[k][j] < distance[i][j]) {
- distance[i][j] = distance[i][k] + distance[k][j];
- }
- }
- }
- }
- //输出
- printf("每对顶点间的最短距离:\n");
- for (i = 0; i < G->vexnum; i++) {
- for (j = 0; j < G->vexnum; j++) {
- if (distance[i][j] == MaxInt) {
- printf("∞ ");
- }
- else {
- printf("%d ", distance[i][j]);
- }
- }
- printf("\n");
- }
- }
-
- int main() {
- AMGraph* G = CreateUDN();
- printf("该无向网邻接矩阵为:\n");
- print(G);
- Floyd(G);
- }
弗洛伊德算法是一种解决图中多源最短路径问题的算法,可以求出图中任意两个节点之间的最短路径长度。该算法的时间复杂度为,空间复杂度为。
需要指出的是,虽然弗洛伊德算法能够解决任意两个节点之间的最短路径问题,但在某些情况下可能不是最优解。因此,在实际使用中,需要根据具体需求选择合适的算法。
总之,弗洛伊德算法作为图论领域中的经典算法,其思想和方法都值得我们深入学习和掌握,以便能够更好地应对实际问题。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。