Johnson 全源最短路径算法

Johnson 算法是一种用于求解给定加权有向图中所有节点对之间的最短路径的算法。它可以处理具有负权边的图，并且时间复杂度为O(n^2logn+m*n)，其中n是图中节点数，m是边数。

算法的基本思想是通过将每条边的权重增加一个非负的常数使得所有边权变为非负，然后使用Dijkstra算法或Bellman-Ford算法求解每个节点到其他节点的最短路径。最后，通过恢复原始权重来得到最终的最短路径。

具体来说，算法的步骤如下：

1. 对原始图进行转换，增加一个新的节点s，并添加从s到所有其他节点的边，边权均为0。

2. 使用Bellman-Ford算法计算s到所有其他节点的最短路径，如果存在负环则停止算法。

3. 对转换后的图进行边权重的修正，对于边(u, v)，设其原始权重为w(u, v)，则修正后的权重为w'(u, v) = w(u, v) + h(u) - h(v)，其中h(u)和h(v)分别为Bellman-Ford算法中计算得到的s到u和s到v的最短路径长度。

4. 对于修正后的图，使用Dijkstra算法求解每个节点到其他节点的最短路径，注意在计算路径长度时需要根据修正前的权重计算。

5. 根据修正后的权重和Dijkstra算法计算得到的最短路径长度，恢复原始权重，得到最终的最短路径。

Johnson算法的核心在于通过将边权重修正为非负来避免负权边对Dijkstra算法的影响，同时通过Bellman-Ford算法计算每个节点到源点的最短路径来计算修正后的权重。但是，由于需要进行两次最短路径的计算，因此算法的时间复杂度比较高。

相关问题

介绍最短路径算法的发展历程

最短路径算法是指在图中找到两个节点之间的最短路径的算法。下面是最短路径算法的发展历程：

1. Dijkstra算法：

Dijkstra算法是最短路径算法中最早的算法之一，由荷兰计算机科学家Edsger Dijkstra于1956年发明。该算法基于贪心思想，在加权图中寻找单个源节点到其他所有节点之间的最短路径。该算法的时间复杂度为O(n^2)，其中n为节点数。

2. Bellman-Ford算法：

Bellman-Ford算法是由美国数学家Richard Bellman和 Lester Ford Jr.在1958年发明的。该算法可以处理具有负权边的图。该算法使用动态规划的思想，通过多次迭代计算，找到单个源节点到其他所有节点之间的最短路径。该算法的时间复杂度为O(nm)，其中n为节点数，m为边数。

3. Floyd算法：

Floyd算法也称为插点法，是由美国计算机科学家Robert Floyd在1962年发明的。该算法可以处理具有负权边的图。该算法基于动态规划的思想，通过求解所有节点对之间的最短路径，找到单个源节点到其他所有节点之间的最短路径。该算法的时间复杂度为O(n^3)，其中n为节点数。

4. A*算法：

A*算法是由Peter Hart, Nils Nilsson和 Bertram Raphael在1968年发明的。该算法是一种启发式搜索算法，通过估计每个节点到目标节点的距离，来选择下一步要走的节点。该算法可以处理具有负权边的图，但是需要满足一定的启发式条件。该算法的时间复杂度取决于启发式函数的复杂度。

5. 迪杰斯特拉算法的优化：

在Dijkstra算法中，使用了一个优先队列来存储节点，以便快速找到下一个要处理的节点。但是，当图很大时，优先队列的维护成本很高。因此，出现了一些优化算法，如斐波那契堆（Fibonacci heap）和D-堆（D-ary heap），它们可以更有效地维护优先队列，从而提高了算法的效率。

6. Johnson算法：

Johnson算法是由Neil Johnson在1977年发明的，它可以处理具有负权边的图。该算法先通过Bellman-Ford算法计算出每个节点到其他所有节点的最短路径的估计值，然后使用这个估计值来改变原始边的权值，并应用Dijkstra算法来计算最短路径。该算法的时间复杂度为O(nmlogn)，其中n为节点数，m为边数。

7. SPFA算法：

SPFA算法是由李煜东在2001年发明的。该算法可以处理具有负权边的图。该算法使用队列来存储节点，通过不断更新每个节点到源节点的距离，来找到最短路径。该算法的时间复杂度最坏情况下为O(nm)，但是在实际应用中，它通常比Bellman-Ford算法和Dijkstra算法更快。

经过多个点的最短路径算法

经过多个点的最短路径算法是一种求解从起点到多个目标点的最短路径的算法。其中，最常用的算法是多源最短路径算法，如 Floyd 算法和 Johnson 算法。Floyd 算法基于动态规划思想，通过对每一对顶点之间的距离进行比较，逐步更新路径长度，直到求得所有顶点之间的最短路径。而 Johnson 算法则是首先对原图进行一些变换，然后再使用 Dijkstra 算法求解每个源点到其他顶点的最短路径。这两种算法都能够有效地解决经过多个点的最短路径问题。