一、最短路算法
1. Dijkstra 算法
Dijkstra 算法的原理是贪心，执行步骤如下：
- 令 \(dis_s=0\)，其余为正无穷；
- 在未被标记过的点中，选择 \(dis\) 最小的点 \(u\)，标记它；
- 枚举 \(u\) 的出边，更新 \(v\) 的 \(dis\)。
重复步骤 2,3 直到所有点被标记。
在步骤 2 中找到的全局最小值，可以证明不会被再次更新了——其他的点 \(dis\) 已经大于 \(dis_u\)，再加上若干条非负权边（Dijkstra 只能在非负权图上使用），显然无法更新 \(dis_u\)。
找全局最小值可以用堆优化，时间复杂度为 \(O((m+n)\log n\)。