用户登录
用户注册

分享至

弗洛伊德算法图文详解

  • 作者: 菊爽开塞露专卖旗舰店
  • 来源: 51数据库
  • 2022-09-23

弗洛伊德算法能够在指定图结构中找到各个顶点之间的最短路径，该算法既适用于无向加权图，也适用于有向加权图。

注意，弗洛伊德算法仅允许非环路的路径权值为负数。换句话说，如果图中某个环路的路径权值为负数，该算法将无法正常执行。

弗洛伊德算法的工作原理

弗洛伊德算法是基于动态规划思想实现的，我们以图 1 所示的有向加权图为例，给您演示该算法的工作原理。


图 1 有向加权图


1) 建立一张表格（如表 1 所示），记录图结构中各个路径的权值信息：

表 1 弗洛伊德算法_1
顶点1234
103∞5
220∞4
3∞10∞
4∞∞20


2) 将顶点 1 作为其它顶点之间最短路径必须经过的顶点，依次判断是否比表 1 中记录的路径值更小，如果更小，则表明顶点之间存在更短的路径，更新表 1 中的路径数据。

也就是说，依次判断以下这些路径的权值是否比表 1 记录的权值更小：

  • 2-1-3 权值为 2 + ∞ = ∞，表 1 中记录的 2-3 的路径值也是 ∞，因此不更新；

  • 2-1-4 权值为 2 + 5 = 7，表 1 中记录的 2-4 的路径值为 4， 7 > 4，因此不更新；

  • 3-1-2 权值为 ∞ + 3，不更新；

  • 3-1-4 权值为 ∞ + 5，不更新；

  • 4-1-2 权值为 ∞ + 3，不更新；

  • 4-1-3 权值为 ∞ + ∞，不更新。 


由此断定，以顶点 1 作为中间顶点，并不能使其它各顶点之间路径的权值更小。

3) 将顶点 2 作为其它顶点之间最短路径必须经过的顶点，依次判断是否比表 1 中记录的路径值更小：

  • 1-2-3 权值为 3 + ∞，不更新；

  • 1-2-4 权值为 3 + 4 = 7，表 1 中 1-4 的权值为 5，7 > 5，不更新； 

  • 3-2-1 权值为 1 + 2 = 3，表 1 中 3-1 的权值为 ∞，前者更短；

  • 3-2-4 权值为 1 + 4 = 5，表 1 中 3-4 的权值为 ∞，前者更短；

  • 4-2-1 权值为 ∞ + 2，不更新；

  • 4-2-3 权值为 ∞ + ∞，不更新。


因此，我们找到了比 3-1、3-4 更短的路径，下表对表 1 进行了更新：

表 2 弗洛伊德算法_2
顶点1234
103∞5
220∞4
33（3-2-1）105（3-2-4）
4∞∞20


4) 将顶点 3 作为其它顶点之间最短路径必须经过的顶点，依次判断是否比表 2 中记录的路径值更小：

  • 1-3-2 权值为 ∞ + 1，不更新；

  • 1-3-4 权值为 ∞ + 5，不更新；

  • 2-3-1 权值为 ∞ + 3，不更新；

  • 2-3-4 权值为 ∞ + 5，不更新；

  • 4-3-1 权值为 2 + 3 = 5，表 2 中 4-1 的权值为 ∞，前者更短；

  • 4-3-2 权值为 2 + 1 = 3，表 2 中 4-2 的权值为 ∞，前者更短；


因此，我们找到了比 4-1 和 4-2 更短的路径，下表对表 2 进行了更新：

表 3 弗洛伊德算法_3
顶点1234
103∞5
220∞4
33（3-2-1）105（3-2-4）
45（4-3-2-1）3（4-3-2）20


5) 将顶点 4 作为其它顶点之间最短路径必须经过的顶点，依次判断是否比表 3 中记录的路径值更小：

  • 1-4-2 权值为 5 + 3 = 8，表 3 中 1-2 的权值为 3，不更新；

  • 1-4-3 权值为 5 + 2 = 7，表 3 中 1-3 的权值为 ∞，前者更短；

  • 2-4-1 权值为 4 + 5 = 9，表 3 中 2-1 的权值为 2，不更新；

  • 2-4-3 权值为 4 + 2 = 6，表 3 中 2-3 的权值为 ∞，前者更短；

  • 3-4-1 权值为 4 + 5 = 9，表 3 中 3-1 的权值为 3，不更新；

  • 3-4-2 权值为 5 + 5 = 10 ，表 3 中 3-2 的权值为 1，不更新。


因此，我们找到了比 1-3 和 2-3 更短的路径，下表对表 3 进行了更新：

表 4 弗洛伊德算法_4
顶点1234
1037（1-4-3）5
2206（2-4-3）4
33（3-2-1）105（3-2-4）
45（4-3-2-1）3（4-3-2）20


表 4 中记录的就是各个顶点之间的最短路径。

弗洛伊德算法的具体实现

如下的 C 语言程序实现了用弗洛伊德算法查找图 1 中所有顶点之间的最短路径：

#include <stdio.h>
#define V 4    //设定图中的顶点数
#define INF 65535   // 设置一个最大值
int P[V][V] = { 0 }; //记录各个顶点之间的最短路径
void printMatrix(int matrix[][V]);  //输出各个顶点之间的最短路径
void printPath(int i, int j); // 递归输出各个顶点之间最短路径的具体线路
void floydWarshall(int graph[][V]); // 实现弗洛伊德算法

int main() {
    // 有向加权图中各个顶点之间的路径信息
    int graph[V][V] = { {0, 3, INF, 5},
                          {2, 0, INF, 4},
                          {INF, 1, 0, INF},
                          {INF, INF, 2, 0} };
    floydWarshall(graph);
}
// 中序递归输出各个顶点之间最短路径的具体线路
void printPath(int i, int j)
{
    int k = P[i][j];
    if (k == 0)
        return;
    printPath(i, k);
    printf("%d-", k + 1);
    printPath(k, j);
}
// 输出各个顶点之间的最短路径
void printMatrix(int graph[][V]) {
    int i, j;
    for (i = 0; i < V; i++) {
        for (j = 0; j < V; j++) {
            if (j == i) {
                continue;
            }
            printf("%d - %d: 最短路径为:", i + 1, j + 1);
            if (graph[i][j] == INF)
                printf("%s\n", "INF");
            else {
                printf("%d", graph[i][j]);
                printf("，依次经过：%d-", i + 1);
                //调用递归函数
                printPath(i, j);
                printf("%d\n", j + 1);
            }
        }
    }
}
// 实现弗洛伊德算法,graph[][V] 为有向加权图 
void floydWarshall(int graph[][V]) {
    int  i, j, k;
    //遍历每个顶点，将其作为其它顶点之间的中间顶点，更新 graph 数组
    for (k = 0; k < V; k++) {
        for (i = 0; i < V; i++) {
            for (j = 0; j < V; j++) {
                //如果新的路径比之前记录的更短，则更新 graph 数组
                if (graph[i][k] + graph[k][j] < graph[i][j]) {
                    graph[i][j] = graph[i][k] + graph[k][j];
                    //记录此路径
                    P[i][j] = k;
                }
            }
        }
    }
    // 输出各个顶点之间的最短路径
    printMatrix(graph);
}


如下的 Java 程序实现了用弗洛伊德算法查找图 1 中所有顶点之间的最短路径：

public class Floyd {
    static int V = 4; // 顶点的个数
    static int[][] P = new int[V][V]; // 记录各个顶点之间的最短路径
    static int INF = 65535; // 设置一个最大值

    // 中序递归输出各个顶点之间最短路径的具体线路
    public static void printPath(int i, int j) {
        int k = P[i][j];
        if (k == 0)
            return;
        printPath(i, k);
        System.out.print((k + 1) + "-");
        printPath(k, j);
    }

    // 输出各个顶点之间的最短路径
    public static void printMatrix(int[][] graph) {
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                if (j == i) {
                    continue;
                }
                System.out.print((i + 1) + " - " + (j + 1) + "：最短路径为:");
                if (graph[i][j] == INF)
                    System.out.println("INF");
                else {
                    System.out.print(graph[i][j]);
                    System.out.print("，依次经过：" + (i + 1) + "-");
                    // 调用递归函数
                    printPath(i, j);
                    System.out.println((j + 1));
                }
            }
        }
    }

    // 实现弗洛伊德算法,graph[][V] 为有向加权图
    public static void floydWarshall(int[][] graph) {
        int i, j, k;
        // 遍历每个顶点，将其作为其它顶点之间的中间顶点，更新 graph 数组
        for (k = 0; k < V; k++) {
            for (i = 0; i < V; i++) {
                for (j = 0; j < V; j++) {
                    // 如果新的路径比之前记录的更短，则更新 graph 数组
                    if (graph[i][k] + graph[k][j] < graph[i][j]) {
                        graph[i][j] = graph[i][k] + graph[k][j];
                        // 记录此路径
                        P[i][j] = k;
                    }
                }
            }
        }
        // 输出各个顶点之间的最短路径
        printMatrix(graph);
    }

    public static void main(String[] args) {
        // 有向加权图中各个顶点之间的路径信息
        int[][] graph = new int[][] { { 0, 3, INF, 5 }, { 2, 0, INF, 4 }, { INF, 1, 0, INF }, { INF, INF, 2, 0 } };
        floydWarshall(graph);
    }
}


如下的 Python 程序实现了用弗洛伊德算法查找图 1 中所有顶点之间的最短路径：

V = 4   # 顶点的个数
INF = 65535    # 设定一个最大值
P = [[0]*V for i in range(V)] # 记录各个顶点之间的最短路径
# 有向加权图中各个顶点之间的路径信息
graph = [[0, 3, INF, 5],
         [2, 0, INF, 4],
         [INF, 1, 0, INF],
         [INF, INF, 2, 0]]
# 中序递归输出各个顶点之间最短路径的具体线路
def printPath(i,j):
    k = P[i][j]
    if k == 0:
        return;
    printPath(i , k)
    print("%d-" % (k + 1) , end='')
    printPath(k , j)
# 输出各个顶点之间的最短路径
def printMatrix(graph):
    for i in range(V):
        for j in range(V):
            if j == i:
                continue
            print("%d - %d: 最短路径为:"%(i + 1, j + 1) , end='')
            if graph[i][j] == INF:
                print("INF")
            else:
                print(graph[i][j] , end='')
                print("，依次经过：%d-"%(i+1) , end='')
                # 调用递归函数
                printPath(i , j)
                print(j + 1)
# 实现弗洛伊德算法,graph[][V] 为有向加权图
def floydWarshall(graph):
    # 遍历每个顶点，将其作为其它顶点之间的中间顶点，更新 graph 数组
    for k in range(V):
        for i in range(V):
            for j in range(V):
                # 如果新的路径比之前记录的更短，则更新 graph 数组
                if graph[i][k] + graph[k][j] < graph[i][j]:
                    graph[i][j] = graph[i][k] + graph[k][j]
                    # 记录此路径
                    P[i][j] = k
    # 输出各个顶点之间的最短路径
    printMatrix(graph)

floydWarshall(graph)


以上程序的输出结果均为：

1 - 2: 最短路径为:3，依次经过：1-2
1 - 3: 最短路径为:7，依次经过：1-4-3
1 - 4: 最短路径为:5，依次经过：1-4
2 - 1: 最短路径为:2，依次经过：2-1
2 - 3: 最短路径为:6，依次经过：2-4-3
2 - 4: 最短路径为:4，依次经过：2-4
3 - 1: 最短路径为:3，依次经过：3-2-1
3 - 2: 最短路径为:1，依次经过：3-2
3 - 4: 最短路径为:5，依次经过：3-2-4
4 - 1: 最短路径为:5，依次经过：4-3-2-1
4 - 2: 最短路径为:3，依次经过：4-3-2
4 - 3: 最短路径为:2，依次经过：4-3


推荐阅读
热点文章

Copyright 2018 51数据库(www.51sjk.com)

软件
前端设计
程序设计
Java相关