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

本文实例讲述了Python基于Floyd算法求解最短路径距离问题。分享给大家供大家参考，具体如下： Floyd算法和Dijkstra算法，相信大家都不陌生，在最短路径距离的求解中应该算得上是最为基础和经典的两个算法了，今天就用一点时间来重新实现一下，因为本科的时候学习数据结构才开始接触的这个算法，当时唯一会用的就是C语言了，现在的话，C语言几乎已经离我远去了，个人感觉入手机器学习以来python更得我心，因为太通俗易懂了，带给你的体验自然也是非常不错的。 当然网 0 Comments

本文实例讲述了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为顶点的规模，其实在具体实际的应用中，这个算法的性能还是很不错的对于求解小规模的图问题的时候，如果感兴趣的话可以把程序拿去做实验试试，直接可以运行的，不依赖第三方的其他模块。

下面看具体的实现：

?

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

#!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节点测试时间最久最耗时，简单看一下结果：

从结果分析可以看到：

节点数量变为5倍的时候，时间变为80倍

节点为100的时候，结果太多已经没有办法也没有意义贴出来了只是简单贴一下时间：

第一个时间是节点数为10的时候的情况，第二个时间是节点数变为10倍的时候的情况，时间变为原来的将近700倍

由这些简单的实验分析可以大概推知：

在节点数量级比较小一般不超过10的3次方的时候性能还是可以的，只不过时间变化的曲线会很陡峭，当节点数目进一步增大的时候，时间消耗会变得难以忍受。

好了，关于Floyd算法的学习和实践就到这里了，如果感兴趣的欢迎交流。

希望本文所述对大家Python程序设计有所帮助。

原文链接：https://blog.csdn.net/together_cz/article/details/74608829

本文链接：https://my.lmcjl.com/post/3499.html

展开阅读全文

相关文章

4 评论

留下您的评论.