Python基于Floyd算法求解最短路径距离问题实例详解

15 浏览量更新于2023-03-03 评论 1 收藏 190KB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

Python基于基于Floyd算法求解最短路径距离问题实例详解算法求解最短路径距离问题实例详解

主要介绍了Python基于Floyd算法求解最短路径距离问题,结合完整实例形式详细分析了Python使用Floyd算法求

解最短路径距离问题的相关操作技巧与注意事项,需要的朋友可以参考下

本文实例讲述了Python基于Floyd算法求解最短路径距离问题。分享给大家供大家参考，具体如下：

Floyd算法和Dijkstra算法，相信大家都不陌生，在最短路径距离的求解中应该算得上是最为基础和经典的两个算法了，今天就

用一点时间来重新实现一下，因为本科的时候学习数据结构才开始接触的这个算法，当时唯一会用的就是C语言了，现在的

话，C语言几乎已经离我远去了，个人感觉入手机器学习以来python更得我心，因为太通俗易懂了，带给你的体验自然也是非

常不错的。

当然网上有很多的算法讲解教程，我不会在这里累赘Floyd是什么原理，因为相信大家都熟悉，简单地说就是：三角不等式这

个核心思想，如果我要求顶点A到顶点B之间的距离的话，我可以先找一个顶点C，求解顶点A到顶点C加上顶点C到顶点B的距

离和，如何这个距离和小于顶点A直接到顶点B的距离的话，那么这个时候就要更新一下距离矩阵中的值，将顶点A到顶点B的

距离更新为：顶点A到顶点C加上顶点C到顶点B的距离和。这就是Folyd的核心思想了，那么如果要找到全局最优的解就要在

选取中间顶点的过程中遍历所有的节点才行，这样就是三层for循环的结构了，得到的时间复杂度就是O(n*n*n)，n为顶点的规

模，其实在具体实际的应用中，这个算法的性能还是很不错的对于求解小规模的图问题的时候，如果感兴趣的话可以把程序拿

去做实验试试，直接可以运行的，不依赖第三方的其他模块。

下面看具体的实现：

#!usr/bin/env python

#encoding:utf-8

'''''

__Author__:沂水寒城

功能：使用floyd算法求最短路径距离

'''

import random

import time

def random_matrix_genetor(vex_num=10):

'''''

随机图顶点矩阵生成器

输入：顶点个数，即矩阵维数

'''

data_matrix=[]

for i in range(vex_num):

one_list=[]

for j in range(vex_num):

one_list.append(random.randint(1, 100))

data_matrix.append(one_list)

return data_matrix

def floyd(data_matrix):

'''''

输入：原数据矩阵，即：一个二维数组

输出：顶点间距离

'''

dist_matrix=[]

path_matrix=[]

vex_num=len(data_matrix)

for h in range(vex_num):

one_list=['N']*vex_num

path_matrix.append(one_list)

dist_matrix.append(one_list)

for i in range(vex_num):

for j in range(vex_num):

dist_matrix=data_matrix

path_matrix[i][j]=j

for k in range(vex_num):

for i in range(vex_num):

for j in range(vex_num):

if dist_matrix[i][k]=='N' or dist_matrix[k][j]=='N':

temp='N'

else:

temp=dist_matrix[i][k]+dist_matrix[k][j]

if dist_matrix[i][j]>temp:

dist_matrix[i][j]=temp

path_matrix[i][j]=path_matrix[i][k]

return dist_matrix, path_matrix

def main_test_func(vex_num=10):

'''''

主测试函数

'''

data_matrix=random_matrix_genetor(vex_num)

dist_matrix, path_matrix=floyd(data_matrix)

for i in range(vex_num):

for j in range(vex_num):

print '顶点'+str(i)+'----->'+'顶点'+str(j)+'最小距离为:', dist_matrix[i][j]

if __name__ == '__main__':

data_matrix=[['N',1,'N',4],[1,'N',2,'N'],['N',2,'N',3],[4,'N',3,'N']]

dist_matrix, path_matrix=floyd(data_matrix)

print dist_matrix

print path_matrix

time_list=[]

print '------------------------------节点数为10测试情况------------------------------------'

start_time0=time.time()

main_test_func(10)

end_time0=time.time()

t1=end_time0-start_time0

time_list.append(t1)

print '节点数为10时耗时为：', t1

print '------------------------------节点数为100测试情况------------------------------------'

start_time1=time.time()

main_test_func(100)

end_time1=time.time()

t2=end_time1-start_time1

time_list.append(t2)

print '节点数为100时耗时为：', t2

print '------------------------------节点数为1000测试情况------------------------------------'

start_time1=time.time()

main_test_func(1000)

end_time1=time.time()

t3=end_time1-start_time1

time_list.append(t3)

print '节点数为100时耗时为：', t3

print '--------------------------------------时间消耗情况为：--------------------------------'

for one_time in time_list:

print one_time

实验结果很庞大，其中1000节点测试时间最久最耗时，简单看一下结果：

[[2, 1, 3, 4], [1, 2, 2, 5], [3, 2, 4, 3], [4, 5, 3, 6]]

[[1, 1, 1, 3], [0, 0, 2, 0], [1, 1, 1, 3], [0, 0, 2, 2]]

------------------------------节点数为10测试情况------------------------------------

顶点0----->顶点0最小距离为: 3

顶点0----->顶点1最小距离为: 46

顶点0----->顶点2最小距离为: 46

顶点0----->顶点3最小距离为: 12

顶点0----->顶点4最小距离为: 2

顶点0----->顶点5最小距离为: 17

顶点0----->顶点6最小距离为: 16

顶点0----->顶点7最小距离为: 12

顶点0----->顶点8最小距离为: 21

顶点0----->顶点9最小距离为: 12

顶点1----->顶点0最小距离为: 21

顶点1----->顶点1最小距离为: 42

顶点1----->顶点2最小距离为: 5

顶点1----->顶点3最小距离为: 26

顶点1----->顶点4最小距离为: 19

顶点1----->顶点5最小距离为: 17

顶点1----->顶点6最小距离为: 16

顶点1----->顶点7最小距离为: 12

顶点1----->顶点8最小距离为: 11

顶点1----->顶点9最小距离为: 33

顶点2----->顶点0最小距离为: 16

顶点2----->顶点1最小距离为: 55

顶点2----->顶点2最小距离为: 41

顶点2----->顶点3最小距离为: 21

顶点2----->顶点4最小距离为: 18

顶点2----->顶点5最小距离为: 12

顶点2----->顶点6最小距离为: 11

顶点2----->顶点7最小距离为: 7

顶点2----->顶点8最小距离为: 36

顶点2----->顶点9最小距离为: 28

顶点3----->顶点0最小距离为: 13

顶点3----->顶点1最小距离为: 34

顶点3----->顶点2最小距离为: 39

顶点3----->顶点3最小距离为: 25

顶点3----->顶点4最小距离为: 2

顶点3----->顶点5最小距离为: 9

顶点3----->顶点6最小距离为: 21

顶点3----->顶点7最小距离为: 21

顶点3----->顶点8最小距离为: 33

顶点3----->顶点9最小距离为: 25

顶点4----->顶点0最小距离为: 24

顶点4----->顶点1最小距离为: 67

顶点4----->顶点2最小距离为: 57

顶点4----->顶点3最小距离为: 36

顶点4----->顶点4最小距离为: 26

顶点4----->顶点5最小距离为: 20

顶点4----->顶点6最小距离为: 19

顶点4----->顶点7最小距离为: 36

顶点4----->顶点8最小距离为: 36

顶点4----->顶点9最小距离为: 36

顶点5----->顶点0最小距离为: 4

顶点5----->顶点1最小距离为: 50

顶点5----->顶点2最小距离为: 50

顶点5----->顶点3最小距离为: 16

顶点5----->顶点4最小距离为: 6

顶点5----->顶点5最小距离为: 21

顶点5----->顶点6最小距离为: 20

顶点5----->顶点7最小距离为: 16

顶点5----->顶点8最小距离为: 24

顶点5----->顶点9最小距离为: 16

顶点6----->顶点0最小距离为: 5

顶点6----->顶点1最小距离为: 51

顶点6----->顶点2最小距离为: 51

顶点6----->顶点3最小距离为: 17

顶点6----->顶点4最小距离为: 7

顶点6----->顶点5最小距离为: 1

顶点6----->顶点6最小距离为: 21

顶点6----->顶点7最小距离为: 17

顶点6----->顶点8最小距离为: 25

顶点6----->顶点9最小距离为: 17

顶点7----->顶点0最小距离为: 9

顶点7----->顶点1最小距离为: 54

顶点7----->顶点2最小距离为: 34

顶点7----->顶点3最小距离为: 21

顶点7----->顶点4最小距离为: 11

顶点7----->顶点5最小距离为: 5

顶点7----->顶点6最小距离为: 4

顶点7----->顶点7最小距离为: 21

顶点7----->顶点8最小距离为: 29

顶点7----->顶点9最小距离为: 21

顶点8----->顶点0最小距离为: 52

顶点8----->顶点1最小距离为: 31

顶点8----->顶点2最小距离为: 36

顶点8----->顶点3最小距离为: 57

顶点8----->顶点4最小距离为: 50

顶点8----->顶点5最小距离为: 48

顶点8----->顶点6最小距离为: 47

顶点8----->顶点7最小距离为: 43

顶点8----->顶点8最小距离为: 42

顶点8----->顶点9最小距离为: 58

顶点9----->顶点0最小距离为: 16

顶点9----->顶点1最小距离为: 40

顶点9----->顶点2最小距离为: 45

顶点9----->顶点3最小距离为: 28

顶点9----->顶点4最小距离为: 18

顶点9----->顶点5最小距离为: 33

顶点9----->顶点6最小距离为: 32

顶点9----->顶点7最小距离为: 28

顶点9----->顶点8最小距离为: 9

顶点9----->顶点9最小距离为: 8

节点数为10时耗时为： 0.00200009346008

------------------------------节点数为50测试情况------------------------------------

顶点0----->顶点0最小距离为: 12

顶点0----->顶点1最小距离为: 11

顶点0----->顶点2最小距离为: 12

顶点0----->顶点3最小距离为: 10

顶点0----->顶点4最小距离为: 4

顶点0----->顶点5最小距离为: 12

顶点0----->顶点6最小距离为: 8

顶点0----->顶点7最小距离为: 11

顶点0----->顶点8最小距离为: 11

顶点0----->顶点9最小距离为: 13

顶点0----->顶点10最小距离为: 6

顶点0----->顶点11最小距离为: 9

顶点0----->顶点12最小距离为: 10

顶点0----->顶点13最小距离为: 7

顶点0----->顶点14最小距离为: 12

顶点0----->顶点15最小距离为: 10

顶点0----->顶点16最小距离为: 12

顶点0----->顶点17最小距离为: 8

顶点0----->顶点18最小距离为: 18

顶点0----->顶点19最小距离为: 11

顶点0----->顶点20最小距离为: 11

顶点0----->顶点21最小距离为: 17

顶点0----->顶点22最小距离为: 12

顶点0----->顶点23最小距离为: 6

顶点0----->顶点24最小距离为: 12

顶点0----->顶点25最小距离为: 10

顶点0----->顶点26最小距离为: 12

顶点0----->顶点27最小距离为: 6

顶点0----->顶点28最小距离为: 3

顶点0----->顶点29最小距离为: 15

顶点0----->顶点30最小距离为: 9

顶点0----->顶点31最小距离为: 5

顶点0----->顶点32最小距离为: 11

顶点0----->顶点33最小距离为: 9

顶点0----->顶点34最小距离为: 7

顶点0----->顶点35最小距离为: 12

顶点0----->顶点36最小距离为: 5

顶点0----->顶点37最小距离为: 10

顶点0----->顶点38最小距离为: 15

顶点0----->顶点39最小距离为: 9

顶点0----->顶点40最小距离为: 11

顶点0----->顶点41最小距离为: 12

顶点0----->顶点42最小距离为: 11

顶点0----->顶点43最小距离为: 10

顶点0----->顶点44最小距离为: 8

顶点0----->顶点45最小距离为: 11

顶点0----->顶点46最小距离为: 6

顶点0----->顶点47最小距离为: 7

顶点0----->顶点48最小距离为: 14

顶点0----->顶点49最小距离为: 11

顶点1----->顶点0最小距离为: 18

顶点1----->顶点1最小距离为: 13

顶点1----->顶点2最小距离为: 15

顶点1----->顶点3最小距离为: 13

顶点1----->顶点4最小距离为: 18

顶点1----->顶点5最小距离为: 16

顶点1----->顶点6最小距离为: 18

顶点1----->顶点7最小距离为: 13

顶点1----->顶点8最小距离为: 14

顶点1----->顶点9最小距离为: 17

顶点1----->顶点10最小距离为: 8

顶点1----->顶点11最小距离为: 11

顶点1----->顶点12最小距离为: 16

顶点1----->顶点13最小距离为: 9

顶点1----->顶点14最小距离为: 18

顶点1----->顶点15最小距离为: 12

顶点1----->顶点16最小距离为: 16

顶点1----->顶点17最小距离为: 10

顶点1----->顶点18最小距离为: 20

顶点1----->顶点19最小距离为: 13

顶点1----->顶点20最小距离为: 16

顶点1----->顶点21最小距离为: 19

顶点1----->顶点22最小距离为: 16

顶点1----->顶点23最小距离为: 16

顶点1----->顶点24最小距离为: 15

顶点1----->顶点25最小距离为: 15

顶点1----->顶点26最小距离为: 14

顶点1----->顶点27最小距离为: 8

顶点1----->顶点28最小距离为: 5

顶点1----->顶点29最小距离为: 17

顶点1----->顶点30最小距离为: 12

顶点1----->顶点31最小距离为: 7

顶点1----->顶点32最小距离为: 21

顶点1----->顶点33最小距离为: 13

顶点1----->顶点34最小距离为: 16

顶点1----->顶点35最小距离为: 14

顶点1----->顶点36最小距离为: 17

顶点1----->顶点37最小距离为: 12

顶点1----->顶点38最小距离为: 17

顶点1----->顶点39最小距离为: 11

顶点1----->顶点40最小距离为: 10

顶点1----->顶点41最小距离为: 22

顶点1----->顶点42最小距离为: 13

顶点1----->顶点43最小距离为: 16

顶点1----->顶点44最小距离为: 14

顶点1----->顶点45最小距离为: 13

顶点1----->顶点46最小距离为: 12

顶点1----->顶点47最小距离为: 13

顶点1----->顶点48最小距离为: 12

顶点1----->顶点49最小距离为: 13

顶点2----->顶点0最小距离为: 7

顶点2----->顶点1最小距离为: 11

顶点2----->顶点2最小距离为: 8

顶点2----->顶点3最小距离为: 11

顶点2----->顶点4最小距离为: 5

顶点2----->顶点5最小距离为: 13

顶点2----->顶点6最小距离为: 8

顶点2----->顶点7最小距离为: 6

顶点2----->顶点8最小距离为: 8

顶点2----->顶点9最小距离为: 11

顶点2----->顶点10最小距离为: 7

顶点2----->顶点11最小距离为: 6

顶点2----->顶点12最小距离为: 5

顶点2----->顶点13最小距离为: 8

顶点2----->顶点14最小距离为: 13

顶点2----->顶点15最小距离为: 10

顶点2----->顶点16最小距离为: 7

顶点2----->顶点17最小距离为: 9

顶点2----->顶点18最小距离为: 13

顶点2----->顶点19最小距离为: 8

顶点2----->顶点20最小距离为: 6

顶点2----->顶点21最小距离为: 13

顶点2----->顶点22最小距离为: 13

顶点2----->顶点23最小距离为: 6

顶点2----->顶点24最小距离为: 12

顶点2----->顶点25最小距离为: 5

顶点2----->顶点26最小距离为: 11

顶点2----->顶点27最小距离为: 6

顶点2----->顶点28最小距离为: 4

顶点2----->顶点29最小距离为: 10

顶点2----->顶点30最小距离为: 10

顶点2----->顶点31最小距离为: 6

顶点2----->顶点32最小距离为: 11

顶点2----->顶点33最小距离为: 10

顶点2----->顶点34最小距离为: 8

顶点2----->顶点35最小距离为: 13

顶点2----->顶点36最小距离为: 6

剩余40页未读，继续阅读

weixin_38641339

粉丝: 12
资源: 927

会员权益专享

Python基于Floyd算法求解最短路径距离问题实例详解

评论0

会员权益专享

最新资源

Python基于Floyd算法求解最短路径距离问题实例详解

评论0

python实现Floyd算法

弗洛伊德（Floyd）算法求任意两点间的最短路径

图论基本算法python实现

列举15个以上的Floyd算法在最短路径问题中的应用研究的 中文文献

用floyd算法解决最短路径问题

floyd算法输出最短路径

floyd算法求最短路径问题matlab

floyd算法求最短路径matlab

floyd算法求最短路径

floyd算法求最短路径问题

基于dijsktra算法的最短路径求解 实验

floyd算法求最短路径python

Floyd方法python算法实现最短路径实例

floyd算法求最短路径c++

除了Floyd算法还能用什么算法实现最短路径问题

flody算法求解最短路径

floyd算法求最短路径c

pycharm最短路径算法

Floyd算法在最短路径问题的应用研究

python实现最短路径的实例方法

会员权益专享

最新资源

列举15个以上的Floyd算法在最短路径问题中的应用研究的中文文献

基于dijsktra算法的最短路径求解实验