基于稀疏图的约翰逊算法(稀疏表示算法)的详细解

Johnson算法是一种求解负权边稀疏图最短路径问题的算法。其主要思想是通过一些变换使图中不存在负权环，然后用Dijkstra算法求解每对顶点之间的最短路径。以下是约翰逊算法的详细步骤:

在图中添加一个新的顶点S，从S到图中的每个顶点V添加一条权重为0的边。这样，就得到一个新的图形G′。Bellman-Ford算法用于计算图中从顶点S到每个顶点V的最短路径长度h(v)。如果贝尔曼-福特算法检测到图中存在负权环，则算法终止，因为这意味着没有最短路径。对于原图G中的每条边(u，v)，边的权重更新为w'(u，v) = w(u，v)+h(u)-h(v)。这一步的目的是消除负权重边，因为当原始图中存在负权重边时，Dijkstra算法无法正确工作。对于新图g’，使用Dijkstra算法计算每个顶点U到每个顶点V的最短路径长度d’(U，V)根据步骤3中的变换，最短路径长度d’(U，V)实际上是原图g中顶点U到顶点V的最短路径长度，对于每对顶点U和V，计算最短路径长度d(u，V)= d’(U， v)-h(u)+h(v)从原图G中的顶点u到顶点v，最后根据步骤5得到的结果，可以得到原图G中每对顶点之间的最短路径长度。 约翰逊算法的时间复杂度为O(V ^ 2 log v+ VE)，其中V为顶点数，E为边数。尽管该算法在稀疏图上的时间复杂度相对较高，但它可以处理具有负权边的图，并且具有比其他算法更好的性能。

以上内容来自互联网，不代表本站全部观点！欢迎关注我们:zhujipindao。com