DSA 最短路径

最短路径问题

最短路径问题在计算机科学领域非常有名。

解决最短路径问题意味着在图中找到两个顶点（或节点）之间的最短路径。

在最短路径问题中，图可以代表任何东西，从道路网络到通信网络，其中顶点可以是交叉路口、城市或路由器，边可以是道路、飞行路径或数据链路。

上图中从顶点 D 到顶点 F 的最短路径是 D->E->C->F，总路径权重为 2+4+4=10。从 D 到 F 的其他路径也是可能的，但它们有更高的总权重，因此不能被认为是最短路径。

最短路径问题的解决方案

Dijkstra 算法 和 Bellman-Ford 算法 找到从一个起点到所有其他顶点的最短路径。

解决最短路径问题意味着检查图中的边，直到找到一条路径，我们可以使用沿边的最低可能的组合权重从一个顶点移动到另一个顶点。

这条构成路径的边的权重之和称为**路径成本**或**路径权重**。

寻找最短路径的算法，如 Dijkstra 算法 或 Bellman-Ford 算法，找到从一个起点到所有其他顶点的最短路径。

首先，算法将起点到所有顶点的距离设置为无限长。当算法运行时，顶点之间的边会被一遍又一遍地检查，并且可能多次找到更短的路径，直到最终找到最短路径。

每次检查一条边并找到并更新到一个顶点的更短距离时，称为**松弛**或**松弛**一条边。

正边权和负边权

一些寻找最短路径的算法，如 Dijkstra 算法，只能在所有边都是正数的图中找到最短路径。这些具有正距离的图也最容易理解，因为我们可以将顶点之间的边视为位置之间的距离。

如果我们将边权解释为从一个顶点到另一个顶点的损失的钱，那么上图中从顶点 A 到 C 的 4 的正边权意味着我们必须花费 4 美元才能从 A 到 C。

但图也可以有负边，对于这样的图，可以使用 Bellman-Ford 算法 来找到最短路径。

同样，如果边权代表损失的钱，那么上图中从顶点 C 到 A 的 -3 的负边权可以理解为一条边，从 C 到 A 赚的钱比损失的钱更多。例如，如果从 C 到 A 的燃油成本为 5 美元，而我们在 C 收取包裹并在 A 送达后获得 8 美元的报酬，则损失的钱为 -3，这意味着我们实际上总共赚了 3 美元。

最短路径问题中的负循环

如果图包含负循环，则无法找到最短路径。

负循环意味着存在一条路径，你可以循环走，构成这条循环的边的总路径权重为负数。

在下图中，路径 A->E->B->C->A 是一个负循环，因为总路径权重为 5+2-4-4=-1。

无法在包含负循环的图中找到最短路径的原因是，始终有可能继续运行算法以找到更短的路径。

例如，假设我们正在寻找上图中从顶点 D 到所有其他顶点的最短距离。首先，我们发现从 D 到 E 的距离为 3，只需沿着边 D->E 走即可。但在此之后，如果我们在负循环 E->B->C->A->E 中走一圈，则 E 的距离变为 2。再走一圈，距离变为 1，更短，以此类推。我们始终可以在负循环中走一圈以找到更短的距离到 E，这意味着永远无法找到最短距离。

幸运的是，Bellman-Ford 算法在包含负边的图上运行，可以实现负循环检测。