数据价值-DataValues

 找回密码
 立即注册

QQ登录

只需一步,快速开始

查看: 108|回复: 0

[python] 教你一招:Python编写的最短路径算法

[复制链接]

1万

主题

1万

帖子

3万

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
39029
发表于 2016-3-31 17:07:33 | 显示全部楼层 |阅读模式
文 | 初行
一心想学习算法,很少去真正静下心来去研究,前几天趁着周末去了解了最短路径的资料,用python写了一个最短路径算法。算法是基于带权无向图去寻找两个点之间的最短路径,数据存储用邻接矩阵记录。首先画出一幅无向图如下,标出各个节点之间的权值。


其中对应索引:
A ——> 0
B——> 1
C——> 2
D——>3
E——> 4
F——> 5
G——> 6
邻接矩阵表示无向图:


算法思想是通过Dijkstra算法结合自身想法实现的。大致思路是:从起始点开始,搜索周围的路径,记录每个点到起始点的权值存到已标记权值节点字典A,将起始点存入已遍历列表B,然后再遍历已标记权值节点字典A,搜索节点周围的路径,如果周围节点存在于表B,比较累加权值,新权值小于已有权值则更新权值和来源节点,否则什么都不做;如果不存在与表B,则添加节点和权值和来源节点到表A,直到搜索到终点则结束。
这时最短路径存在于表A中,得到终点的权值和来源路径,向上递推到起始点,即可得到最短路径,下面是代码:



运行结果:


再来一例:



以上就是本文给大家分享的全部内容了,希望大家能够喜欢,能够学习python有所帮助。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|Archiver|手机版|小黑屋|DataValues ( 赣ICP备16006919号 ) DataValues

GMT+8, 2019-9-22 20:57 , Processed in 0.111282 second(s), 29 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表