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 randomimport timedef 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_matrixdef 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_matrixdef 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