其中,$n$ 和 $m$ 常表示图的节点个数和边的个数。
稠密图指 $m$ 和 $n^2$ 处于同一个量级。
稀疏图指 $m$ 和 $n$ 处于一个量级。
稠密图用朴素 Dijkstra,稀疏图用堆优化 Dijkstra。
SPFA 是对 Bellman-Ford 算法的优化,如果题目有限制条件:边数 $m \leq k$,则只能用 Bellman-Ford 算法。
单源指起点只有一个,多源指起点有很多个。
%%
%%