shortest-path-algorithms-how-to-use-data-to-navigate-and-optimize-746809d51e8f.md

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

原文：towardsdatascience.com/shortest-path-algorithms-how-to-use-data-to-navigate-and-optimize-746809d51e8f?source=collection_archive---------9-----------------------#2024-07-30

迪杰斯特拉算法与贝尔曼-福特算法概述

Ben Chamblee

·发布于 Towards Data Science ·阅读时间：7 分钟·2024 年 7 月 30 日

--

图片来源：Unsplash+ 在 Unsplash

你有没有想过，为什么你的 GPS 总是能够找到最快的路线？无论从 A 点到 B 点有多少条路线，你的 GPS 会筛选出所有路径并给出一条路线——它是怎么知道哪条路线最好呢？在后台，使用像迪杰斯特拉算法这样的算法，正在进行大量的计算，以找出你所在的位置与目标地点之间的最短路径。然而，也有许多其他算法可以实现这一点，我想介绍其中的一些！在这篇文章中，我将介绍一种流行的最短路径算法以及一种更高级的算法，并展示你如何在数据项目中使用它们，或者仅仅为了好玩！

迪杰斯特拉算法

我可以写一篇关于迪杰斯特拉算法如何工作的总结，但我强烈推荐你先观看这段 Spanning Tree 的 YouTube 视频。

如果你不想观看视频，下面是重点：

你有一组点，想要找出它们之间的最短路径。例如，如果你想从 S 点到 P 点，最短且唯一的路径是 2 分钟。然而，如果…