如何修改Dijkstra最短路径代码以正常显示无路径提示

问题根源 #

1. 判断逻辑完全错误：原代码末尾if (next!=dest)的判断完全颠倒——当有路径时，next最终会等于node（不等于dest），这会导致有路径时反而触发无路径提示；而无路径时，previous[dest]未被初始化，while(next != node)会进入死循环或打印乱码，根本走不到判断语句。
2. 未利用可靠的路径存在标志：Dijkstra算法中，如果两点间无路径，目标节点的distance值会保持初始的INT_MAX，这是判断无路径的可靠依据。

修改步骤 #

1. 在打印路径前，先检查distance[dest]是否等于INT_MAX：
   • 如果等于，直接输出无路径提示，函数返回。
   • 如果不等于，再执行路径打印逻辑。
2. 移除原代码末尾错误的无路径判断代码。

修改后的完整代码 #

void dijkstra2(GRAPH graph, int node,int dest)
{
    int previous[MAX];
    double distance[MAX]; 
    bool Check[MAX]; 
    for (int i = 0; i < graph.n; i++) 
    {
        distance[i] = INT_MAX;
        Check[i] = false;
    }

    distance[node] = 0; 
    previous[node] = node;
    for (int z = 0; z < graph.n - 1; z++)
    {
        int md = minimumDistance(graph, distance, Check);
        Check[md] = true;
        
        for (int o = 0; o < graph.n; o++)
        {
            if (!Check[o] && graph.ms[md][o] && distance[md] != INT_MAX && distance[md] + graph.ms[md][o] < distance[o])
            {
                distance[o] = distance[md] + graph.ms[md][o];
                previous[o] = md;
                if (o == dest) break;
            }
        }
    }

    if (node == dest) {
        cout << "起点和终点相同，无需查找路径。" << endl;
        return;
    }

    // 核心判断：检查是否存在路径
    if (distance[dest] == INT_MAX) {
        cout << "起点和终点之间不存在路径。" << endl;
        return;
    }

    // 打印路径
    int next = dest;
    while (next != node) 
    {
        cout << next+1 << " <- ";
        next = previous[next]; 
    }
    cout << node + 1 << endl;
}

额外说明 #

• 原代码中distance是double类型，但初始化用了INT_MAX（整数最大值），虽然能工作，但更规范的做法是用DBL_MAX（需引入头文件<cfloat>）来匹配浮点类型。
• 确保minimumDistance函数能正确处理distance为INT_MAX的情况，返回未被访问的节点中距离最小的那个。

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