迪杰斯特拉算法
迪杰斯特拉算法是由荷兰计算机科学家艾兹赫尔·迪杰斯特拉（Edsger W. Dijkstra）在 1956 年提出的，用于解决单源最短路径问题的经典算法。该算法的目标是从一个起始顶点找到到图中其他顶点的最短路径。
主要特点
- 适用于带权图，其中权重为非负数。（为什么只适用于非负数，因为迪杰斯特拉的思想是贪心测量，当有负权引入的时候，贪心策略将不再适用）
- 解决从单个源点到其他所有顶点的最短路径问题。
- 时间复杂度：当使用优先队列（例如堆）时，复杂度为 O(E log V)，其中 V 为顶点数量，E 为边的数量。
基本思想
Dijkstra 算法通过不断探索距离最近的顶点，逐步扩展其最短路径的已知范围，直到找到从源点到所有其他顶点的最短路径。该算法基于贪心策略：每一步选择尚未处理的、距离源点最近的顶点进行扩展。
算法步骤
- 初始化：
- 将起始顶点的距离设为 0，其余所有顶点的距离设为∞（表示不可达）。
- 使用一个优先队列（或最小堆）来存储顶点及其当前的最短距离。
- 取距离源点最近的顶点，并标记为已处理。
- 对于该顶点的每个邻接顶点，更新其最短距离（如果通过当前顶点可以获得更短的路径，则更新距离）。
- 重复步骤 2 和 3，直到所有顶点都被处理过，或优先队列为空。
示例
假设起点为 s，初始化距离，更新邻居，贪心选择最近点 y，继续更新...最终得到最短路径。 具体过程如下： 第一步按照迪杰斯特拉的表述应该将起点到起点的最短路径初始化为 0，起点到另外其他点的距离初始化为正无穷。 这里我们更新完 s 点之后，应该更新和 s 点相连的点的最短路径了，由于之前 s 到 t 点和到 y 点的最短路径是正无穷，由于 st 和 sy 都小于两个最短路径，所以更新两个最短路径。 根据贪心策略，更新出来的两个最短路径，sy 更小，所以我们应该更新 y 相连的路径。 接下来更新 y 连接的点的最短路径。 由于原本 s 到 t 的最短路径是 10，但是现在的最短路径更新了之后是 8，所以更新结果，由于之前 s 到 x 的最短路径是正无穷，所以现在将最短路径更新为 14，s 到 z 也是相同的，因为之前的最短路径是正无穷，所以现在将最短路径更新为 7。 在这三条最短路径中选择最短的那条，这里就应该以 z 为新的起点。 更新 z 连接的顶点，z 一共有两条边，一条是 zs，一条是 zx，由于 s 到 s 是最近的 0，所以这里不需要更新，由于之前 s 到 x 的距离是 14，所以这里更新 s 到 x 的距离。 接下来再从剩下的边中，选择最小的路径。 从 t 点开始只有一条路径，所以这里 t 到 x，tx 是 1，由于之前的 st 的最短路径是 8，所以此时的最短路径是 9,9<13 所以这里应该更新最短路径为 9。 这里最短路径算是更新完了。
实现迪杰斯特拉算法
基本步骤
首先假设我们有如下的一个图，灰色的点代表起点，我们需要从起点开始算每个点到起点的最短路径。
算法思路
由于这里我们涉及到最短路径，所以应该开辟一个 dist 数组，我们来想一想一个 dist 数组是否能解决问题，很显然是不能的，我们还需要一个数组，记录当前最短路径的前一个顶点的下标，在遍历的时候我们可以索引每一个顶点了。
代码展示：
void Dijkstra(const V& src, vector<W>& dist, vector<int>& pPath){
//获取起点的下标
size_t srci = GetVertexIndex(src);
//确定节点的数量
size_t n = _vertexs.size();
dist.(n, MAX_W);
pPath.(n, MAX_W);
dist[srci] = ;
pPath[srci] = srci;
;
( j=;j<n;j++){
u = ;
W min = MAX_W;
( i =;i < n;i++){
(S[i]== && dist[i]< min){
u = i;
min = dist[i];
}
}
S[u]= ;
( v =;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;
}
}
}
}
