Johnson

• 本質：SPFA+Dijkstra
• 特點：多源最短路
• 適用對象：允許負權圖，不允許負環圖(負環：圖上邊權之和為負的環，負環圖無法求解最短路)
• 存儲結構：鏈式前向星
• 核心思想：先使用SPFA/Bellman-Ford計算潛在值，將所有邊的權值調整為非負，再對每個頂點使用Dijkstra
• 算法流程：定義潛在值數組$h$，點對間最短距離數組$dis[i][j]$
  • SPFA求解頂點潛在值：增設虛擬源點$s$，并在其與其他各點間增設一條$w=0$的邊。運行SPFA，計算出頂點的$dis$為潛在值$h$；若有負環則直接終止
  • 重新標定權值：對于圖中每一條邊，重新標定其權值為$w+=h[u]?h[v]$，目的是消除負權邊對于后續步驟的影響
  • 運行$V$次Dijkstra：對于每個頂點都運行一次Dijkstra，求出任意兩點對間最短路徑
  • 恢復初始邊權：恢復$dis[u][v]+=h[v]?h[u]$
• 復雜度：$O((V+E){\log }_{2}V+VE)$