189 8069 5689
这篇文章将为大家详细讲解有关用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
示例三：