基于关键图的带插图的最短路径算法-第1部分：Dijkstra和Bellman-Ford算法
尽管许多编程库都封装了图形和其他算法的内部工作细节，但作为数据科学家，它对相当了解这些细节很有帮助。对此类算法背后的直觉的深刻理解，不仅有助于了解其背后的逻辑，而且还有助于就其在现实生活中的适用性做出有意识的决策。有几种基于图的算法，最值得注意的是最短路径算法。通常会遇到Dijkstra，Bellman Ford，A *，Floyd-Warshall和Johnson等算法。尽管在线上的许多教科书和信息资源中都讨论了这些算法，我觉得没有多少提供的可视化示例可以以足够的粒度说明处理步骤，从而使您可以轻松理解工作细节。因此，为了我自己的理解，我不得不使用足够简单的图形来可视化算法流程，并且我想与本文分享我的示例以及解释。由于有很多算法可以说明，因此我决定将文章分为几部分。在第1部分中，我说明了Dijkstra和Bellman-Ford算法。在深入研究算法之前，我还想强调图形数据结构上的显着点。由于有许多算法可以说明，因此我决定将文章分为几部分。在第1部分中，我说明了Dijkstra和Bellman-Ford算法。在深入研究算法之前，我还想强调图形数据结构上的显着点。由于有很多算法可以说明，因此我决定将文章分为几部分。在第1部分中，我说明了Dijkstra和Bellman-Ford算法。在深入研究算法之前，我还想强调图形数据结构上的显着点。
图形数据结构快速入门
图是一种数据结构，包括一组有限的非空顶点，其中一些顶点对被连接。在现实生活中，这样的顶点表示现实世界中的对象，其中一些这样的对象对是相关的，并且这种关系由链接连接表示。一对顶点之间的链接称为边。边缘具有方向性。在单向边缘的情况下，箭头从尾顶点（源）指向头顶点（目标），因此链接采用一种方式。这样，顶点v1和v2之间的边是有序对（v1，v2），其中v1是尾顶点，而v2是头顶点。在双向边缘的情况下，箭头指向两个方向，因此链接是双向的。这样，顶点v1和v2之间的边是无序对，其中（v1，v2）和（v2，v1）代表同一条边。包含所有单向边的图称为有向图。包含所有双向边的图称为无向图。其中一些边是单向而某些边是双向的图称为混合图。入射到顶点的边的数量称为顶点的程度。顶点的出度是入射到以顶点为尾的顶点的有向边的数目，而顶点的入度是入射到以顶点为头的顶点的有向边的数目。另外，边缘具有重量。边缘权重表示该边缘的容量，成本或距离。这样，边缘权重可以是正数或负数。从顶点v1到顶点vn的路径是顶点v1，v2，v3的序列... 图中的vn使得（v1，v2），（v2，v3）…（vn-1，vn）对通过图中的边连接。这样，如果图中两个顶点之间存在路径，则两个顶点将被连接。如果除了第一个和最后一个顶点以外的所有顶点都不同，则一条路径被认为是简单的。如果第一个和最后一个顶点相同，则将路径称为圆形或循环形。没有任何圆形路径的有向图称为有向无环图（DAG）。路径中的边缘数量表示路径的长度，路径中边缘权重的总和表示该路径的容量，成本或距离。如果路径权重在循环路径中为负，则该路径称为负循环。如果图中两个顶点之间存在路径，则将连接这两个顶点。如果除了第一个和最后一个顶点以外的所有顶点都不同，则一条路径被认为是简单的。如果第一个和最后一个顶点相同，则将路径称为圆形或循环形。没有任何圆形路径的有向图称为有向无环图（DAG）。路径中的边缘数量表示路径的长度，路径中边缘权重的总和表示该路径的容量，成本或距离。如果路径权重在循环路径中为负，则该路径称为负循环。如果图中两个顶点之间存在路径，则将连接这两个顶点。如果除了第一个和最后一个顶点以外的所有顶点都不同，则一条路径被认为是简单的。如果第一个和最后一个顶点相同，则将路径称为圆形或循环形。没有任何圆形路径的有向图称为有向无环图（DAG）。路径中的边缘数量表示路径的长度，路径中边缘权重的总和表示该路径的容量，成本或距离。如果路径权重在循环路径中为负，则该路径称为负循环。没有任何圆形路径的有向图称为有向无环图（DAG）。路径中的边缘数量表示路径的长度，路径中边缘权重的总和表示该路径的容量，成本或距离。如果路径权重在循环路径中为负，则该路径称为负循环。没有任何圆形路径的有向图称为有向无环图（DAG）。路径中的边缘数量表示路径的长度，路径中边缘权重的总和表示该路径的容量，成本或距离。如果路径权重在循环路径中为负，则该路径称为负循环。
如果图的每个顶点都连接到所有其他顶点，则称该图是完整的。如果完整图形中有N个顶点，则图形中将有N（N-1）/ 2条边。完整图通常也称为通用图。
Dijkstra的算法
Dijkstra算法是一种贪婪算法，用于在包含加权边的图形中查找源顶点和其他顶点之间的最短路径。如果算法在执行的每一步都利用局部最优解，并期望这种局部最优解最终会导致全局最优解，那么该算法就是贪婪的。因此，Dijkstra的算法基于贪婪的期望，即顶点A和C之间的全局最短路径内的顶点A和B之间的子路径也是A和B之间的最短路径。Dijkstra算法的局限性在于它可能如果边缘权重为负，则不起作用；如果图形中存在负循环，则绝对不起作用。该算法通过访问源顶点来测量从源顶点到所有其他顶点的最短路径，测量从源到其所有相邻顶点的路径长度，然后以最短路径访问其中一个邻居。算法迭代地重复这些步骤，直到完成访问图形中的所有顶点为止。
图1：Dijkstra算法的图示
图1说明了执行Dijkstra算法的逻辑步骤。该算法从维护两组开始。1]包含所有未访问顶点的集合，以及2]包含所有已访问顶点的集合，该集合最初是空的。另外，该算法为从源顶点到当前所测得的图中的每个顶点维持暂定最短路径的计数，并在从源顶点到每个顶点的路径上保留对先前顶点的引用。如图1所示，在步骤1，该算法将到源顶点的距离（在本例中为A）设置为其余顶点的无穷大，而从源到自身的距离为0。在步骤2，该算法进行测量到示例中到源顶点每个未访问的邻居B，C和E的暂定距离。顶点到源的距离被认为是暂定的，直到算法确认它是最短的距离。给定顶点U到源的暂定距离，使用公式d（U）+ d（U，V）测量顶点V的暂定距离，其中d（U）是顶点U到源顶点的暂定距离，并且d（U，V）是顶点U和V之间的边缘权重。如果新测量的暂定距离（即d（U）+ d（U，V））小于顶点V的先前分配的暂定距离，则d（ V），然后该算法将顶点V的暂定距离更新为新值，即d（V）= d（U）+ d（U，V）。如果新测量的距离小于先前分配的距离，则更新顶点距离的过程通常称为松弛。如果顶点的距离被更新为小于其先前测量距离的新测量距离，则该顶点被视为松弛。在该示例中，算法放宽了顶点B，C和E，并同时将顶点A设置为其先前顶点。该算法将当前源顶点A标记为已访问，将其弹出未访问的集合，并将其放置在已访问的集合中。然后，该算法将距离最短的相邻顶点确定为要访问的下一个顶点（在示例中为顶点C），并迭代到下一步。在步骤3中，该算法测量顶点C的未访问邻居（即B，D和E）相对于原始源顶点A的暂定距离。该算法使用新的暂定距离放宽顶点D并将其先前路径顶点设置为C 。该算法不会更新顶点B和E的暂定距离，因为它们通过顶点C测得的距离大于它们先前分配的暂定距离。与第2步一样，该算法将当前顶点C标记为已访问，将其弹出未访问的集合，并将其放置在已访问的集合中。然后，该算法将距离最短的未访问顶点确定为要访问的下一个顶点（在示例中为顶点B），然后迭代到下一步。算法将重复这样的步骤，直到所有顶点都标记为已访问或不再有要评估的连接顶点为止。然后，可以通过从已评估表中查找先前顶点来确定从源顶点到任何其他顶点的最短路径。例如，要确定从顶点A到顶点G的最短路径，{A，B，D，G}，最短距离为11。
在包含N个顶点的完整图形中，每个顶点都与所有其他顶点相连，该算法要访问的顶点数量将为N。而且，每次访问顶点时可能放松的顶点数量也为N。这样，Dijkstra算法的最坏情况下的时间复杂度约为NxN = N 2。
Bellman-Ford算法
Bellman-Ford算法用于在加权图中查找从源顶点到所有其他顶点的最短路径。与Dijkstra的算法不同，Bellman-Ford算法在存在负边缘权重时可以工作。该算法的核心集中在迭代放宽顶点到源顶点的路径距离。如果有N个顶点，则从源顶点到第N 个顶点的最大边数顶点可能是（N-1）个边。这样，该算法最多重复（N-1）次以放宽顶点距离。在每次迭代中，该算法均从源顶点开始，将传出的边沿移至连接的邻居，并评估每个邻居的暂定距离，如果该暂定距离小于先前值，则更新该暂定距离。然后，该算法移至下一个顶点，并重复遍历出站边缘并相应地放宽每个已连接邻居的暂定距离的过程。这样，在每次迭代中，该算法都会访问所有顶点并遍历所有边，从而尽可能地放松顶点距离。该算法重复最多（N-1）次放宽顶点的迭代，或者直到不再更新任何顶点为止。
图2：Bellman-Ford算法的图示
图2说明了执行Bellman-Ford算法的逻辑步骤。本质上，该算法维护一个表，该表包含从源顶点到每个顶点到每个顶点的估计的最短距离，该表可能会在每次迭代时更新。在示例图中，有4个顶点，因此该算法将执行最多4-1 = 3次迭代。在启动步骤中，该算法将表中从源顶点到示例中所有其他顶点的距离设置为无穷远，并将源顶点到自身的距离设置为0。在此步骤中，前一个顶点行为空。然后，该算法开始迭代1。该算法从源顶点开始，并评估到通过传出边连接的邻居的距离。在这个例子中 顶点A仅具有一个权重为-2的顶点到顶点C。因此，测得的顶点C与顶点A的距离为d（A）+ d（A，C），即0 – 2 = -2，小于C当前分配的无穷大值。因此，算法放宽了表中的顶点C，并将顶点A设置为C的前一个顶点。然后，算法移至示例中的下一个顶点B。由于顶点B的暂定距离仍然是无穷大，因此没有任何松弛点可以通过输出边缘连接。这样，该算法将移至下一个顶点C。顶点C的一个输出边与顶点D连接。由于C的当前暂定距离为-2，而顶点D的输出边权重为2，因此该算法将估算C的暂定距离。顶点D为-2 + 2 = 0，因为它小于顶点D的当前距离，即 无穷大，算法放宽顶点D，并将C设置为D的前任顶点。然后，算法移至顶点D。顶点D的权重为-1的顶点到顶点B。这样，该算法将顶点B的暂定距离评估为0 – 1 = -1，并且由于它小于B当前的无穷远距离，因此算法放宽了顶点B并将D设置为B的前任顶点。这样，算法完成了迭代1。算法然后开始了迭代2。与迭代1一样，算法在源顶点A处开始。由于顶点C是唯一由传出边连接的邻居，因此该算法会评估C与A的距离距离在-2处不变，因此算法移至下一个顶点B。在迭代1中测量的当前顶点B的暂定距离为-1。顶点B有两个传出边；一个连接顶点A，另一个连接顶点C。算法将评估顶点A和C相对于顶点B的暂定距离。由于顶点A的出站边权重为4，因此该算法将评估顶点A相对于顶点B的暂定距离当-1 + 4 = 3时。由于此距离大于顶点A的距离0，因此算法不会松弛顶点A。类似地，顶点C的输出边缘权重为3，并且该算法评估顶点C相对于顶点C的暂定距离。顶点B为-1 + 3 =2。由于它大于C的当前距离-2，因此算法不会更新表中的顶点C。然后，该算法移至顶点C。由于顶点C具有一个相对于顶点D的输出边缘，因此该算法将评估顶点D相对于顶点C的暂定距离。由于C的当前暂定距离为-2，并且顶点D的输出边缘权重为2，因此该算法将顶点D的暂定距离评估为-2 + 2 = 0，并且由于它与顶点D的当前距离相同，因此该算法不更新表中的顶点D。然后，算法移动到顶点B到顶点B的一个点。算法将顶点B的暂定距离评估为0 – 1 = -1，并且由于它与B的当前距离相同，因此该算法不会更新表中的顶点B 。这样，算法完成了迭代2。完成迭代2之后，算法确定在迭代2中没有顶点松弛，并且距离保持不变。这样，即使迭代3未完成，该算法也会停止执行。然后，可以通过从已评估表中查找先前顶点来确定从源顶点到任何其他顶点的最短路径。例如，要确定从顶点A到顶点B的最短路径，可以查找表格以找到B的前任顶点，即D。D的前任顶点为C，C的前任顶点为A。从顶点A到顶点B的最短路径是{A，C，D，B}，最短距离为-1。
本质上，Bellman-Ford算法在每次迭代中最大放松E个顶点，其中E是图中的边数。由于该算法最多执行（N-1）次，其中N是图形中的顶点数，因此松弛的总数将为E x（N-1）。这样，算法的时间复杂度约为（E x N）。在包含N个顶点的完整图形中，其中每个顶点都连接到所有其他顶点，边的总数将为N（N-1）/ 2。因此，弛豫的总数将为N（N-1）/ 2 x（N-1）。这样，Bellman-Ford算法的最坏情况下的时间复杂度约为N 3。
涵盖更多算法
在本文的后续部分中，我将用具体插图介绍其他几种基于图的最短路径算法。我希望这些插图有助于更好地理解此类算法背后的直觉。

关注 CDA人工智能学院 ，回复“录播”获取更多人工智能精选直播视频！