最短路径算法：如何利用数据进行导航和优化Dijkstra算法和Bellman-Ford算法概述

图片来源于 Unsplash+ 在 Unsplash

你有没有想过，为什么你的GPS总是能够找到到达目的地的最快路线？无论从A点到B点有多少种方式，你的GPS会对它们进行筛选，只提供一条路线——它是如何知道哪条路线是最佳的呢？在后台，使用像Dijkstra算法这样的算法进行大量计算，以找到你所在位置和目标位置之间的最短路径。然而，还有许多不同的算法可以实现这一点，我想向你介绍其中的几个！在这篇文章中，我将介绍一种流行的最短路径算法和一种更高级的算法，并展示如何将它们应用于你的数据项目或仅仅是为了好玩！

迪克斯特拉算法

我可以写一个关于Dijkstra算法如何工作的简短总结，但我强烈建议您首先观看这Spanning Tree的YouTube视频。

如果你不想看，这里是要点：

图像来自 维基共享资源

您有一组点，并想要找出它们之间的最短路径。例如，如果您想从点 S 到点 P，最短且唯一的路径是 2 分钟。然而，如果您想从点 P 到点 W，则有几条路径可以到达那里。如果您从 P 到 X，再到 V 然后到 W，这段旅程将花费 16 分钟（路线 1\）；另外，您可以从 P 到 X，再到 Y，最后到 W，这段旅程只需 13 分钟（路线 2\）。Dijkstra 算法基本上就是在更大规模上进行所有这些计算。

图片来源于 维基共享资源 作者编辑

图片来自 维基媒体共享资源，由作者编辑

这里在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}  }

然后我们只需要一个函数来遍历这个路径的每种组合。

def dijkstra_example(path, start_vertex, end_vertex):      max_value = 10**6 #假设所有边的权重都小于这个值      distances = {vertex: max_value for vertex in graph}      distances[start_vertex] = 0        # 初始化优先队列并将起始顶点和距离0添加进去      priority_queue = [(0, start_vertex)]        while priority_queue:          # 获取距离最小的顶点          current_distance, current_vertex = heapq.heappop(priority_queue)            # 如果当前顶点是目标顶点，则返回距离          if current_vertex == end_vertex:              return distances[end_vertex]            # 如果距离大于记录的距离，则跳过          if current_distance > distances[current_vertex]:              continue            # 探索当前顶点的邻居          for neighbor, weight in path[current_vertex].items():              distance = current_distance + weight                # 如果找到更短的路径              if distance < distances[neighbor]:                  distances[neighbor] = distance                  heapq.heappush(priority_queue, (distance, neighbor))        return 100  # 如果目标顶点不可达则返回100

该函数将输出两个起始点和终止点之间的最短路径，您可以使用我们路径字典中的值来测试它！在更大规模，如拥有数千个点的字典时，使用Python即时实现这一点是非常有用的。

一般来说，Dijkstra算法是确定两点之间最短路径的可靠算法。然而，在选择最短路径问题的算法时，还有一些其他考虑因素。例如，如果你需要处理负权重，负权重起初可能没有意义，但如果你考虑到驾驶时，你可以选择最短路径或花费最少金额的路径（没有通行费），负权重可能代表某条路径成本的降低。如果你正在处理负权重的减少或类似情况，你应该考虑Bellman-Ford算法。

贝尔曼-福特算法 + 边松弛

这个算法的工作原理类似于迪杰斯特拉算法，但它在处理可能比较复杂的现实世界问题时更加灵活。它的运作原则是“边松弛”，基本上意味着如果从一个点到另一个点的已知路径可以通过经过一个相邻点来改善，那么该已知的最短路径将被更新。边松弛在迪杰斯特拉算法中也存在，但两者之间的主要区别是贝尔曼-福特算法可以处理负权重。

图片来自 维基媒体共享资源

一个使用贝尔曼-福特算法的例子是在处理物流/供应链问题时。公司通常需要在仓库、供应商和店面之间运输货物——每条路线都有相关的费用，因为各种因素（重量！）可能会导致成本增加。贝尔曼-福特算法可以帮助识别在成本方面最有效的路线，并找出任何低效之处或节省成本的机会。

一些需要考虑的事项：

该算法的实现将涉及：

为了可视化这样的场景，请查看下面的图像：

图像作者提供

在Python中要做类似的事情，看起来会像这样：

路径 = {  'A': {'B': 5, 'C': 2},  'B': {'C': 1, 'D': 3},  'C': {'D': 8},  'D': {'A': 7, 'B': -2}  }

    def bellman_ford(path, start_vertex):      #初始化从起始顶点到所有其他顶点的距离为无穷大      max_value = float('inf')      distances = {vertex: max_value for vertex in path}      distances[start_vertex] = 0        #放宽所有边 |x| - 1 次      for x in range(len(path) - 1):          for vertex in path:              for neighbor, weight in graph[vertex].items():                  if distances[vertex] != max_value and distances[vertex] + weight < distances[neighbor]:                      distances[neighbor] = distances[vertex] + weight        #检查负权重循环      for vertex in path:          for neighbor, weight in path[vertex].items():              if distances[vertex] != max_value and distances[vertex] + weight < distances[neighbor]:                  raise ValueError("图包含负权重循环")        return distances    shortest_distances = bellman_ford(graph, 'A')  print(shortest_distances)  #输出从 'A' 到所有其他顶点的最短距离

现在我敢打赌你在想“什么是ValueError？我以为Bellman-Ford能够处理负权重？？”，你是对的！问题不来自负权重，而是负权重环。

如你所见，这些东西可能变得相当复杂，但如果你遇到这样的错误，可能是数据输入错误，可以很容易地修复。

项目想法

现在你已经对这些算法的工作原理有了一定了解，我鼓励你使用它们来制作一些有趣的项目！以下是几个你可以添加到数据科学作品集中的示例。

最佳配送路线规划器

您将要构建一个应用程序，以找到在城市内配送的最佳路线，最小化旅行距离。您可以在 OpenStreetMap 上找到数据，并将应用程序托管在 Streamlit。在您的地图上标识配送点，并在您的数据中为这些节点贴上标签。然后，您可以使用 Dijkstra 算法找到每条路径之间的最短点——或者您可以确定一个起点，并从那里使用该算法。

航班价格优化工具

您可以构建一个工具，在城市之间找到最便宜的航班，您还可以通过考虑直飞和有经停的航班，增加复杂性，并考虑价格变化（这可以表示正权重和负权重）。数据可以从像 Skyscanner 这样的来源获得，而 Streamlit 再次是托管应用程序的一个不错选择。可以使用贝尔曼-福特算法根据几个不同的特征找到最佳路线——这可能是一个方便的工具，同时也是展示在您作品集中一个很好的工具！

结论

我希望阅读这篇文章能让你更好地理解最短路径算法的工作原理，并激励你在下一个项目中使用其中之一。这些算法有很多有趣的应用案例，我在为这篇文章阅读更多相关内容时感到很高兴。

谢谢你的阅读！