一、算法简析\(Johnson\)算法可以求解带负权边的中小图的全源最短路径。算法步骤：建立虚拟源点\(0\)，从\(0\)至其它各点添加权值为\(0\)有向边。用\(spfa\)算法求出从\(0\)至其它各点的最短路径h[i]。将原图中边的权值改为：\(w(u,v)+h[u]-h[v]\)，建立了一张新图。以