如何用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)。AB的最短路径是在所有节点X次之后找到的。
示例一：
#-*-coding:utf-8-*-
#floython实现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]
defback_path(path,i,j):#递归回溯
while(-1!=path[i][j]):
back_path(path,i,path[i][j])
back_path(path,path[i][j],j)
printpath[i][j],14
return;
return;
print"Graph:\n",graph
forkinrange(N):
foriinrange(N):
forjinrange(N):
ifgraph[i][j]>graph[i][k]+graph[k][j]:
graph[i][j]=graph[i][k]+graph[k][j]
path[i][j]=k
print"Shortestdistance:\n",graph
print"Path:\n",path
print"Pointspass-by:"
foriinrange(N):
forjinrange(N):
print"%d->%d:"%(i,j),
back_path(path,i,j)
print"\n",示例二：
#!usr/bin/envpython#encoding:utf-8 ''' 功能：使用floyd算法寻求最短的路径距离 ''' importrandom importtime defrandom_matrix_genetor(vex_num=10): ''' 随机图顶点矩阵生成器 输入：顶点数，即矩阵维数 ''' data_matrix=[] foriinrange(vex_num): one_list=[] forjinrange(vex_num): one_list.append(random.randint(1,100)) data_matrix.append(one_list) returndata_matrixdeffloyd(data_matrix): ''' 输入：原始数据矩阵，也就是说，二维数组 输出:顶点间距''' dist_matrix=[] path_matrix=[] vex_num=len(data_matrix) forhinrange(vex_num): one_list=['N']*vex_num path_matrix.append(one_list) dist_matrix.append(one_list) foriinrange(vex_num): forjinrange(vex_num): dist_matrix=data_matrix path_matrix[i][j]=j forkinrange(vex_num): foriinrange(vex_num): forjinrange(vex_num): ifdist_matrix[i][k]=='N'ordist_matrix[k][j]=='N': temp='N' else: temp=dist_matrix[i][k]+dist_matrix[k][j] ifdist_matrix[i][j]>temp: dist_matrix[i][j]=temp path_matrix[i][j]=path_matrix[i][k] returndist_matrix,path_matrixdefmain_test_func(vex_num=10): ''' 主测试函数 ''' data_matrix=random_matrix_genetor(vex_num) dist_matrix,path_matrix=floyd(data_matrix) foriinrange(vex_num): forjinrange(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',[4，'，;N',3,'N']] dist_matrix,path_matrix=floyd(data_matrix) printdist_matrix printpath_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'--------------------------------------时间消耗如下:-' forone_timeintime_list: printone_time
示例三：
importnumpyasnp Max=100 v_len=4 edge=np.mat([[0,1,Max,4],[Max,0，9，2]，[3，5，0，8][Max,Max,6,0]]) A=edge[:] path=np.zeros((v_len,v_len)) defFolyd(): foriinrange(v_len): forjinrange(v_len): if(edge[i,j]!=Maxandedge[i,j]!=0): path[i][j]=i print'init:' printA,'\n',path forainrange(v_len): forbinrange(v_len): forcinrange(v_len): if(A[b,a]+A[a,c]<A[b,c]): A[b,c]=A[b,a]+A[a,c] path[b][c]=path[a][c] print'result:' printA,'\n',path if__name__=="__main__": Folyd()
第三种算法：
SPFA算法是由理查德·贝尔曼解决单源最短路径问题的算法（Richard Bellman） 和 莱斯特·福特 创建。有时这种算法也被称为 Moore-Bellman-Ford 算法，因为 Edward F. Moore 这也有助于该算法的发展。其原理是对图片进行V-1次放松操作，以获得所有可能的最短路径。
优于迪科斯彻算法的是，边缘权值可以为负，实现简单。缺点是时间太复杂，高达 O(VE)。但是算法可以优化几种，提高效率。
思路：
我们使用数组dis记录每个节点的最短路径估计值，并使用邻接表或邻接矩阵存储图G。我们采用的方法是动态接近方法：建立先进先出的队列，以保存待优化的节点。优化时，每次取出团队的第一个节点u，并使用当前U点最短路径估计值放松离开U点的节点v。如果调整了V点的最短路径估计值，并且V点不在当前队列中，则将V点放在队尾。通过这种方式，继续从队列中取出节点进行放松操作，直到队列是空的。
推荐课程:深入分析聚类算法(黑马程序员)
