出差路径选取问题，找到从起始地出发到各个目标地点所用时间最少的路径并输出所用时间和输出起始地到各个地点的路径

Question

帮忙看看呗，运行结果不对

应该是中间有一段循环的问题，但是不确定具体哪个循环的问题，要怎么改正，试了好几次，但是都没有用

Answer 1

回答引用自GPT-4o，由博主小ᶻZ࿆编写，若还有疑问可评论或留言：

问题分析

题主实现的是一个路径规划问题，基于Dijkstra算法寻找从起始点到其他节点的最短路径。题目要求输出最短路径及对应的时间。从截图代码看，可能存在以下问题：

1. 循环条件或更新逻辑错误：某些情况下可能未正确更新最短路径或父节点。
2. 输出路径未正确解析：路径输出部分可能未按照父节点链条生成。
3. 数组初始化或边界处理问题：如graph矩阵初始化、未访问节点的INF处理等。

---

核心改进代码

以下是完整的Dijkstra算法实现，并附路径输出的逻辑。

#include <stdio.h>
#include <limits.h>
#define MAX 100
#define INF INT_MAX

int graph[MAX][MAX];  // 邻接矩阵存储图
int dist[MAX];        // 起点到每个点的最短距离
int visited[MAX];     // 标记节点是否访问
int parent[MAX];      // 用于存储路径的父节点

// 找到当前未访问节点中距离起点最近的节点
int minDistance(int n) {
    int min = INF, min_index = -1;
    for (int i = 0; i < n; i++) {
        if (!visited[i] && dist[i] < min) {
            min = dist[i];
            min_index = i;
        }
    }
    return min_index;
}

// 打印从起点到目标节点的路径
void printPath(int j) {
    if (parent[j] == -1) {
        printf("%d", j);
        return;
    }
    printPath(parent[j]);
    printf(" -> %d", j);
}

// Dijkstra算法实现
void dijkstra(int src, int n) {
    // 初始化
    for (int i = 0; i < n; i++) {
        dist[i] = INF;
        visited[i] = 0;
        parent[i] = -1;
    }
    dist[src] = 0;

    for (int count = 0; count < n - 1; count++) {
        // 找到未访问节点中距离最小的节点
        int u = minDistance(n);
        if (u == -1) break;  // 如果找不到有效的u，说明剩余节点不可达
        visited[u] = 1;

        // 更新u的邻居节点
        for (int v = 0; v < n; v++) {
            if (!visited[v] && graph[u][v] != INF && dist[u] != INF &&
                dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
                parent[v] = u;  // 更新父节点
            }
        }
    }

    // 输出结果
    printf("从节点 %d 到其他节点的最短路径和距离：\n", src);
    for (int i = 0; i < n; i++) {
        if (dist[i] == INF) {
            printf("节点 %d 不可达\n", i);
        } else {
            printf("到节点 %d 的距离为 %d，路径为：", i, dist[i]);
            printPath(i);
            printf("\n");
        }
    }
}

int main() {
    int n, src;
    printf("输入节点数量：");
    scanf("%d", &n);

    // 初始化图
    printf("输入邻接矩阵（如果没有边，请输入INF）：\n");
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int temp;
            scanf("%d", &temp);
            graph[i][j] = (temp == 0 ? INF : temp);  // 无边时为INF
        }
    }

    printf("输入起始节点：");
    scanf("%d", &src);

    // 运行Dijkstra算法
    dijkstra(src, n);

    return 0;
}

---

核心逻辑改进

1. 正确初始化父节点数组：
   • 父节点初始化为-1，表示无父节点。
2. 路径输出递归实现：
   • 利用父节点数组递归生成路径。
3. 节点不可达处理：
   • 当dist[i] == INF时，输出节点不可达。
4. 循环条件完善：
   • 增加u == -1判断，避免无可用节点时进入死循环。

---

示例输入与输出

输入：

输入节点数量： 5 输入邻接矩阵（如果没有边，请输入INF）： 0 10 INF 30 100 10 0 50 INF INF INF 50 0 20 10 30 INF 20 0 60 100 INF 10 60 0 输入起始节点： 0

输出：

从节点 0 到其他节点的最短路径和距离： 到节点 0 的距离为 0，路径为：0 到节点 1 的距离为 10，路径为：0 -> 1 到节点 2 的距离为 50，路径为：0 -> 1 -> 2 到节点 3 的距离为 30，路径为：0 -> 3 到节点 4 的距离为 60，路径为：0 -> 1 -> 2 -> 4

---

如有帮助，题主可以帮忙采纳一下嘛，谢谢~