创新互联www.cdcxhl.cn八线动态BGP香港云服务器提供商，新人活动买多久送多久，划算不套路！
这篇文章将为大家详细讲解有关用python实现最短路径的方法，小编觉得挺实用的，因此分享给大家做个参考，希望大家阅读完这篇文章后可以有所收获。
用python实现最短路径的方法：1、迪杰斯特拉算法：声明一个数组dis来保存源点到各个顶点的最短距离；2、弗洛伊德算法：在有向图中求解点与点之间最短路径；3、SPFA算法：用数组dis记录每个结点的最短路径估计值。
最短路径问题（python实现）
解决最短路径问题：（如下三种算法）
（1）迪杰斯特拉算法（Dijkstra算法）
（2）弗洛伊德算法（Floyd算法）
（3）SPFA算法
第一种算法：
Dijkstra算法
广度优先搜索解决赋权有向图或者无向图的单源最短路径问题.是一种贪心的策略
算法的思路
声明一个数组dis来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合：T，
初始时，原点s的路径权重被赋为0（dis[s]=0）。若对于顶点s存在能直接到达的边（s,m），则把dis[m]设为w（s, m）,
同时把所有其他（s不能直接到达的）顶点的路径长度设为无穷大。初始时，集合T只有顶点s。
然后，从dis数组选择最小值，则该值就是源点s到该值对应的顶点的最短路径，并且把该点加入到T中，OK，此时完成一个顶点，
再看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短，
如果是，那么就替换这些顶点在dis中的值，然后，又从dis中找出最小值，重复上述动作，直到T中包含了图的所有顶点。
第二种算法：
Floyd算法
原理：
Floyd算法（弗洛伊德算法）是一种在有向图中求最短路径的算法。它是一种求解有向图中点与点之间最短路径的算法。
用在拥有负权值的有向图中求解最短路径（不过不能包含负权回路）
流程：
有向图中的每一个节点X，对于图中过的2点A和B，
如果有Dis（AX）+ Dis（XB）< Dis（AB），那么使得Dis（AB）=Dis（AX）+Dis（XB)。
当所有的节点X遍历完后，AB的最短路径就求出来了。
示例一：
#-*- coding:utf-8 -*-
#python实现Floyd算法
N = 4
_=float('inf') #无穷大
graph = [[ 0, 2, 6, 4],[ _, 0, 3, _],[ 7, _, 0, 1],[ 5, _,12, 0]]
path = [[-1,-1,-1,-1],[-1,-1,-1,-1],[-1,-1,-1,-1],[-1,-1,-1,-1]] #记录路径，最后一次经过的点
def back_path(path,i,j): #递归回溯
while(-1 != path[i][j]):
back_path(path,i,path[i][j])
back_path(path,path[i][j],j)
print path[i][j],14
return;
return;
print "Graph:\n",graph
for k in range(N):
for i in range(N):
for j in range(N):
if graph[i][j] > graph[i][k] + graph[k][j]:
graph[i][j] = graph[i][k] + graph[k][j]
path[i][j] = k
print "Shortest distance:\n",graph
print "Path:\n",path
print "Points pass-by:"
for i in range(N):
for j in range(N):
print "%d -> %d:" % (i,j),
back_path(path,i,j)
print "\n",示例二：
#!usr/bin/env python#encoding:utf-8 ''' 功能：使用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_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
示例三：
