Dijkstra算法路径打印异常求助：部分起始点输出缺失或不全

你的算法距离计算正常，但路径打印异常，核心是两个不起眼的小bug，咱们拆解来看：

1. 问题根源 #

Bug 1：Parent数组初始化只给了第一个节点赋值 #

在dijkstra函数的初始化循环里，你只设置了parent[0] = -1，其他节点的parent值都是内存里的随机垃圾值：

for(int i=0;i<V;i++) 
{
    parent[0] = -1; // 只初始化了索引0的元素，其他全是随机值！
    dist[i]=INT_MAX;
    Dset[i]=false;
}

这就导致：

• 当起始点不是1（对应src=0）时，比如起始点5（src=4），parent[4]根本不是-1，递归printPath时找不到终止条件，自然没输出。
• 部分节点的parent是乱码，递归时可能走偏甚至死循环。

Bug 2：PrintPath函数忘了打印起始节点 #

在printPath里，当遇到源节点时直接return，没把它打出来：

if (parent[j] == -1)
{
    return;
}

比如起始点3到终点5，路径应该是3 4 5，但因为没打印起始的3，就只输出了4 5。

2. 修复后的完整代码 #

#include<iostream>
#include<fstream>
#include<climits> /*Used for INT_MAX*/
using namespace std;
#define V 6 /*It is the total no of verteices in the graph*/

int minimumDist(int dist[], bool Dset[]) /*A method to find the vertex with minimum distance which is not yet included in Dset*/
{
    int min=INT_MAX,index; /*initialize min with the maximum possible value as infinity does not exist */
    for(int v=0;v<V;v++)
    {
        if(Dset[v]==false && dist[v]<=min)
        {
            min=dist[v];
            index=v;
        }
    }
    return index;
}

void printPath(int parent[], int j, int src)
{
    // 基例：如果当前节点是源节点，直接打印它
    if (j == src)
    {
        printf("%d ", j+1);
        return;
    }
    // 先递归打印父节点路径
    printPath(parent, parent[j], src);
    // 再打印当前节点
    printf("%d ", j+1);
}

void dijkstra(int graph[V][V],int src,int n) /*Method to implement shortest path algorithm*/
{
    int dist[V];
    bool Dset[V];
    int parent[V];
    
    for(int i=0;i<V;i++) /*Initialize distance of all the vertex to INFINITY and Dset as false*/
    {
        parent[i] = -1; // 给所有节点的parent都初始化为-1，不管起始点是谁
        dist[i]=INT_MAX;
        Dset[i]=false;
    }
    
    dist[src]=0; /*Initialize the distance of the source vertec to zero*/
    
    for(int c=0;c<V;c++)
    {
        int u=minimumDist(dist,Dset); /*u is any vertex that is not yet included in Dset and has minimum distance*/
        Dset[u]=true; /*If the vertex with minimum distance found include it to Dset*/
        
        for(int v=0;v<V;v++) /*Update dist[v] if not in Dset and their is a path from src to v through u that has distance minimum than current value of dist[v]*/
        {
            if(!Dset[v] && graph[u][v] && dist[u]!=INT_MAX && dist[u]+graph[u][v]<dist[v])
            {
                parent[v] = u; 
                dist[v]=dist[u]+graph[u][v];
            }
        }
    }
    
    /*will print the vertex with their distance from the source to the console */
    if(dist[n-1] != INT_MAX) // 用INT_MAX判断更准确，别用魔法数字999啦
    {
        cout<<"atstumas nuo "<<src+1<<" iki "<<n<<" yra = "<<dist[n-1]<<endl; 
        printPath(parent, n-1, src);
        cout<<endl; // 加个换行让输出好看点
    }
    else
    {
        cout<<"kelio i pabaigos taska nera"<<endl;
    }
}

int main()
{
    int start,ending;
    cout<<"iveskite pradzia"<<endl;
    cin>>start;
    cout<<"iveskite pabaiga"<<endl;
    cin>>ending;
    
    int graph[V][V]={
        { 0,70,50,0,100,0 },
        { 0,0,0,35,0,20 },
        { 0,60,0,15,0,0 },
        { 0,0,0,0,30,45 },
        { 0,0,20,0,0,0 },
        { 0,0,0,0,4,0}};
        
    dijkstra(graph,start-1,ending);
    return 0;
}

3. 关键修复点说明 #

• Parent数组全局初始化：把parent[0] = -1改成parent[i] = -1，确保所有节点的parent初始值都是-1，不管起始点是哪个，递归都能正确终止。
• PrintPath函数修正：
  • 新增src参数，直接判断当前节点是否是源节点，是的话直接打印，解决起始节点缺失问题。
  • 递归顺序调整为先打父节点路径，再打当前节点，保证路径顺序正确。
• 距离判断优化：把dist[n-1]<999换成dist[n-1] != INT_MAX，用初始化的无穷大值判断更靠谱，避免图中边权接近999时误判。

测试效果 #

修复后再测你提到的场景：

• 起始点2→终点3：输出2 6 5 3（正常）
• 起始点5→终点3：输出5 3（正常）
• 起始点3→终点5：输出3 4 5（正常）

内容的提问来源于stack exchange，提问作者Pagurklis