100个免费货源网站,做网站用的军事图片,网站建设步骤列表图片,蔚县网站建设前置文章#xff1a; dijkstra 算法为什么高效 有向图的负权值边与建模 求单源最短路径的新方法
前天晚上实现了一个基于 dijkstra 算法的求单源最短路径的新算法#xff0c;整理了一篇文章。我非常不愿意把一些直观的问题太过于技术化#xff0c;但多年的职业经历偏偏让一…前置文章 dijkstra 算法为什么高效 有向图的负权值边与建模 求单源最短路径的新方法
前天晚上实现了一个基于 dijkstra 算法的求单源最短路径的新算法整理了一篇文章。我非常不愿意把一些直观的问题太过于技术化但多年的职业经历偏偏让一篇好好的文字写着写着就变成技术博客了非常不适。
我的新算法强调 “只需要一次广度优先遍历”文章 求单源最短路径的新方法 里的图解释得已经很明白了但这和 dijkstra 算法有什么关系为什么说是 “基于 dijkstra 算法的新算法”基不基于不重要要点在于dijkstra 算法本身它就是一个 “只需要一次广度优先遍历” 就获得结果的算法不同点在于dijkstra 算法用 S 到 V_curr 的距离来松弛而我的方法则是用坐标系把每个节点的松弛结果都展示了出来松弛的过程通过递归调整后继节点纵坐标来完成而广度优先恰恰意味着后继节点非常少在绝大多数情况下好运常在O(E) 时间复杂度即可完成。
要点就是广度优先遍历。
我先解释广度优先和深度优先两种遍历方式的不同
来看 dijkstra 算法本身将节点不断加入 closeset 的过程就是广度优先遍历的过程如果节点不是离散的而是连续的这意味着边缩短到无穷小而不再有权重那么广度优先遍历能确保首先接触到的节点一定是距离最短的节点。广度优先遍历会系统地检查从起点出发的每一步距离确保它找到的第一个目的地的路径一定是最短的。这是因为它按波次向外扩展首先检查所有与起始点直接相邻的点然后检查与这些点相邻的点以此类推。
通常经理们喜欢讲 “爆炸半径” 这个词爆炸半径越小波及面越小但也是最先被波及到。控制爆炸半径就是尽量让爆炸只影响它直接接触到的第一波接触面因为爆炸本身就是广度优先遍历一圈一圈向外只不过它是并行的。
为了理解距离短一定先接触可以手工做一张图节点用绳子打的结模拟边就是绳子边的权值就是绳子长度往外抻这张网直到绳子变紧拉不动了停止那些拉紧的绳子就是最短路径在源点放一些蚂蚁看看蚂蚁先到达哪里。
但对于算法我们必须理解算法的本质由于人脑和计算机的秉性算法是一个流程一个串行的步骤序列所以算法无法 “一下子看出谁距离 S 最近”算法必须通过一系列步骤去比对而广度优先遍历就是最有效的方式它非常形象地模拟了 “一圈一圈向外按波次扩展” 的过程。
如果你到了一个陌生的城市找最近的路比如找回家最短的路去商场最短的路去公园最短的路不依赖现代导航纯粹 citywalk 步行找路是深度优先一条路见路口就拐还是广度优先不同的路都试一下呢
在实际中可以将广度优先搜索策略简化为 “始终选择离你最近的未探索路径”这就是 dijkstra 算法的核心。当你来到一个十字路口你总是先探索离你最近的未走过的街道而不是随机选择或深入一条特定的路径。
相比之下深度优先搜索可能会导致你走过一些不必要的长路甚至可能会多次经过相同的地方除非你有很好的记忆或者有某种方式来标记已经探索过的路径。深度优先策略更适合探索迷宫或查找任何可达但不一定最短的路径。
有人认为人脑并不擅长即时地计算和记忆复杂的路径图所以必须要有个导航但导航背后大概率还是 dijkstra 算法使用现代导航工具或询问当地居民通常更实用但对我而言幸运的是我个人非常擅长 citywalk 并寻找计算最短路径从 45 岁直到现在我一直保持着 citywalk 的习惯第一次是 4 岁半从安阳市钟楼经过北大街走到北门绕行解放路走到铁狮口迷路硬摸回家最后一次就是今天嘉定环城河跑步一圈后从东大街走到温宿路拐入博乐路进入州桥经清河路走到罗宾森吃了一顿本清素酸菜鱼。
这也许就是我擅长图论图算法的原因吧实践经历加上一点天赋历练出来的虽然我不懂那些技术术语但我能给人直感直击本质。
浙江温州皮鞋湿下雨进水不会胖。
