最短路径算法：如何使用数据导航和优化

原文towardsdatascience.com/shortest-path-algorithms-how-to-use-data-to-navigate-and-optimize-746809d51e8fhttps://unsplash.com/ 在 Unsplash 上提供](…/Images/6f861b51b31c488d694759f308a2da6e.png)图片由 [Unsplash](https://unsplash.com/photos/top-view-of-unrecognizable-young-couple-with-maps-planning-vacation-trip-holiday-desktop-travel-concept-w98knetr8EA) 在 Unsplash 上提供你有没有想过你的 GPS 总是能找到去目的地的最快路线无论从点 A 到点 B 有多少种方式你的 GPS 都会筛选出所有路线只给你一条路线——它是如何知道哪条路线是最好的呢在后台正在使用像迪杰斯特拉这样的算法进行大量计算以找到你所在位置和你想去的位置之间的最短路径。虽然有许多不同的算法可以实现这一点但我想要介绍其中的一些在这篇文章中我将探讨一个流行的最短路径算法以及一个更高级的算法并展示你如何将它们用于你的数据项目或仅仅是为了乐趣迪杰斯特拉算法我可以简要地总结一下迪杰斯特拉算法的工作原理但我强烈建议你先观看 Spanning Tree 的这个 YouTube 视频。如果你不想看视频这里有一个要点https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/05ea7b7892819ec797fc737c38a27919.png图片来自 维基共享资源你有一系列点并想找出它们之间的最短路径。例如如果你想从点 S 到点 P最短且唯一的路径是 2 分钟。然而如果你想从点 P 到点 W有几种方式可以到达那里。如果你从 P 到 X 到 V 到 W这次旅行将花费你 16 分钟路线 1或者你可以从 P 到 X 到 Y 到 W这次旅行只需 13 分钟路线 2。迪杰斯特拉算法基本上会进行所有这些计算但规模要大得多。https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/aa85faca6075dce34c52926d0236a4e5.png图片来自 维基共享资源 由作者编辑https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/63fd3f8f370ead4c80b63a33a6d29593.png图片来自 维基共享资源 由作者编辑这在 Python 中看起来会是这样首先创建一个字典存储每个点、该点可以到达的点以及这些点之间的距离。对于上面的图片它看起来会是这样path{S:{P:2,U:3},U:{S:3,X:1,V:3},P:{S:2,X:4,Q:5},X:{P:4,U:1,Q:7,Y:6,V:8},Q:{P:5,X:7,R:2},Y:{X:6,R:1,W:3},V:{U:3,X:8,W:4},W:{V:4,Y:3,T:5},R:{Q:2,Y:3,T:6},T:{R:6,W:5}}然后我们只需要一个函数来遍历这条路径的所有组合。defdijkstra_example(path,start_vertex,end_vertex):max_value10**6#assume all edge weights are smaller than this valuedistances{vertex:max_valueforvertexingraph}distances[start_vertex]0#initialize a priority queue and add the start vertex with distance 0priority_queue[(0,start_vertex)]whilepriority_queue:#get the vertex with the smallest distancecurrent_distance,current_vertexheapq.heappop(priority_queue)#if the current vertex is the end vertex, return the distanceifcurrent_vertexend_vertex:returndistances[end_vertex]#if the distance is greater than the recorded distance, skip itifcurrent_distancedistances[current_vertex]:continue#explore neighbors of the current vertexforneighbor,weightinpath[current_vertex].items():distancecurrent_distanceweight#if a shorter path is foundifdistancedistances[neighbor]:distances[neighbor]distance heapq.heappush(priority_queue,(distance,neighbor))return100#return 100 if you end vertex isnt reachable该函数将输出两个起始顶点和终止顶点之间的最短路径你可以使用路径字典中的值来测试它在更大的规模上比如有数千个点的字典使用 Python 立即执行此操作非常有用。通常Dijkstra 算法是确定两点之间最短路径的一个可靠的算法。但在选择最短路径问题的算法时还有一些其他考虑因素。例如如果你必须处理负权重。负权重一开始可能没有意义但如果你像开车一样考虑你可以选择最短路径或成本最低的路径没有过路费负权重可能代表某条路径成本的降低。如果你在处理负权重以进行减少或其他类似操作时你应该考虑贝尔曼-福特算法。贝尔曼-福特算法 边松弛这个算法与 Dijkstra 算法类似但在处理现实世界问题数据可能更混乱时可能更灵活。它基于“边松弛”的原则这意味着如果从一点到另一点已知路径可以通过一个相邻点得到改善那么该已知最短路径将被更新。边松弛也存在于 Dijkstra 算法中但两者之间的主要区别是 Bellman-Ford 可以处理负权重。https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/3b28f8414362875dd7058fb176152e8b.png来自维基共享资源的图片你可以使用贝尔曼-福特算法的例子是如果你正在处理一个物流/供应链问题。公司通常需要在仓库、供应商和店面之间运输货物——每一条路线都有相关的成本这些成本可能会因为各种因素权重而累积。贝尔曼-福特算法可以帮助从成本角度确定最有效的路线并找到任何低效或节省成本的机会。几个需要考虑的事项每个位置都表示为一个顶点。在某些情况下路线可能会有折扣这可以降低运输成本从而导致负的边权重。该算法的实现将涉及从起始位置到其他位置的初始化距离。一开始我们将所有距离设置为无穷大这样所有节点最初看起来都是不可达的。但这只是为了设置将在边松弛过程中更新。对 X-1 次的所有边进行松弛其中 X 是位置的数量。检查是否存在负权重循环。要可视化这种情况请看下面的图片https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/bbc1c7c87efea9dc84da6ac9f6215545.png作者提供的图片而在 Python 中实现类似的功能代码可能看起来像这样Path{A:{B:5,C:2},B:{C:1,D:3},C:{D:8},D:{A:7,B:-2}}defbellman_ford(path,start_vertex):#initialize distances from start_vertex to all other vertices as infinitymax_valuefloat(inf)distances{vertex:max_valueforvertexinpath}distances[start_vertex]0#relax all edges |x| - 1 timesforxinrange(len(path)-1):forvertexinpath:forneighbor,weightingraph[vertex].items():ifdistances[vertex]!max_valueanddistances[vertex]weightdistances[neighbor]:distances[neighbor]distances[vertex]weight#check for negative-weight cyclesforvertexinpath:forneighbor,weightinpath[vertex].items():ifdistances[vertex]!max_valueanddistances[vertex]weightdistances[neighbor]:raiseValueError(Graph contains a negative weight cycle)returndistances shortest_distancesbellman_ford(graph,A)print(shortest_distances)#output the shortest distances from A to all other vertices现在我敢打赌您在想“什么是 ValueError我以为 Bellman-Ford 可以处理负权重”您是对的问题不在于负权重而在于负权重循环。负权重是具有负值的单个边可以用来表示正权重图的相反。想象一下正权重意味着成本更高而负权重则意味着折扣。当一个起点和终点相同的路径具有负权重之和时会发生负权重循环。这基本上意味着每次您从起点到终点时都会无限期地继续降低成本因此代码将无限循环以使成本尽可能小。这应该会引发错误如您所见这些内容可能会变得相当复杂但如果您遇到这样的错误这很可能是数据输入错误可以轻松修复。项目想法现在您已经了解了这些算法的工作原理我鼓励您使用它们来制作一些有趣的项目以下是一些您可以添加到您的数据科学作品集的示例。最优配送路线规划器您将构建一个应用程序来寻找城市内的最优配送路线以最小化行驶距离。您可以在OpenStreetMap上找到数据并在Streamlit上托管应用程序。在您的地图上识别配送点并在您的数据中标记这些节点。然后您可以使用 Dijkstra 算法找到每条路径之间的最短路径——或者您可以从一个起点开始并从那里使用该算法。航班价格优化工具您可以构建一个工具来查找城市之间的最便宜航班您还可以通过考虑直达航班和有中转的航班以及价格变化的可能性来增加复杂性这可以表示正负权重。数据可以从Skyscanner等来源获取而Streamlit再次是一个托管应用程序的绝佳选择。Bellman-Ford 算法可以根据几个不同的特征找到最优路线——这可以是一个很有用的工具同时也是一个很好的展示在您的作品集中的工具结论我希望阅读这篇文章能让您更好地了解最短路径算法的工作原理并激发您在下一个项目中使用其中之一。这些算法有无数有趣的用例我也很享受为这篇文章关于它们的内容。感谢您的阅读