利用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

网络可视化展示