迪杰斯特拉算法概述
算法描述：
1. 初始化：
o 将起点 s 的距离设置为 0，其余顶点的距离设为无穷大。
o 创建一个集合 unvisited，其中包含图中的所有顶点。
o 初始化优先队列（通常使用最小堆），将起点 s 放入队列，根据距离值进行排序。
2. 迭代过程：
o 当 unvisited 集合不为空时，执行以下步骤：
o 从优先队列中取出当前已知距离最小的顶点 u，并将其标记为已访问（从 unvisited 中移除）。
o 遍历与顶点 u 相邻的所有顶点 v：
o 计算通过顶点 u 到达顶点 v 的新路径长度（即当前顶点 u 的距离加上 u 到 v 的边权值）。
o 如果新路径长度小于之前记录的顶点 v 的距离，则更新顶点 v 的距离，并将 v 的前驱节点指向 u。
o 将顶点 v 更新后的信息放入优先队列中，按照新的距离值重新排列。
3. 终止条件：
o 当优先队列为空时，说明所有可达顶点都已经找到了从源点出发的最短路径，算法结束。
C++实现示例：
下面是一个简化的基于优先队列（std::priority_queue）实现的Dijkstra算法示例：
#include <iostream>
#include <vector>
#include <queue>
#include <limits>
using namespace std;
const int INF = numeric_limits<int>::max(); // 表示无穷大的常量
// 假设有这样的结构体来表示图中的边和顶点
struct Edge {
int from, to;
int weight;
};
struct Node {
int id;
int dist; // 从源点到达此顶点的最短距离
bool visited; // 标记是否已经访问过
int prev; // 指向前一个顶点，用于构建最短路径
};
void dijkstra(vector<Node>& nodes, vector<Edge>& edges, int src) {
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
nodes[src].dist = 0;
pq.push({ 0, src }); // 将源点及其距离0加入优先队列
while (!pq.empty()) {
int current = pq.top().second;
pq.pop();
if (nodes[current].visited)
continue;
nodes[current].visited = true;
for (Edge& e : edges) {
if (e.from == current && nodes[e.to].visited == false) {
int newDist = nodes[current].dist + e.weight;
if (newDist < nodes[e.to].dist) {
nodes[e.to].dist = newDist;
nodes[e.to].prev = current;
pq.push({ nodes[e.to].dist, e.to });
}
}
}
}
}
// 可以进一步添加函数来打印最短路径等操作请注意，这个示例假设了一个简化的情况，实际应用中可能需要对数据结构和具体实现细节进行调整以适应不同的场景，例如，可以使用邻接矩阵或邻接表来存储图的信息。此外，在更复杂的版本中，可能还需要额外的数据结构来存储每一步的状态变化。