当前位置:   article > 正文

利用Floyd算法求解最短路径问题_floyd算法求最短路径问题

floyd算法求最短路径问题

利用Floyd算法求解最短路径问题

1、最短路径问题

从图中的某个顶点出发到达另一个顶点所经过的边的权重和最小的一条路径,成为最短路径

解决问题算法常见的有三种:

  1. Dijstra算法
  2. SPFA算法
  3. Floyd算法

本文介绍Floyd算法,利用python编程,利用Floyd算法求解最短路径问题,并生成可视化图分析

2、Floyd算法

算法思想:逐个顶点试探

3、经典最短路径求解例题

在这里插入图片描述

python Floyd算法 源代码

import pandas as pd, numpy as np, matplotlib.pyplot as plt, networkx as nx


# 最短路径计算模块
class Shortest_path_pro(object):
    # 初始化函数
    def __init__(self, start_node, end_node, directivity=1):
        # 无穷大表示
        self.M = np.inf
        # 有向图还是无向图
        self.directivity = directivity
        # 获取权矩阵
        self.weight_df = self.get_weight_df()
        # 获取路径矩阵
        self.S_df = self.get_S_df()
        # 获取路径矩阵
        [self.last_weight_df, self.last_S_df] = self.Floyd(self.weight_df, self.S_df)
        # 展示结果
        print("利用Floyd算法计算过程如下")
        strs = "-" * 20
        key_list = [key for key in self.weigth_df_dict.keys()]
        key1_list = [key1 for key1 in self.S_df_dict.keys()]
        for k in range(len(key_list)):
            print(f"{strs}{key_list[k]}{strs}")
            print(self.weigth_df_dict[key_list[k]].replace(self.M, "∞"))
            print(f"{strs}{key1_list[k]}{strs}")
            print(self.S_df_dict[key1_list[k]])
        print(f"{strs}迭代完成{strs}")
        print(f"{strs}最终结果如下{strs}")
        # 输出最短路径
        self.shortest_path = self.get_shortest_path(start_node, end_node)
        print("最短路径为:")
        i = 1
        n = len(self.shortest_path)
        for node in self.shortest_path:
            if i < n:
                print(f"Node{node}->", end="")
                i += 1
            else:
                print(f"Node{node}", end="")
        # 绘图
        self.network_graph(self.weight_edge_list)

    # 获取路径矩阵
    def get_S_df(self):
        S_df = pd.DataFrame([[i + 1 for i in range(len(self.weight_df.index.tolist()))] for j in
                             range(len(self.weight_df.index.tolist()))],
                            index=[f"Node{i + 1}" for i in range(len(self.weight_df.index.tolist()))],
                            columns=[f"Node{i + 1}" for i in range(len(self.weight_df.index.tolist()))])
        return S_df

    # 获取权矩阵
    def get_weight_df(self):
        # 赋权边
        self.weight_edge_list = []
        # 有向图
        if self.directivity == 1:
            node_number = int(input("请输入节点个数:"))
            edge_number = int(input("请输入弧数:"))
            self.node_number = node_number
            # 构造空的路径矩阵
            W_df = pd.DataFrame(index=[f"Node{i + 1}" for i in range(node_number)],
                                columns=[f"Node{i + 1}" for i in range(node_number)])
            for k in range(edge_number):
                print(f"{k + 1}条边的两个端点为:")
                startnode = int(input(f"起点:"))
                print("->", end="")
                endnode = int(input(f"终点:"))
                weight = int(input(f"权重:"))
                self.weight_edge_list.append((startnode, endnode, weight))
                W_df.iloc[startnode - 1, endnode - 1] = weight
            for i in range(node_number):
                for j in range(node_number):
                    if i == j:
                        W_df.iloc[i, j] = 0
            W_df = W_df.replace(np.nan, self.M)
            return W_df
        # 无向图
        else:
            node_number = int(input("请输入节点个数:"))
            edge_number = int(input("请输入边数:"))
            # 构造空的路径矩阵
            W_df = pd.DataFrame(index=[f"Node{i + 1}" for i in range(node_number)],
                                columns=[f"Node{i + 1}" for i in range(node_number)])
            for k in range(edge_number):
                print(f"{k + 1}条边的两个端点为:")
                startnode = int(input(f"左端点:"))
                print("->", end="")
                endnode = int(input(f"右端点:"))
                weight = int(input(f"权重:"))
                self.weight_edge_list.append((startnode, endnode, weight))
                W_df.iloc[startnode, endnode] = weight
                W_df.iloc[endnode, startnode] = weight
            for i in range(node_number):
                for j in range(node_number):
                    if i == j:
                        W_df.iloc[i, j] = 0
            W_df = W_df.replace(np.nan, self.M)
            return W_df

    #  Floyd算法实现
    def Floyd(self, weight_df0, S_df0):
        n = self.node_number
        self.weigth_df_dict = {"D(0)": weight_df0}
        self.S_df_dict = {"S(0)": S_df0}
        k = 1
        while k <= n:
            next_weight_df = pd.DataFrame(index=[f"Node{i + 1}" for i in range(n)],
                                          columns=[f"Node{j + 1}" for j in range(n)])
            next_S_df = pd.DataFrame(index=[f"Node{i + 1}" for i in range(n)],
                                     columns=[f"Node{j + 1}" for j in range(n)])
            for i in range(n):
                for j in range(n):
                    next_weight_df.iloc[i, j] = min(
                        [weight_df0.iloc[i, j], weight_df0.iloc[i, k - 1] + weight_df0.iloc[k - 1, j]])
            for i in range(n):
                for j in range(n):
                    if weight_df0.iloc[i, j] <= weight_df0.iloc[i, k - 1] + weight_df0.iloc[k - 1, j]:
                        next_S_df.iloc[i, j] = S_df0.iloc[i, j]
                    elif weight_df0.iloc[i, j] > weight_df0.iloc[i, k - 1] + weight_df0.iloc[k - 1, j]:
                        next_S_df.iloc[i, j] = S_df0.iloc[i, k - 1]
            weight_df0 = next_weight_df
            S_df0 = next_S_df
            self.weigth_df_dict.update({f"D({k})": weight_df0})
            self.S_df_dict.update({f"S({k})": S_df0})
            k += 1
        return [weight_df0, S_df0]

    # 获取最短路径和长度
    def get_shortest_path(self, start_node, end_node):
        path_list = [start_node]
        while 1:
            if self.last_S_df.iloc[start_node - 1, end_node - 1] != end_node:
                path_list.append(self.last_S_df.iloc[start_node - 1, end_node - 1])
                start_node = self.last_S_df.iloc[start_node - 1, end_node - 1]
            else:
                path_list.append(self.last_S_df.iloc[start_node - 1, end_node - 1])
                break
        return path_list

    # 绘制网络
    def network_graph(self, weight_edge_list):
        # 无向图
        if self.directivity == 0:
            G2 = nx.Graph()  # 创建无向图
            G2.add_weighted_edges_from(weight_edge_list)
            pos = nx.spring_layout(G2)  # 用 FR算法排列节点
            nx.draw(G2, pos, with_labels=True, alpha=0.5)
            labels = nx.get_edge_attributes(G2, 'weight')
            nx.draw_networkx_edge_labels(G2, pos, edge_labels=labels)
        # 有向图
        else:
            G2 = nx.DiGraph()  # 创建:空的 有向图
            G2.add_weighted_edges_from(weight_edge_list)  # 添加 带权边,weight表示边权
            # 添加 带权边,weight表示边权
            pos = nx.spring_layout(G2)  # 用 FR算法排列节点
            nx.draw(G2, pos, with_labels=True, alpha=0.5)
            labels = nx.get_edge_attributes(G2, 'weight')
            nx.draw_networkx_edge_labels(G2, pos, edge_labels=labels)
        edgeList = []
        for i in range(len(self.shortest_path) - 1):
            edgeList.append((self.shortest_path[i], self.shortest_path[i + 1]))
        nx.draw_networkx_edges(G2, pos, edgelist=edgeList, edge_color='m', width=4)  # 设置边的颜色
        plt.show()


# 脚本自调试
if __name__ == '__main__':
    start_node = int(input("请输入起始节点(如节点1,输入数字1,以此类推):"))
    end_node = int(input("请输入终止节点(如节点2,输入数字2,以此类推):"))
    # 实例化
    short = Shortest_path_pro(start_node, end_node)
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172

结果输出展示

C:\Users\Administrator\AppData\Local\Programs\Python\Python36\python.exe H:/python学习/GraphAndNetwork/Floyd_ShortesePayhPro.py
请输入起始节点(如节点1,输入数字1,以此类推):1
请输入终止节点(如节点2,输入数字2,以此类推):3
请输入节点个数:5
请输入弧数:8
1条边的两个端点为:
起点:1
->终点:2
权重:5
2条边的两个端点为:
起点:2
->终点:3
权重:6
3条边的两个端点为:
起点:2
->终点:5
权重:-3
4条边的两个端点为:
起点:3
->终点:5
权重:2
5条边的两个端点为:
起点:4
->终点:1
权重:4
6条边的两个端点为:
起点:4
->终点:3
权重:8
7条边的两个端点为:
起点:5
->终点:1
权重:4
8条边的两个端点为:
起点:5
->终点:4
权重:-2
利用Floyd算法计算过程如下
--------------------D(0)--------------------
      Node1 Node2 Node3 Node4 Node5
Node1     0     5     ∞     ∞     ∞
Node2     ∞     0     6     ∞    -3
Node3     ∞     ∞     0     ∞     2
Node4     4     ∞     8     0     ∞
Node5     4     ∞     ∞    -2     0
--------------------S(0)--------------------
       Node1  Node2  Node3  Node4  Node5
Node1      1      2      3      4      5
Node2      1      2      3      4      5
Node3      1      2      3      4      5
Node4      1      2      3      4      5
Node5      1      2      3      4      5
--------------------D(1)--------------------
      Node1 Node2 Node3 Node4 Node5
Node1     0     5     ∞     ∞     ∞
Node2     ∞     0     6     ∞    -3
Node3     ∞     ∞     0     ∞     2
Node4     4     9     8     0     ∞
Node5     4     9     ∞    -2     0
--------------------S(1)--------------------
      Node1 Node2 Node3 Node4 Node5
Node1     1     2     3     4     5
Node2     1     2     3     4     5
Node3     1     2     3     4     5
Node4     1     1     3     4     5
Node5     1     1     3     4     5
--------------------D(2)--------------------
      Node1 Node2  Node3 Node4  Node5
Node1     0     5   11.0     ∞    2.0
Node2     ∞     0    6.0     ∞   -3.0
Node3     ∞     ∞    0.0     ∞    2.0
Node4     4     9    8.0     0    6.0
Node5     4     9   15.0    -2    0.0
--------------------S(2)--------------------
      Node1 Node2 Node3 Node4 Node5
Node1     1     2     2     4     2
Node2     1     2     3     4     5
Node3     1     2     3     4     5
Node4     1     1     3     4     1
Node5     1     1     1     4     5
--------------------D(3)--------------------
      Node1 Node2  Node3 Node4  Node5
Node1     0     5   11.0     ∞    2.0
Node2     ∞     0    6.0     ∞   -3.0
Node3     ∞     ∞    0.0     ∞    2.0
Node4     4     9    8.0     0    6.0
Node5     4     9   15.0    -2    0.0
--------------------S(3)--------------------
      Node1 Node2 Node3 Node4 Node5
Node1     1     2     2     4     2
Node2     1     2     3     4     5
Node3     1     2     3     4     5
Node4     1     1     3     4     1
Node5     1     1     1     4     5
--------------------D(4)--------------------
      Node1 Node2  Node3 Node4  Node5
Node1     0     5   11.0     ∞    2.0
Node2     ∞     0    6.0     ∞   -3.0
Node3     ∞     ∞    0.0     ∞    2.0
Node4     4     9    8.0     0    6.0
Node5     2     7    6.0    -2    0.0
--------------------S(4)--------------------
      Node1 Node2 Node3 Node4 Node5
Node1     1     2     2     4     2
Node2     1     2     3     4     5
Node3     1     2     3     4     5
Node4     1     1     3     4     1
Node5     4     4     4     4     5
--------------------D(5)--------------------
       Node1  Node2  Node3  Node4  Node5
Node1    0.0    5.0    8.0    0.0    2.0
Node2   -1.0    0.0    3.0   -5.0   -3.0
Node3    4.0    9.0    0.0    0.0    2.0
Node4    4.0    9.0    8.0    0.0    6.0
Node5    2.0    7.0    6.0   -2.0    0.0
--------------------S(5)--------------------
      Node1 Node2 Node3 Node4 Node5
Node1     1     2     2     2     2
Node2     5     2     5     5     5
Node3     5     5     3     5     5
Node4     1     1     3     4     1
Node5     4     4     4     4     5
--------------------迭代完成--------------------
--------------------最终结果如下--------------------
最短路径为:
Node1->Node2->Node5->Node4->Node3
进程已结束,退出代码为 0
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127

网络可视化展示

在这里插入图片描述

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/代码探险家/article/detail/797426
推荐阅读
相关标签
  

闽ICP备14008679号