在带权有向图中，寻找从起点到终点的路径使得边权总和最小，这是图论中最基础也最实用的问题之一。根据图的特性（是否有负权边、是否需要全源路径等），我们通常有三种经典算法可供选择：Dijkstra、Bellman-Ford 和 Floyd-Warshall。
Dijkstra 算法
Dijkstra 是单源最短路径的经典贪心算法。它适用于没有负权边的图。核心思想是从起点出发，每次从未确定最短路径的节点中选出距离最小的一个，用它去'松弛'所有邻接点，标记该节点为已确定，直到所有节点处理完毕。
在实际实现中，我们需要维护一个距离数组和一个前驱数组。初始化时，起点距离为 0，其余为无穷大。每一轮迭代都扫描未访问节点找到当前最小值，然后更新邻居的距离。如果某条路径通过当前节点能更短地到达邻居，就更新距离并记录前驱。
// 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_dist = MAX_W;
for (size_t i = 0; i < n; ++i) {
if (!S[i] && dist[i] < min_dist) {
u = i;
min_dist = dist[i];
}
}
S[u] = true;
// 松弛更新 u 连接顶点 v
// srci -> u + u -> v < srci -> v 更新
for (size_t v = 0; v < n; ++v) {
(!S[v] && _matrix[u][v] != MAX_W && dist[u] + _matrix[u][v] < dist[v]) {
dist[v] = dist[u] + _matrix[u][v];
pPath[v] = u;
}
}
}
}
