python实现最短路径的实例方法_最短路径问题python,无向图最短路径python - CSDN文库

84 浏览量更新于2023-03-03 评论 8 收藏 67KB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

python实现最短路径的实例方法实现最短路径的实例方法

最短路径问题（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:",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:",graph

print "Path:",path

print "Points pass-by:"

for i in range(N):

for j in range(N):

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余2页未读，立即下载

评论0

weixin_38581992

粉丝: 3
资源: 908

会员权益专享

图片转文字

全年可省5，000元立即开通

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈