johnson算法 johnson算法是什么
你是否想了解更多关于johnson算法和johnson算法是什么的知识？在本文中，小编将为您详细介绍这两个话题，帮助您更好地理解。
johnson算法最优顺序怎么算
根据约翰逊(S.M.Johson)—贝尔曼(R.Bellem)法则的基本思想:在TiA和TiB中找到最小对应的的工序,若为先行工序则排在最前,若为后续工序则排在最后。找出一个任务后,任务数量减少一项,在剩余的m-1项任务(施工段)中仍采用上述方法进行排序,以此类推直到剩余的任务数为0,最终得到的就是最优施工顺序。
johnson算法是什么
Johson算法是目前最高效的在无负环可带负权重的网络中求所有点对最短路径的算法.
Johson算法是Bellman-Ford算法,
Reweighting(重赋权重)和Dijkstra算法的大综合.
对每个顶点运用Dijkstra算法的时间开销决定了Johnson算法的时间开销.
每次Dijkstra算法(d堆PFS实现)的时间开销是O(
E
*
lgd(V)
).
其中E为边数,
V为顶点数,
d为采用d路堆实现优先队列ADT.
所以,
此种情况下Johnson算法的时间复杂度是O(
V
*
E
*
lgd(V)
).
算法: Johnson 算法
Johnson算法是用来解决在有负权重边图里的最短路径问题的，它主要了结合 Dijkstra算法和 Bellman-Ford算法。其实负数边的问题也可以用 Folyd算法来解决，只不过它的算法复杂度是，而 Johnson算法在稀疏图里复杂度是，会比 Folyd好一点。
我们考虑如下图结构
其中 0-> 1是负数的，是不能使用 Dijkstra去求最短路径的。这时我们可能会想到把全部的边都加上 5那大家不就都变成正数了？使用 Dijkstra求完最短路径后再减回 5那答案不就求到了么？这是一种思路，但是不完成正确，考虑如下图
这个图的 S到 T最短路径是 3（选上面那条路），但是所有边都加 1后，最短路径就变成了 4（选了下面那条路）。
而 Johnson的方法是通过给每个节点设置一个值，用这些节点的值去做 reweight，公式如下：
就是节点 X的值，这个值是通过 Bellman-Ford求出来的。
现在来说说怎么求这个。其实很简单，在这个图中添加一个虚拟的节点，如下图所示，为什么说是虚拟的呢，因为用完就删除了。这个虚拟节点指向所有的节点，而指向所有节点的边权重为 0。
就是用 Bellman-ford去求这个虚拟节点到每个节点的最短距离。以上图为例，每个节点的 h值为：
有了这些值后就可以对每条边进行 reweight操作了，最终的路径应该要减去开始节点的 h值，再加上结束节点的 h值。以 0-> 1-> 2为例，Dijkstra算法求出的路径是
然后再还原到真实的路径
以上面的图为例
上面都是 Johnson的关键步骤，下面就说说整个 Johnson算法的流程。
再来分析这个算法的时间复杂度，Bellman-Ford算法时间复杂度是，Dijkstra算法的时间复杂度是，因为每个节点都要做 Dijkstra，所以总的时间复杂度是。
约翰森算法的基本步骤
约翰森算法（Johnson's algorithm）是一种用于解决有向无环图（DAG）上的单源最短路径问题的算法。其基本思想是将原图转换为一个新的加权图，使其边的权重非负，然后使用Dijkstra算法或Bellman-Ford算法求解最短路径。
约翰森算法的基本步骤如下：
1.将原图的每个节点都连接到一个新的起点s，权重为0。同时，将这个起点和每个节点之间的边权重赋值为一个新的值，使其非负，例如可以使用Bellman-Ford算法或SPFA算法来处理。
2.使用Dijkstra算法或Bellman-Ford算法，以新的起点s为源点，求解从s到其他节点的最短路径。
3.将求解出的最短路径中，与新的起点s相连的边去掉，得到原图中每个节点到其他节点的最短路径。
需要注意的是，如果原图中存在负权边，则算法无法正确处理。因此，在使用约翰森算法之前，需要先判断原图是否存在负权边，如果存在，则需要使用其他算法来解决单源最短路径问题，例如Bellman-Ford算法或SPFA算法。
总的来说，约翰森算法的基本思想是将原图转换为一个非负权重的加权图，然后使用Dijkstra算法或Bellman-Ford算法求解最短路径。该算法可以在时间复杂度为O(mnlogn)的情况下求解单源最短路径问题，其中n为节点数，m为边数。
好了，关于johnson算法和johnson算法是什么的问题到这里结束啦，希望可以解决您的问题哈！