稀疏图带负边的全源最短路Johnson算法
BellmanFord算法
Johnson算法解决的问题
带负权的稀疏图的全源最短路
算法流程
重新设置的每条边的权重都大于或等于0，跑完Djikstra后得到的全源最短路，记得要还原，即：f(u,v) = d(u,v) - h[u] + h[v]
例题
带负权的稀疏图的全源最短路
重新设置的每条边的权重都大于或等于0，跑完Djikstra后得到的全源最短路，记得要还原，即：f(u,v) = d(u,v) - h[u] + h[v]
例题