核心概念数学发布日期:2021年12月10日

找到你的路:网络上的最短路径

作者

特蕾莎修女Rexin

梅森·a·波特

年轻的评论家

贝基

巴黎珍妮·曼努埃尔学院

摘要

旅行到不同的目的地是我们生活的一个重要组成部分。无论是在日常生活中还是在度假时，我们都会去各种各样的地方。我们怎样才能找到从一个地方到另一个地方的最佳路线呢?也许我们可以测试两地之间所有不同的旅行方式，但另一种方法是使用数学和计算来找到两地之间的最短路径。在本文中，我们讨论了如何构造最短路径，并引入了Dijkstra算法来最小化路径的总代价，其中代价可能是旅行距离、旅行时间或其他一些量。我们还讨论了如何在现实世界中使用最短路径来节省时间和提高旅行效率。

什么是路径?

每天，我们都要决定在不同的地方之间使用哪条路线。在家里，你可以从卧室走到厨房。在你的家之外，你可以从你的家到学校。假设我们有一个网络由街道和人行道相互连接的地方。这些位置中的每一个都被称为a节点，街道和人行道被称为边缘．节点的“邻居”是由边连接到的节点。一个路径是原点节点和目标节点之间的边序列[1，2］．

最短路径

在数学中，人们研究路径的长度来构造短路径。找到最短路径通常是有用的。最短路径是两个节点之间具有最少边的路径成本每条边都是相同的(例如，如果每条边都是相同长度的街道)。更一般地说，给定一个起始节点和一个目的节点，a最短路径从起始节点到目的节点是在从起始节点到目的节点的所有路径中总代价最小的路径[1］．为了计算一条路径的代价，我们把它所有边的代价加起来。成本可以衡量距离、时间或其他东西。例如，在小城市地图中图1从家到学校的最短路径可能是在所有可能的路径中所花费的时间最少的一条。网络中两个节点之间可以有多条最短路径，因为多条路径可以具有相同的最小代价。这就是为什么我们提到两个节点之间的“a”最短路径(尽管这听起来很奇怪)，而不是它们之间的“the”最短路径。

图1 -在这张小城市地图中，这是一个网络的例子，位置(即节点)1 - 4出现在街道之间的十字路口(即边缘)。万博manbetxapp最新

每个位置(蓝色和红色的房子、池塘、学校和杂货店)也是一个节点。**活动1:**在地图上画一条从蓝房子到学校的路。你在照片中拍摄了哪些街道(即边缘)?在现实生活中，当你从家到学校时，你会走哪条街?(这个图的灵感来自于http://clipart-library.com/clipart/449476.htm．我们的数字还使用了公共剪贴画。)

在日常生活中，当你去不同的地方时，你可能已经想到了最短路径。在我们从卧室到厨房的例子中，如果你只想从卧室走到厨房，那么从卧室走到洗衣房，然后走到外面的后院，最后走到厨房就没有多大意义了。直接从你的卧室走到厨房会快得多，而不是先在洗衣房和后院停留。在一个距离很近的旅行中，只有几个十字路口(即节点)，你可以尝试大多数不同的路径来找到最短的路径。万博manbetxapp最新但如果地点相距较远——例如，你的家、学校和不同城市的玩具店——那么找到最短路径就会困难得多。像谷歌Maps这样的导航工具是如何确定到达目的地的最佳方式的?一种方法是解决最短路径问题，这是一个数学问题，在两个节点之间找到一条路径，使路径上的边的代价之和最小化¹．

在数学中，我们经常用数字来标记节点(参见万博manbetxapp最新图1)或信件(见图2)。为了简单起见，我们还假设所有东西都是二维的(就像在一张纸上画画一样)，所以我们将用测量家里地板上两点之间距离的方式来测量距离。我们不会担心地球的高度或曲率。在网络中图2，如果我们要找到从节点a到节点F的最短路径，我们应该选择代价最小的边。例如，我们不选择从节点A到节点B的代价为4的边，而是选择从节点A到节点c的代价为2的边迪杰斯特拉算法²^，^3.．

图2 -在这个网络中，突出显示的蓝色箭头显示了从节点A到节点F的最短路径

数字表示边缘的成本(不是按比例绘制的)。蓝色箭头显示最短路径生成树A是原点节点。观察到从节点A到节点F的最短路径是最短路径生成树的一部分。标签“dist”表示从“原点”节点到特定节点的总距离，标签“last”表示从“原点”a到达特定目标节点所经过的最后一个节点。在“Dijkstra’s Algorithm”一节中，我们详细解释了确定最短路径的步骤。[这个数字的灵感来自于网上的数字¹^，^3.．]

图3 -活动2:现在轮到您了!使用Dijkstra的算法找到一个最短路径生成树，从原点到这个网络中的每一个节点5。 — 图3 -**活动2:**现在轮到你了!使用Dijkstra的算法来找到一个最短路径生成树，从原点到这个网络中的其他节点⁵．

我们已经为您完成了Dijkstra算法的第一步。[这个数字的灵感来自于一个在线活动¹．]

迪杰斯特拉算法

“算法”是解决问题的精确步骤集，例如最短路径问题[1］．Dijkstra算法是一种著名的最短路径算法;它是以它的发明者Edsger Dijkstra的名字命名的，他是一位著名的荷兰计算机科学家⁴．可以使用Dijkstra算法来创建最短路径生成树(参见图2)，通过分别计算从原点到每个其他节点的距离，找到网络中从原点节点到其他节点的最短路径。在这个讨论中，我们使用距离作为代价，但是我们可以使用Dijkstra算法来计算任何类型的代价。

在图2，我们展示了如何使用Dijkstra算法来构造一个连通网络的最短路径生成树。跟随在图2当你阅读我们的解释时，看视频1对于这个例子的动画。

视频1 -图2介绍:跟随本视频讲解使用Dijkstra算法为网络找到最短路径生成树的示例图2．

以下是我们采取的步骤:

1.我们在“原点”节点上画阴影。(参见中节点A图2)。对于原点节点的每个邻居，我们将“dist”的初始值设置为原点节点到该邻居的距离，并将“last”的初始值设置为原点节点。在图2，到这一步结束时，我们为节点B和c填写“dist”和“last”的值。节点D、E和F的“dist”和“last”项仍然为空。

2.我们标识“dist”值最低(不包括空格)的非阴影节点，并将其标记为“当前”节点。例如，如果我们从节点A开始作为原点，那么当前节点是节点C，因为从A到C的“dist”小于从A到b的“dist”。如果有平局，我们选择具有最小“dist”值的任何节点。

3.我们对“current”的每个无阴影邻居执行以下步骤:

a.我们将“current”的“dist”加到从“current”到邻居的边的代价。

b.如果步骤3a中的“dist”小于邻居的“dist”(或者邻居的“dist”仍然为空)，我们将邻居的“dist”更新为步骤3a中计算的“dist”，并将邻居的“last”设置为当前节点。

4.在为“current”的所有未着色邻居完成步骤3后，我们用阴影填充“current”并划掉“current”标签。

5.如果所有节点都是阴影，则转到步骤6。否则，我们返回步骤2。

6.我们突出显示每个节点与其“最后”节点之间的边缘，以显示从原点开始的最短路径生成树。

应用程序

使用Dijkstra算法，我们可以找到一个最短路径从一个原点节点到网络中的任何其他节点。如果你把你的家看作起点节点，把你的目的地看作网络中的其他节点，你就可以确定一条从你的家到任何你想去的地方的好路线。假设你想在回家之前参观几个地方。你如何找到游览所有这些目的地的最佳方式，同时最大限度地减少费用，如汽油、酒店和时间?更抽象地说，我们如何找到一条经过的最短路径所有然后返回到起始节点?这个问题是最短路径问题的扩展，被称为“旅行推销员问题”。⁶．

寻找最短路径对于解决许多不同类型网络中的问题都很重要。例如，最短路径可以提高城市规划的效率。土木工程师可以代表一个城市作为一个网络，并确定修建道路以减少交通拥堵的最佳位置，以及安装灌溉管道以向居民供水的最佳位置[2］．寻找最短路径还可以使数据从一台计算机高速传输到另一台计算机，允许大量信息在几秒钟内传播。1，2］．

在通信和社交网络中也有许多短路径的例子。例如，假设社交网络中的每个人都是一个节点，每条边代表一段友谊。你可以通过朋友的关系找到如何与朋友圈之外的人联系的方法。在美国，两个随机的人之间最短的联系(比如友谊)比人们想象的要短。在这条路径上，起点人与终点人之间的平均距离不超过6步[3.] !人与人之间最短路径的典型缩短说明了“小世界现象”，这些短路径长度也启发了“六度分离”这个术语[1］．第二个例子与当前事件有关。在COVID-19大流行期间，寻找捷径对于限制暴露于导致COVID-19的病毒非常有用。例如，在过去一年半的时间里，当我们在超市里走动时，选择一条较短的路径来购买杂货是有益的(同时通过保持身体距离来避免与他人接触)[4，5］．

结论

当从一个地方旅行到另一个地方时，最短路径很重要。它们在许多类型的网络中有许多应用，并可以帮助解决各种现实问题。从计划家庭度假到探索我们的世界是如何连接的，网络上最短路径的研究是非常重要的，它构成了更复杂调查的基础。

术语表

网络：↑对象的集合(称为“节点”)和它们之间的连接(称为“边”)。

节点：↑网络中连接到其他对象的对象。例如，在图1，每个地点和每个路口都是一个节点。

边缘：↑连接两个节点的对象。例如，当你从家到学校时，每条街道都是一条边。

路径：↑从起始节点到目的节点的边序列。

成本：↑度量沿网络边缘移动所花费的努力。在现实生活中，成本可以衡量距离、时间或其他东西。

最短路径：↑从起始节点到目的节点的所有路径中总开销最小的路径。

最短路径生成树：↑连接网络的一部分，从给定的起始节点开始，并指定从该节点到网络中其他节点的最短路径。例如，如果网络有6个节点，那么最短路径生成树中就有5条这样的最短路径。网络的生成树包括网络的所有节点。此外，由于生成树是一种被称为“树”的网络类型，其中的任何一对节点之间只有一条路径。

利益冲突

作者声明，这项研究是在没有任何商业或财务关系的情况下进行的，这些关系可能被解释为潜在的利益冲突。

致谢

我们非常感谢我们的年轻读者——nia Chiou, Taryn Chiou, Zoë Chiou, Tycho Elling和Sage hansen——他们提供了许多有用的评论。我们也感谢他们的家人——lyndie Chiou、Christina Chow、Tim Elling和Sterling hansen——让我们与他们取得联系，并征求他们的反馈。我们也感谢Lyndie Chiou, Michelle Lee, Thomas Rexin和Akrati Saxena的宝贵意见。我们也感谢我们的年轻审稿人和他们的导师提出的许多优秀建议。MAP感谢国家科学基金会(授权号1922952)通过威胁检测算法(ATD)计划提供的支持。