原题链接

第一部分：介绍朴素版的dijkstra。
第二部分：介绍更改的Dijkstra：求起点到终点的path数组。

一、朴素版dijkstra

Dijkstra 算法步骤：

1.初始化： 初始化邻接矩阵 g 为无穷大，表示初始时没有边相连；将距离数组 dist 初始化为无穷大，表示初始时源点到所有点的距离都未知；将点的加入状态数组 st 初始化为 false，表示初始时所有点均未加入最短路径树。

memset(g, 0x3f, sizeof g);  // 初始化邻接矩阵为无穷大
memset(dist, 0x3f, sizeof dist);  // 初始化距离数组为无穷大

2.读入图的边信息： 通过输入，读入图的点数 n、边数 m 以及每条边的起点、终点、权值信息，更新邻接矩阵 g。

cin >> n >> m;
for (int i = 0; i < m; i ++)
{
    int a, b, c;
    cin >> a >> b >> c;
    g[a][b] = min(g[a][b], c);  // 更新边权信息，取最小值
}

3.Dijkstra 算法主体： 执行 Dijkstra 算法的核心部分，不断选择当前最短距离的点，并更新通过该点到其他点的距离。

dijkstra();  // 调用Dijkstra算法

void dijkstra()
{
    dist[1] = 0;  // 源点到自身距离为0

    for (int i = 0; i < n; i ++)
    {
        int t = -1;
        // 选择当前最短距离的点
        for (int j = 1; j <= n; j ++)
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        st[t] = true;  // 将该点加入最短路径树

        // 更新通过t点的距离
        for (int j = 1; j <= n; j ++)
            dist[j] = min(dist[j], dist[t] + g[t][j]);
    }
}

4.输出结果： 根据最短距离数组 dist 的值，输出源点到目标点的最短距离。

if (dist[n] == INF) puts("-1");
else cout << dist[n] << endl;

这样，代码就完成了 Dijkstra 算法，求解了源点到目标点的最短距离。

#include <iostream>
#include <cstring>

using namespace std;

const int N = 510, M = 100010, INF = 0x3f3f3f3f;

int g[N][N];   // 邻接矩阵存储图的边权信息
int n, m;       // n为点数，m为边数
bool st[N];     // 记录每个点是否已经加入最短路径树
int dist[N];    // 记录源点到各个点的最短距离

void dijkstra()
{
    memset(dist, 0x3f, sizeof dist);  // 初始化距离数组为无穷大

    dist[1] = 0;  // 源点到自身距离为0

    for (int i = 0; i < n; i ++)
    {
        int t = -1;
        // 选择当前最短距离的点
        for (int j = 1; j <= n; j ++)
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        st[t] = true;  // 将该点加入最短路径树

        // 更新通过t点的距离
        for (int j = 1; j <= n; j ++)
            dist[j] = min(dist[j], dist[t] + g[t][j]);
    }
}

int main()
{
    memset(g, 0x3f, sizeof g);  // 初始化邻接矩阵为无穷大

    cin >> n >> m;
    for (int i = 0; i < m; i ++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = min(g[a][b], c);  // 更新边权信息，取最小值
    }

    dijkstra();  // 调用Dijkstra算法

    if (dist[n] == INF) puts("-1");
    else cout << dist[n] << endl;

    return 0;
}

二、更改dijkstra求起点到终点的path数组

修改内容：
新增了pre数组用于记录路径上每个点的前驱节点。在Dijkstra算法中，每次更新最短距离时，同时更新对应点的前驱节点。最后根据前驱节点数组获取路径，并将路径输出。

以下是修改后的 Dijkstra 算法的关键修改点：

1.增加前驱节点数组 pre： 在全局范围内增加了 pre 数组，用于记录路径上每个点的前驱节点。

int pre[N];     // 记录路径上每个点的前驱节点

2.增加路径记录数组 path： 在全局范围内增加了 path 向量，用于记录从起点到终点的路径。

vector<int> path;  // 记录路径

3.在 dijkstra 函数中记录路径： 修改了 dijkstra 函数，在求解最短路径的同时记录了路径上的节点。

void dijkstra(int start, int end)
{
    // ... （省略部分代码）

    // 根据前驱节点数组获取路径
    for (int i = end; i != start; i = pre[i])
        path.push_back(i);
    path.push_back(start);

    // 将路径逆序输出
    for (int i = path.size() - 1; i >= 0; i--)
        cout << path[i] << ' ';
    cout << endl;
}

4.在 main 函数中输入起点和终点： 修改了 main 函数，增加了输入起点和终点的过程。

int start, end;
cin >> start >> end;

dijkstra(start, end);  // 调用Dijkstra算法求解路径

这样，通过记录前驱节点数组 pre 和路径数组 path，就可以在求解最短路径的同时得到起点到终点的具体路径。

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

const int N = 510, M = 100010, INF = 0x3f3f3f3f;

int g[N][N];   // 邻接矩阵存储图的边权信息
int n, m;       // n为点数，m为边数
bool st[N];     // 记录每个点是否已经加入最短路径树
int dist[N];    // 记录源点到各个点的最短距离
int pre[N];     // 记录路径上每个点的前驱节点

vector<int> path;  // 记录路径

void dijkstra(int start, int end)
{
    memset(dist, 0x3f, sizeof dist);  // 初始化距离数组为无穷大

    dist[start] = 0;  // 源点到自身距离为0

    for (int i = 0; i < n; i ++)
    {
        int t = -1;
        // 选择当前最短距离的点
        for (int j = 1; j <= n; j ++)
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        st[t] = true;  // 将该点加入最短路径树

        // 更新通过t点的距离
        for (int j = 1; j <= n; j ++)
            if (dist[j] > dist[t] + g[t][j])
            {
                dist[j] = dist[t] + g[t][j];
                pre[j] = t;  // 记录路径上的前驱节点
            }
    }

    // 输出起点到终点的最短距离
    printf("dist[%d] = %d\n", end, dist[end]);

    // 根据前驱节点数组获取路径
    for (int i = end; i != start; i = pre[i])
        path.push_back(i);
    path.push_back(start);

    // 将路径逆序输出
    for (int i = path.size() - 1; i >= 0; i--)
        cout << path[i] << ' ';
    cout << endl;
}

int main()
{
    memset(g, 0x3f, sizeof g);  // 初始化邻接矩阵为无穷大

    cin >> n >> m;
    for (int i = 0; i < m; i ++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = min(g[a][b], c);  // 更新边权信息，取最小值
    }

    int start, end;
    cin >> start >> end;

    dijkstra(start, end);  // 调用Dijkstra算法求解路径

    return 0;
}

输入：

6 9
1 2 1
1 3 4
2 3 2
2 4 5
3 4 1
3 5 3
4 6 4
5 4 2
5 6 5
1 6

最下面1行的1 6表示起点和终点

输出：

dist[6] = 8
1 2 3 4 6 

【思考】
这里求出了带权有向图的最短距离以及路径，如果题目改一下，要你求带权DAG的最长距离，应该如何解？
https://www.acwing.com/blog/content/66048/