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 算法中实现对负环的检测，该算法适用于带有负边的图。