大家好，欢迎来到IT知识分享网。

1 算法步骤

  Johnson算法分为三步：
  1. 先使用bellman-ford算法，计算单源到其他点的最短路径；
  2. 利用计算结果去重赋权reweight，使得没有负数权重；
  3. 循环调用dijikstra算法计算所有点的权重。
  4. 所有点的权重再换算回来，得到结果。
  复杂度为$O(nm+n^{2}logn)$(计算机学科的对数以2为底)，从理论上讲这是目前世界上性能最高的全源负权最短距离算法。
  重赋权的计算也不难。步骤分为以下几步：
  1. 图增加一个新的节点H，使图变成增广图$G^{\prime }$，新节点H与图中每一个节点都相连，并且距离为0；
  2. 使用bellman-ford算法计算H与其他点的单源最短路径。
  3. 计算出来后，用以下公式进行重赋权
$$W_2(x,y)=W_1(x,y)+h(x)-h(y)$$
  4. 然后移除新的顶点H，因为这是个虚拟节点，所以在计算完成之后，要将图进行恢复。

2 重赋权为什么非负

  为了解释重赋权公式，我画一张图，图中$h(x)$代表虚拟点h到x的最短路径，$h(y)$代表虚拟点h到y的最短路径，$w(x,y)$代表x指向y的边的权重：

  因为是最短路径，所以必定有以下公式：
$$\begin{gathered} h(x)+w(x,y)\ge h(y) \\ \therefore w(x,y)+h(x)-h(y)\ge 0 \end{gathered}$$
  所以重赋权之后，一定不会出现负权重。

3 为什么可以重赋权

  但是还有一个问题，为什么可以这样重赋权？我们必须证明一点，重赋权之后还是最短路径。假设$u_0$到$v_k$的最短路径为$p$。在p上，除了$v_0$和$v_k$外还有$v_1,v_2,\dots ,v_{k-1}$这些点。所以最短路径总权重，也就是最短距离$d(v_0,v_k)$就是：
$$d(v_0,v_k)=\sum _{i=0}^{k-1}w(v_i,v_{i+1})$$
  我们进行重赋权，重赋权公式为：
$$w^{\prime }(x,y)=w(x,y)+h(x)-h(y)$$
  那么重赋权之后的最短路径总权重为：
$$d^{\prime }(v_0,v_k)=\sum _{i=0}^{k-1}{w}^{\prime }(v_i,v_{i+1})=\sum _{i=0}^{k-1}w(v_i,v_{i+1})+h(v_i)-h(v_{i+1})$$
  展开之后，发现这是个伸缩数列，中间的$h(v_1)\dots h(v_{k-1})$全部是一正一负，相加之后被消去了，只剩下了首尾：
$$\begin{gathered} d^{\prime }(v_0,v_k) \\ =w(v_0,v_1)+h(v_0)-h(v_1) \\ +w(v_1,v_2)+h(v_1)-h(v_2) \\ +\cdots \\ +w(v_{k-2},v_{k-1})+h(v_{k-2})-h(v_{k-1}) \\ +w(v_{k-1},v_k)+h(v_{k-1})-h(v_k) \\ =h(v_0)-h(v_k)+\sum _{i=0}^{k-1}w(v_i,v_{i+1}) \\ =d(v_0,v_k)+h(v_0)-h(v_k) \end{gathered}$$
  所以证明了，最短路径上，重赋权之后的权重和是原权重和的重赋权。巧妙地利用伸缩数列，是Johnson算法的精妙之处。而其他博文是很少讲到这里的，感觉有点意思的，有意思的，可以收藏本文，也可以顺势关注一波。

4 小例子

  创建虚拟节点H

  重赋权：

5 python实现

  Python代码如下：

class WeightedEdge:

    def __init__(self, from_index, to_index, weight):
        self.__from_index = from_index
        self.__to_index = to_index
        self.__weight = weight

    @property
    def weight(self):
        return self.__weight

    @weight.setter
    def weight(self, value):
        self.__weight = value

    @property
    def from_index(self):
        return self.__from_index

    @from_index.setter
    def from_index(self, value):
        self.__from_index = value

    @property
    def to_index(self):
        return self.__to_index

    @to_index.setter
    def to_index(self, value):
        self.__to_index = value

    def __repr__(self):
        return f'{ 
     self.from_index} to { 
     self.to_index} = { 
     self.__weight}'

    def __str__(self):
        return f'{ 
     self.__from_index} to { 
     self.__to_index} = { 
     self.__weight}'


class WeightedGraph:
    def __init__(self):
        self.__vertices = []
        self.__edges = []

    def bellman_ford(self, start_index):
        # 设置初始化距离全部为负无穷
        d = [float('inf') for _ in self.__vertices]
        predecessors = [None for _ in self.__vertices]
        d[start_index] = 0
        for _ in self.__vertices:
            for e in self.__edges:
                u = e.from_index
                v = e.to_index
                dv = d[v]
                d[v] = min(d[v], d[u] + e.weight)
                if dv != d[v]:
                    predecessors[v] = u

        for e in self.__edges:
            u = e.from_index
            v = e.to_index
            if d[v] > d[u] + e.weight:
                raise RuntimeError('存在负权重环')
        return d, predecessors

    def dijkstra(self, s):
        cost = [float('inf') for _ in self.__vertices]
        cost[s] = 0
        parent = [None for _ in self.__vertices]
        parent[s] = -1
        visited = set()
        while len(visited) < len(self.__vertices):
            u = self.shortest(visited, cost)
            visited.add(u)
            for e in self.__edges:
                if e.from_index == u:
                    v = e.to_index
                    if cost[v] > cost[u] + e.weight:
                        cost[v] = cost[u] + e.weight
        return cost

    def shortest(self, visited, cost):
        s = None
        for u in range(0, len(self.__vertices)):
            if u in visited:
                continue
            if s is None:
                s = u
            elif cost[u] < cost[s]:
                s = u
        return s

    def johnson(self):

        # 新加一个虚拟节点
        self.__vertices.append('H')
        n = len(self.__vertices)
        for i in range(0, n - 1):
            self.__edges.append(WeightedEdge(n - 1, i, 0))

        h = self.bellman_ford(n - 1)[0]
        # 重建权重
        for e in self.__edges:
            e.weight = e.weight + h[e.from_index] - h[e.to_index]
        # 删除后，使用
        self.__vertices.pop()
        self.__edges = self.__edges[0:-n + 1]
        distance = [None for _ in range(len(self.__vertices))]
        for s in range(len(self.__vertices)):
            dijkstra = self.dijkstra(s)
            for i, e in enumerate(dijkstra):
                dijkstra[i] = e - h[s] + h[i]
            distance[s] = dijkstra
        # 恢复权重
        for e in self.__edges:
            e.weight = e.weight - h[e.from_index] + h[e.to_index]
        return distance

    def to_dot(self):
        s = 'digraph s {\n'
        for v in self.__vertices:
            s += f'"{ 
     v}";\n'
        for e in self.__edges:
            s += f'\"{ 
     self.__vertices[e.from_index]}\"->"{ 
     self.__vertices[e.to_index]}"[label="{ 
     e.weight}"];\n'
        s += '}\n'
        return s

    @property
    def vertices(self):
        return self.__vertices

    @vertices.setter
    def vertices(self, value):
        self.__vertices = value

    @property
    def edges(self):
        return self.__edges

    @edges.setter
    def edges(self, value):
        self.__edges = value

  测试数据：

import unittest

from com.youngthing.graph.johnson import WeightedEdge
from com.youngthing.graph.johnson import WeightedGraph


class MyTestCase(unittest.TestCase):
    def test(self):
        # 定义一个图，测试BFS搜索
        graph = self.create_graph()
        path = graph.johnson()
        print(path)

    def create_graph(self):
        vertices = ['A', 'B', 'C', 'S']
        edges = [
            WeightedEdge(0, 1, 2),
            WeightedEdge(2, 0, -2),
            WeightedEdge(2, 1, 1),
            WeightedEdge(3, 0, 1),
            WeightedEdge(3, 2, 2)
        ]
        graph = WeightedGraph()
        graph.vertices = vertices
        graph.edges = edges
        return graph

  测试结果：

[[0, 2, inf, inf], [inf, 0, inf, inf], [-2, 0, 0, inf], [0, 2, 2, 0]]