带权重的最短路径搜索是图结构处理中的核心需求，迪杰斯特拉算法通过贪心策略逐步确定起点到各个顶点的最短距离，是处理非负权重图最短路径问题的经典方案，下面介绍其C++实现方式。
算法核心原理
迪杰斯特拉算法的核心逻辑是维护一个距离数组，记录起点到每个顶点当前已知的最短距离，每次从还未确定最短距离的顶点中选取距离最小的顶点，将其标记为已确定，然后尝试通过该顶点更新其邻接顶点的距离。算法要求图中所有边的权重为非负数，否则无法保证正确性。
基础实现步骤
- 初始化距离数组，起点距离设为0，其余顶点距离设为无穷大
- 每次选取未访问顶点中距离最小的顶点作为当前顶点
- 遍历当前顶点的所有邻接边，尝试更新邻接顶点的距离
- 重复上述步骤直到所有顶点都被访问
图的存储结构
这里使用邻接表存储带权重的无向图，每个顶点对应一个列表，列表中存储邻接顶点和对应的边权重。首先定义图的结构：
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
// 定义邻接边结构，存储邻接顶点和边权重
struct Edge {
int to; // 邻接顶点编号
int weight; // 边权重
Edge(int t, int w) : to(t), weight(w) {}
};
// 定义图结构，使用邻接表存储
class WeightedGraph {
private:
int vertexCount; // 顶点数量
vector<vector<Edge>> adjList; // 邻接表
public:
// 构造函数，初始化顶点数量
WeightedGraph(int n) : vertexCount(n) {
adjList.resize(n);
}
// 添加无向边
void addEdge(int u, int v, int weight) {
adjList[u].push_back(Edge(v, weight));
adjList[v].push_back(Edge(u, weight));
}
// 获取邻接表
vector<vector<Edge>> getAdjList() {
return adjList;
}
// 获取顶点数量
int getVertexCount() {
return vertexCount;
}
};
基础版迪杰斯特拉实现
基础版本不使用优先队列，每次遍历所有顶点找到未访问的最小距离顶点，时间复杂度为O(n²)，适合顶点数量较少的场景：
// 基础版迪杰斯特拉算法实现
vector<int> dijkstraBasic(WeightedGraph& graph, int start) {
int n = graph.getVertexCount();
vector<int> dist(n, INT_MAX); // 距离数组，初始为无穷大
vector<bool> visited(n, false); // 访问标记数组
dist[start] = 0; // 起点距离为0
for (int i = 0; i < n; i++) {
// 找到未访问顶点中距离最小的顶点
int u = -1;
int minDist = INT_MAX;
for (int j = 0; j < n; j++) {
if (!visited[j] && dist[j] < minDist) {
minDist = dist[j];
u = j;
}
}
// 如果所有顶点都已访问或剩余顶点都不可达，跳出循环
if (u == -1) break;
visited[u] = true;
// 遍历当前顶点的所有邻接边，更新距离
vector<Edge> edges = graph.getAdjList()[u];
for (auto& edge : edges) {
int v = edge.to;
int weight = edge.weight;
if (!visited[v] && dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
}
}
}
return dist;
}
优先队列优化版实现
使用最小堆（优先队列）优化查找最小距离顶点的过程，时间复杂度可降至O((n+m)logn)，其中m为边数量，适合顶点和边较多的场景：
#include <queue>
// 定义优先队列的元素结构，存储距离和顶点编号
struct Node {
int dist; // 当前距离
int vertex; // 顶点编号
Node(int d, int v) : dist(d), vertex(v) {}
// 重载小于运算符，让优先队列按照距离从小到大排序
bool operator<(const Node& other) const {
return dist > other.dist; // 注意这里是大于号，因为优先队列默认是大顶堆
}
};
// 优先队列优化版迪杰斯特拉算法
vector<int> dijkstraOptimized(WeightedGraph& graph, int start) {
int n = graph.getVertexCount();
vector<int> dist(n, INT_MAX); // 距离数组
dist[start] = 0;
priority_queue<Node> pq; // 最小距离优先队列
pq.push(Node(0, start));
while (!pq.empty()) {
Node cur = pq.top();
pq.pop();
int u = cur.vertex;
int curDist = cur.dist;
// 如果当前距离大于记录的距离，说明已经被更新过，跳过
if (curDist > dist[u]) continue;
// 遍历邻接边更新距离
vector<Edge> edges = graph.getAdjList()[u];
for (auto& edge : edges) {
int v = edge.to;
int weight = edge.weight;
if (dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
pq.push(Node(dist[v], v));
}
}
}
return dist;
}
测试代码与结果验证
下面编写测试代码，构建一个带权重的无向图，验证两种实现的正确性：
int main() {
// 构建包含5个顶点的图
WeightedGraph graph(5);
// 添加带权重的边
graph.addEdge(0, 1, 2);
graph.addEdge(0, 2, 4);
graph.addEdge(1, 2, 1);
graph.addEdge(1, 3, 7);
graph.addEdge(2, 4, 3);
graph.addEdge(3, 4, 2);
int start = 0;
// 测试基础版算法
vector<int> basicDist = dijkstraBasic(graph, start);
cout << "基础版迪杰斯特拉结果（起点" << start << "）：" << endl;
for (int i = 0; i < basicDist.size(); i++) {
cout << "到顶点" << i << "的最短距离：" << basicDist[i] << endl;
}
cout << endl;
// 测试优化版算法
vector<int> optimizedDist = dijkstraOptimized(graph, start);
cout << "优化版迪杰斯特拉结果（起点" << start << "）：" << endl;
for (int i = 0; i < optimizedDist.size(); i++) {
cout << "到顶点" << i << "的最短距离：" << optimizedDist[i] << endl;
}
return 0;
}
上述测试代码的输出结果中，起点0到各个顶点的最短距离分别为0、2、3、8、6，两种实现的结果一致，验证了算法的正确性。