代码

本文使用vetor模拟邻接表，可以直接用二维数组

void print_path(int path[], int a)
{
    // path实际是一个双亲存储结构的树
    // 只能从叶子节点找到根节点
    // 因此需要一个栈，将序列倒着输出，即为从根节点到叶子节点
    stack<int> s;
    
    while (path[a] != -1) // 一直向上直到查找到根节点
    {
        s.push(a);  // 思考一下如果这两句交换位置会怎么样？
        a = path[a];
    }

    while (!s.empty())
    {
        cout << s.top() << " ";
    }

    cout << endl;
}

struct node {
    int to, cost;
};
vector <node> G[MAXN];
int vis[MAXN]; // 标记节点是否已经加入到最短路中
int dis[MAXN]; // 当前源点到i的最短距离
int path[MAXN];  // path[i] = j，代表从源点到i的上一步是j

void dijkstra(int v, int n)
{
    // 初始化三个数组
    for (int i=0; i<n; i++)
    {
        dis[i] = INF;
        vis[i] = 0;
        path[i] = -1;
    }

    // 把与源点直连的节点的距离在dis数组中更新
    // 并且路径数组中进行更新
    for (int i=0; i<G[v].size(); i++)
    {
        dis[G[v][i].to] = G[v][i].cost;
        path[G[v][i].to] = v;
    }

    vis[v] = 1;  // 代表已经访问过v

    // 将剩下的n-1个节点依次加入到最短路中
    for (int i=0; i<n-1; i++)
    {
        int index = 0, min = INF;

        // 查找当前dis中最短的路径，记下节点编号
        for (int j=0; j<n; j++)
        {
            if (!vis[j] && dis[j] < min)
            {
                index = j;
                min = dis[j];
            }
        }

        vis[index] = 1; // 将找到的节点加入到最短路中

        // 通过新加入的节点进行更新dis数组
        for (int j=0; j<G[index].size(); j++)
        {
            // 如果当前从源点到j的距离大于源点到index+index到j的距离，更新dis数组
            if (!vis[G[index][j].to] && dis[j] < dis[index] + G[index][j].cost)
            {
                dis[j] = dis[index] + G[index][j].cost;
                path[j] = index;  // 前驱为index
            }
        }
    }
}