dijkstra算法求最短路径中的朴素算法

Question

dijkstra算法求最短路径中的朴素算法

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 510;

int n, m;
int g[N][N];
int dist[N];
bool st[N];

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for (int i = 0; i < n - 1; i ++ )
    {
        int t = -1;
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], dist[t] + g[t][j]);

        st[t] = true;
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main()
{
    scanf("%d%d", &n, &m);

    memset(g, 0x3f, sizeof g);
    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);

        g[a][b] = min(g[a][b], c);
    }

    printf("%d\n", dijkstra());

    return 0;
}

中

  for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

这一步不理解，为什么求不在集合中的距离最近的点可以这样写

Answer 1

以下内容由CHATGPT及阿里嘎多学长共同生成、有用望采纳：

---

问题概括

这个问题是关于Dijkstra算法在寻找最短路径时的一个具体实现细节。Dijkstra算法是一种用于在加权图中找到单个源点到所有其他顶点的最短路径的算法。问题中的代码段是算法中用于选择下一个最近顶点的部分，提问者对这部分的逻辑表示不理解。

问题出现原因

问题出现的原因可能是因为对Dijkstra算法的工作原理或者对特定代码实现的逻辑不够熟悉。在Dijkstra算法中，我们需要维护一个集合来记录已经找到最短路径的顶点，以及一个距离数组来记录从源点到每个顶点的当前已知最短距离。

问题解决方案

在Dijkstra算法中，每次迭代都需要从尚未确定最短路径的顶点中选择一个距离源点最近的顶点。代码中的内层循环：

for (int j = 1; j <= n; j++)
    if (!st[j] && (t == -1 || dist[t] > dist[j]))
        t = j;

这段代码的目的是找到未被标记（即!st[j]表示顶点j不在已确定最短路径的集合中）且距离源点最近的顶点。这里，t是用来记录当前找到的最近顶点的索引。如果t已经是-1（表示还没有找到任何最近顶点），或者找到了一个更近的顶点（即dist[t] > dist[j]），则更新t为这个新找到的最近顶点。

提供示例

以下是对原始代码中不理解部分的注释说明，以帮助理解其逻辑：

// 初始化所有距离为无穷大，除了源点到自身的距离设为0
memset(dist, 0x3f, sizeof dist);
dist[1] = 0; // 假设源点的索引为1

for (int i = 0; i < n - 1; i++) {
    int t = -1; // 初始化t为-1，表示尚未找到最近顶点
    // 寻找未被标记的最近顶点
    for (int j = 1; j <= n; j++) {
        if (!st[j] && (t == -1 || dist[t] > dist[j])) { // 如果j未被标记，并且t未定义或j比t更接近源点
            t = j; // 更新t为j
        }
    }
    // 更新所有未标记顶点的距离，如果通过t顶点可以找到更短的路径
    for (int j = 1; j <= n; j++) {
        dist[j] = min(dist[j], dist[t] + g[t][j]);
    }
    // 标记t顶点为已处理
    st[t] = true;
}

// 如果终点n到源点的距离仍然是无穷大，则说明没有路径；否则返回最短路径长度
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];

示例代码运行方式

这段代码是C++语言编写的，需要一个支持C++的编译器，如GCC或Clang。编译命令可能是：

g++ -o dijkstra dijkstra.cpp

然后运行编译后的程序：

./dijkstra

示例代码预期运行结果

代码将读取输入的图的顶点数和边数，然后是边的具体信息，包括两个顶点和它们之间的权重。之后，它将输出从源点到终点的最短路径长度。如果没有路径，则输出-1。

输入格式:
顶点数 边数
顶点1 顶点2 权重
...
输出格式:
最短路径长度 或 -1

请注意，这里的示例代码并没有包含完整的主函数和输入处理，需要将其嵌入到完整的程序中才能得到预期的运行结果。