一、Dijkstra 算法
最短路径问题是指，从在带权的有向图中从某一顶点出发，找到通往另一顶点的最短路径，'最短'指的是沿路径各边的权值总和最小。
Dijkstra 算法是单源最短路径的经典贪心算法，只能用于没有负权的图。它从起点出发，每次选当前距离最小且未确定最短路径的节点，用它去松弛（更新）所有邻接点的最短路径估计值，标记该节点为'已确定'，重复此过程直到所有节点处理完毕，最终得到起点到图中所有节点的最短路径。
// src 是选定的起点，dist 记录起点到各点的最短路径，pPath 记录到每个点的最短路径的前驱顶点下标
void Dijkstra(const V& src, vector<W>& dist, vector<int>& pPath){
size_t srci = GetVertexIndex(src);
size_t n = _vertexs.size();
dist.resize(n, MAX_W);
pPath.resize(n, -1);
dist[srci] = 0;
pPath[srci] = srci;
// 已经确定最短路径的顶点集合
vector<bool> S(n, false);
for (size_t j = 0; j < n; ++j) {
// 选最短路径顶点且不在 S 更新其他路径
int u = 0;
W min = MAX_W;
for (size_t i = 0; i < n; ++i) {
if (S[i] == false && dist[i] < min) {
u = i;
min = dist[i];
}
}
S[u] = true;
// 松弛更新 u 连接顶点 v srci->u + u->v < srci->v 更新
for (size_t v = 0; v < n; ++v) {
if (S[v] == false && _matrix[u][v] != MAX_W && dist[u] + _matrix[u][v] < dist[v]) {
dist[v] = dist[u] + _matrix[u][v];
pPath[v] = u;
}
}
}
}
二、Bellman_Ford 算法
Bellman-Ford 算法能用来解决负权图的单源最短路径问题，但是它的时间复杂度高于 Dijkstra 算法，本质是暴力求解。从起点出发，把图里所有边从头到尾松弛一遍，重复 n 次，就能算出起点到所有点的最短路径；因为任何最短路径最多只经过 n-1 条边。跑完之后再扫一遍所有边，如果还能更新距离，就说明图里有负权回路，最短路径不存在。
