尧图网络 高端网站定制 · 原创设计
免费咨询热线
400-888-6620
免费获取方案
算法系列——贝尔曼福特算法(Bellman-Ford)
本系列旨在用简单的人话讲解算法尽可能避免晦涩的定义读者可以短时间内理解算法原理及应用细节。我在努力本篇文章编程语言为Python供参考。贝尔曼福特算法Bellman-Ford典型最短路径算法用于计算一个节点到其他节点的最短路径。Dijkstra算法也是基本原理逐遍的对图中每一个边去迭代计算起始点到其余各点的最短路径执行N-1遍最终得到起始点到其余各点的最短路径。N为连通图结点数与迪杰斯特拉算法的区别1. 迪杰斯特拉算法是借助贪心思想每次选取一个未处理的最近的结点去对与他相连接的边进行松弛操作贝尔曼福特算法是直接对所有边进行N-1遍松弛操作。2. 迪杰斯特拉算法要求边的权值不能是负数贝尔曼福特算法边的权值可以为负数并可检测负权回路。名词解释1. 松弛操作不断更新最短路径和前驱结点的操作。2. 负权回路绕一圈绕回来发现到自己的距离从0变成了负数到各结点的距离无限制的降低停不下来。1. 邻接矩阵构建基本用途用一个二维数组存放两两结点之间的距离或权值。2. 算法实现3. 最短路径的寻找同Dijkstra算法准备一路径数组更新时记录前驱结点。较为简单直接看也能看懂不太懂可以翻阅之前Dijkstra算法那篇博客算法系列——迪杰斯特拉算法Dijkstra4. 优化1. 提前跳出2. 队列优化见SPFA算法见另一篇博客算法系列——SPFA算法贝尔曼-福特算法的队列优化形式附全部源码#北京 天津 郑州 济南 长沙 海南 # 0 1 2 3 4 5 #模拟从文件中读入图的各个路径 a 0 1 500 0 2 100 1 2 900 1 3 300 2 3 400 2 4 500 3 4 1300 3 5 1400 4 5 1500 INF float(inf) N 6 weight [] def init(): global weight #定义邻接矩阵 记录各城市之间的距离 weight [[INF if j!i else 0 for j in range(N)] for i in range(N)] #解析数据 b [[int(i) for i in i.split( )] for i in a.split(\n) if i ! ] for i in b: weight[i[0]][i[1]] i[2] weight[i[1]][i[0]] i[2] init() def bellman_ford(src, target): dist [0 if i src else INF for i in range(N)] #用于记录最后更新结点 last_update [src if i ! INF else -1 for i in dist] #松弛n-1次因为最短路径的深度最多是n-1,n为结点数目 for i in range(N-1): change False #分别遍历边的两个顶点从而实现遍历所有边。 for j in range(N): for k in range(N): if dist[j] dist[k] weight[j][k]: dist[j] dist[k] weight[j][k] #记录更新该结点的结点编号 last_update[j] k #标记更改状态 change True #如果本轮未作出更改说明已完成 if not change: break #判断负权回路 for i in range(N): for j in range(N): if dist[j] dist[i] weight[j][i]: raise ValueError(存在负权回路) #输出从起点到终点的路径结点 tmp target path [] while tmp ! src: path.append(tmp) tmp last_update[tmp] path.append(src) print(-.join([str(i) for i in reversed(path)])) return dist[target]后记看了两个晚上第一个晚上看着看着放弃了今天晚上又鼓起勇气开写用了一晚上的时间现在是次日凌晨127终于完成了希望能对看完本文的各位有所帮助有所启发吧。我也在写的过程中不断学习不断变得更秃、变得更强晚安。本文大部分内容来自百度百科掺杂了一部分个人的理解和思考感谢完成该词条的大佬们写的很详细很易懂。 贝尔曼-福特算法
RELATED

相关推荐

leaflet的简单使用-离线地图方案

leaflet的简单使用-离线地图方案

先上官网 leaflet官网 中文官网 展示地图 <link rel"stylesheet" href"leaflet/leaflet.css"/><script type"text/javascript" src"leaflet/leaflet-src.js"></script><div id"mapid"></div&g…

📅 2026/11/14 2:58:12
xss攻击过滤

xss攻击过滤

<?php 关于XSS攻击&#xff0c;如果不是很清楚&#xff1a; 什么是XSS跨站脚本攻击 跨站脚本攻击&#xff08;Cross-site scripting&#xff0c;通常简称为XSS&#xff09;是一种网站应用程式的安全漏洞攻击&#xff0c;允许恶意使用者将程式码注入到网页上&#xff0…

📅 2026/11/15 13:06:14
基于高德API与异步Python构建智能选址AI Skill实战

基于高德API与异步Python构建智能选址AI Skill实战

1. 项目缘起&#xff1a;一个“选址直觉”的诞生与困惑 做线下生意&#xff0c;尤其是开一家新店&#xff0c;选址永远是那个最让人头疼、也最关键的决策。我干了十几年零售和餐饮&#xff0c;从街边小店到商场铺位&#xff0c;踩过的坑比走过的路还多。时间长了&#xff0c;脑…

📅 2026/11/15 10:19:43
MORE NEWS

更多资讯

📰

综合维修用哪种电工证?郑州报考避坑指南:别再交完钱考不过!

综合维修用哪种电工证?郑州报考避坑指南:别再交完钱考不过! 怕考不过白交培训费?现在很多人想考电工证,但不知道该选哪一种,结果花了不少钱,最后发现不是自己需要的证。今天我就以漯河转岗从业者的角度,详细说说 综合维修用哪种电工证…

📰

出租电工证是否合法了在哪考电工证怕挂科怎么办

出租电工证是否合法了在哪考电工证怕挂科怎么办 实操考试心里没底怕挂科,很多人一想到要考电工证,头就大。尤其是像你这样的安阳在职建筑工人,天天在工地上跑,想考个证提升自己,可一听说要实操,就开始发愁了。别担心,今天咱们就来聊聊【出租电工证是否…

📰

临漳哪能办电工证多少钱?电工证办理全攻略,刚需党必看

临漳哪能办电工证多少钱?电工证办理全攻略,刚需党必看 你是不是正为找工作发愁?手里缺个电工证,面试机会都少一半?在临漳,很多人因为没有电工证,错失了很多机会。而 临漳哪能办电工证多少钱…

📰

电工证被认可吗?应届生考这个证值不值得考?

电工证被认可吗?应届生考这个证值不值得考? 你是不是也像我一样,刚毕业就急着找工作,可用人单位偏偏要求你有特种作业操作证?电工证被认可吗?值不值得考?这些疑问压得我喘不过气来。作为平顶山某高校工程类专业的应届生,我亲身经历了找工作的难,也深…

📰

平遥电工证培训怎么报名别踩坑,考不过钱就白花了

平遥电工证培训怎么报名别踩坑,考不过钱就白花了 怕考不过白交培训费?现在越来越多的平遥电工想考证,但不知道怎么报名,更怕花了钱最后拿不到证。特别是劳务班组负责人,手里掌握着大量施工项目,电工证是刚需,但流程复杂、政策多变,一不小心就掉坑里。…

📰

特种工保险培训机构怎么选 通过率揭秘

特种工保险培训机构怎么选 通过率揭秘 你是不是也遇到过这种情况?不知道去哪报名怕被中介坑,特种工证考试又不是谁都能一次通过,要是碰上个不靠谱的培训机构,花了几千块还白忙一场。其实,选对培训机构是特种工保险考试通过率揭秘的关键。特别是在像平顶…

TODAY

今日更新

THIS WEEK

本周精选

THIS MONTH

本月热门

读完文章,想聊聊您的网站?

告诉我们您的行业与需求,资深顾问一对一梳理方案与报价,全程免费。

📞 💬