1.无负权边:dijkstra 理由:算法的前提是st数组里的都是已经确定是最短路的,若存在负权边会破坏这个前提。
2.有负权边:spfa
自我感觉spfa能求,还未验证过
1.>=1:dijkstra 理由:算法的前提是st数组里的都是已经确定最小值的,若存在<1的话会破坏这个前提。
2.>0:spfa, 相当于后续还有可能会变小
1.0-1:dijkstra
2.>0:spfa