椰蘿Yerosius的博客

摘要： SPFA 本質(zhì)：DP，基于隊列優(yōu)化的Bellman-Ford 特點：單源最短路，求解一個源點到其他所有點的最短距離，不穩(wěn)定 適用對象：允許負權(quán)圖，不允許負環(huán)圖(負環(huán)：圖上邊權(quán)之和為負的環(huán)，負環(huán)圖無法求解最短路)，同時也可求最長路。 存儲結(jié)構(gòu)：鏈式前向星 核心思想：用隊列保存松弛邊的出度點，調(diào)整其鄰接 閱讀全文