在实际工程中，我们经常需要解决从一点到另一点代价最小的问题，这就是图论中的最短路径。根据图的特性（是否有负权边、单源还是多源），我们需要选择不同的算法策略。
Dijkstra 算法
Dijkstra 是单源最短路径的经典贪心算法，前提是不能有负权边。它的核心逻辑很直观：从起点出发，每次从未确定的节点中选出距离最小的那个，用它去更新邻居的距离，标记为已确定，直到所有点都处理完。
这里有个细节要注意：松弛操作时，只有当 dist[u] + weight < dist[v] 时才更新，否则说明当前路径已经是最优或更差的了。
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;
// S 集合记录已确定最短路径的顶点
vector<bool> S(n, false);
for (size_t j = 0; j < n; ++j) {
// 1. 选最短路径顶点且不在 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;
// 2. 松弛更新 u 连接的顶点 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;
}
}
}
}
