[C++知识库]查找最短路的路径，存在多条最短路长度相同的情况（c++实现）

最短路问题需要记录路径，需要找出多条长度一样的最短路径

思路

另外开一个数组记录从哪个点走过来的
类似邻接链表的形式记录被更新的点，最后用dfs搜索

代码

int dijkstra() //求最短路
{
    memset(d, 0x3f, sizeof d);
    d[0] = 0;
    
    for (int i = 0; i < n + 1; i ++ )
    {
        int t = -1;
        for (int j = 0; j <= n; j ++ )
            if ((t == -1 || d[j] < d[t]) && !st[j]) t = j;
        
        st[t] = true;
        
        for (int j = 1; j <= n; j ++ )
        {
            if (d[j] > d[t] + g[t][j])
            {
                d[j] = d[t] + g[t][j];
                la[j].clear(); //la数组用来记录上一个点（被更新时记录）
                la[j].push_back(t);
            }
            else if (d[j] == d[t] + g[t][j])
            {
                la[j].push_back(t); //此时可能有多条路径
            }
        }
    }
    
    return d[prob];
}

void dfs(int u) //从终点搜索到起点
{
    path.push_back(u); //记录路径
    if (u == 0)
    {
        check(); //表示搜到一种path
        return;
    }
    
    for (int i = 0; i < la[u].size(); i ++ )
    {
        int j = la[u][i];
        dfs(j);
        path.pop_back();
    }
}