图的最短路径问题
在带权图中，从某一顶点出发找到通往另一顶点的路径，使得沿路径各边的权值总和最小，这就是最短路径问题。解决这类问题主要有三种经典算法，它们各自适用于不同的场景。
Dijkstra 算法：贪心策略的单源求解
Dijkstra 算法是单源最短路径的经典贪心算法，只能用于没有负权的图。它从起点出发，每次选当前距离最小且未确定最短路径的节点，用它去松弛（更新）所有邻接点的最短路径估计值，标记该节点为'已确定'，重复此过程直到所有节点处理完毕。
简单来说，就是不断找离起点最近的未访问点，用这个点去更新周围点的距离。下面是一个基于邻接矩阵的实现示例，注意代码中 MAX_W 代表无穷大。
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] && 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] && _matrix[u][v] != MAX_W && dist[u] + _matrix[u][v] < dist[v]) {
dist[v] = dist[u] + _matrix[u][v];
pPath[v] = u;
}
}
}
}
