Python基于Floyd算法求解最短路径距离问题实例详解
35 浏览量
2020-12-23
12:01:48
上传
评论 6
收藏 189KB PDF 举报
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()
剩余40页未读，继续阅读
资源评论
