C/C++迪杰斯特拉（Dijkstra）最短路径算法实现详解
本文详解在C/C++中如何利用迪杰斯特拉（Dijkstra）算法求解单源最短路径问题。文章从算法的基本思想出发，分别给出了基于邻接表和邻接矩阵的完整代码实现，并解释了 dist、path 和 final 数组的作用，最后辅以测试案例验证算法的正确性。
Dijkstra算法核心原理
对于带权有向图或无向图，最短路径是指两个顶点之间经过的边上权值之和最小的路径。迪杰斯特拉算法正是用于寻找从一个源点出发到图中其余各顶点的最短路径。
其核心思想是贪心策略：按照路径长度递增的次序逐步产生最短路径。即在每一步中，从未求出最短路径的顶点集合中，选择一个距离源点最近的顶点，将其纳入已求解集合，并以此为中转点，更新其与周边未访问顶点之间的距离。
关键数据结构定义
在实现过程中，主要维护三个辅助数组，以记录状态：
dist[]：数组的第i个分量表示当前找到的从源点到终点i的最短路径长度。初始化为源点到该顶点的边权，若无直接相连则设为无穷大（如65535或INT_MAX）。path[]：记录最短路径的前驱节点信息，用于最终回溯打印具体路径。final[]：标记是否求得从源点到该顶点的最短路径。值为1表示已确定，为0表示尚未确定。
步骤一：初始化阶段
算法开始前，需要对上述三个数组进行初始化设置。假设图结构为邻接表，源点索引为 vi：
- 将所有
final[i]置为0，表示所有顶点均未求得最短路径； - 将所有
path[i]置为0； - 将所有
dist[i]初始化为无穷大，但针对与源点vi直接相连的邻接节点，将dist更新为其对应的边权值。
int* final = (int*)malloc(sizeof(int) * g.vexnum);
for (int i = 0; i < g.vexnum; i++) {
path[i] = 0;
final[i] = 0;
dist[i] = INFNITY; // INFNITY 需预定义为足够大的整数，如 65535
}
// 初始化与源点直接相连的边的权重
ArcNode* p = g.vertexlist[vi].firstarc;
for (p; p != NULL; p = p->nextarc) {
dist[p->adjvex] = p->weight;
}随后，将源点本身的状态特殊处理：源点到自身的距离 dist[vi] 设为 0，同时将其 final[vi] 标记为 1，代表第一个到达源点自身的最短路径已确认。
dist[vi] = 0; final[vi] = 1;
步骤二：主循环与路径更新
接下来进入主要的循环逻辑，我们需要对剩余的 vexnum-1 个节点进行扫描。
第1步：选择最近未访问节点
在当前未确定的节点集合（即 final[w]==0）中，查找具有最小 dist 值的节点 k。这个节点 k 就是下一轮将要“固化”的最短路径目标点。
int k;
for (int v = 1; v < g.vexnum; v++) {
int min = INFNITY;
for (int w = 0; w < g.vexnum; w++) {
// 找到未访问且距离最小的节点下标k
if (!final[w] && dist[w] < min) {
k = w;
min = dist[w];
}
}第2步：固定该节点并更新邻居
一旦确定了节点 k，首先将其 final[k] 置为 1。然后检查以 k 为起点的出边：k 的所有邻接点 p->adjvex。如果通过 k 到达某个邻接点的路径（min + weight）比原来记录的 dist 更短，则更新该邻接点的 dist 值，并将它的 path 指向 k。
final[k] = 1;
ArcNode* p = g.vertexlist[k].firstarc;
while (p != NULL) {
// 若存在更短路径，则更新dist和path
if (!final[p->adjvex] && (p->weight + min) < dist[p->adjvex]) {
dist[p->adjvex] = min + p->weight;
path[p->adjvex] = k;
}
p = p->nextarc;
}
}完整代码实现
基于邻接表的完整函数
将上述步骤整合，适用于邻接表存储结构的完整代码如下：
void ShortestPath(AdjList g, int vi, int* path, int* dist) {
int* final = (int*)malloc(sizeof(int) * g.vexnum);
for (int i = 0; i < g.vexnum; i++) {
path[i] = 0;
final[i] = 0;
dist[i] = INFNITY;
}
ArcNode* p = g.vertexlist[vi].firstarc;
for (p; p != NULL; p = p->nextarc) {
dist[p->adjvex] = p->weight;
}
dist[vi] = 0;
final[vi] = 1;
int k;
for (int v = 1; v < g.vexnum; v++) {
int min = INFNITY;
for (int w = 0; w < g.vexnum; w++) {
if (!final[w] && dist[w] < min) {
k = w;
min = dist[w];
}
}
final[k] = 1;
ArcNode* p = g.vertexlist[k].firstarc;
while (p != NULL) {
if (!final[p->adjvex] && (p->weight + min) < dist[p->adjvex]) {
dist[p->adjvex] = min + p->weight;
path[p->adjvex] = k;
}
p = p->nextarc;
}
}
free(final);
return;
}基于邻接矩阵的修改差异
如果使用邻接矩阵存储图，初始化逻辑略有不同。由于可以直接通过二维数组访问边权，初始化时不再需要指针遍历链表，而是直接将矩阵中的值赋给 dist：
void ShortestPath(AdjMatrix g, int vi, int* path, int* dist) {
int* final = (int*)malloc(sizeof(int) * g.vexnum);
for (int i = 0; i < g.vexnum; i++) {
path[i] = 0;
final[i] = 0;
dist[i] = g.arc[vi][i]; // 直接从矩阵获取源点到i的距离
}
dist[vi] = 0;
final[vi] = 1;
int k;
for (int v = 1; v < g.vexnum; v++) {
int min = INFNITY;
for (int w = 0; w < g.vexnum; w++) {
if (!final[w] && dist[w] < min) {
k = w;
min = dist[w];
}
}
final[k] = 1;
// 邻接矩阵版本遍历更新所有可能相连的w节点
for (int w = 0; w < g.vexnum; w++) {
if (!final[w] && (min+g.arc[k][w])<dist[w]) {
dist[w]=min+g.arc[k][w];
path[w]=k;
}
}
}
free(final);
return;
}测试结果验证
为了验证代码逻辑，构建一个简单的测试图。在该例子中，因为我们的边表建立顺序将A设定为索引0的第一个节点，故默认A为源点进行计算。
程序运行后，终端输出的最短路径及距离信息如下：
从输出结果可以看到，算法正确计算出了各节点相对于源点的最短距离，证明实现逻辑无误。
总结
迪杰斯特拉算法的时间复杂度为 O(n²)，其中 n 是图中的顶点数量。如果需要求任意两点间的最短路径，可对每个顶点作为源点调用一次该算法，总时间复杂度达到 O(n³)，这与弗洛伊德（Floyd）算法同级。不过相比于Floyd算法优雅的三重嵌套结构，Dijkstra算法更适合解决单源最短路径问题，且在配合优先队列优化后可大幅降低特定场景的计算开销。
以上就是C/C++迪杰斯特拉（Dijkstra）最短路径算法实现的详细内容，更多关于C/C++迪杰斯特拉算法的资料请关注本站其它相关文章！本站声明
本文内容仅供参考，不代表本站观点。转载或引用请注明出处。如发现内容问题，请通过联系我们页面反馈。
