prim算法求最小生成树邻接矩阵法

Question

初始化距离矩阵把dist i j设为了无穷大，在后面prim函数里调用他的时候怎么知道两点间距离？

Answer 1

【以下回答由 GPT 生成】

首先，从代码中可以看出，dist是一个二维数组，用于表示两个城市之间的距离。通常情况下，我们可以利用dist[i][j]获取城市i和城市j之间的距离。

但是，在初始化距离矩阵时，你将dist[i][j]的值设为了无穷大，这样的话在后续的代码中可能会出现问题。因为无穷大无法用一个具体的数值表示距离，所以无法在后续的代码中使用dist[i][j]获取实际的距离值。

为了解决这个问题，你可以在初始化距离矩阵时，将dist[i][j]的值设为一个较大的数值，例如1000000。这样，在后续的代码中你可以使用dist[i][j]获取距离，并且判断距离是否为无穷大。

下面是修改后的代码示例：

int minCost = INF; // 最小生成树中当前最小的公路费用
for (int i = 0; i < n; i++) {
    if (visited[i]) {
        for (int j = 0; j < n; j++) {
            if (visited[j] && dist[i][j] < minCost) {
                minCost = dist[i][j];
                u = i;
                v = j;
            }
        }
    }
    visited[v] = true; // 将v城市加入最小生成树
    // 其他操作
}

请注意，你需要确保在后续代码中对dist[i][j]的使用是合理的，以避免出现其他错误。如果还有其他问题，请提供更多信息，我会尽力帮助你解决。

【相关推荐】

• 这篇博客: 【图解算法】最小生成树中的 2.3 prim 算法的优化 部分也许能够解决你的问题。

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^