多条最短路径的dijstra

图里面可能有多条最短路径，并且我们可能会想要获得多条最短路径

通过给每一个节点维护一个前面节点数组，当新的距离等于这个节点当前的距离时，不是抛弃这条路径，而是将这条路径保存到数组中，当新的距离小于这个节点当前的距离时，清空数组，将当前路径存入

最后通过回溯来获得所有的路径(广度优先搜索也行)

代码

```

#include <iostream>
#include <vector>

using namespace std;
void backtracking(vector<vector<int>>& c,vector<vector<int>>& path_arr,vector<int> path,int i)
{

    path.emplace_back(i);
    if(i==0)
    {
        path_arr.emplace_back(path);
        return;
    }
    for(int j=0;j<c[i].size();j++)
    {
        backtracking(c,path_arr,path,c[i][j]);
    }
}
int main()
{
    int n,m;
    cin>>n>>m;
    vector<vector<int>> g(n);
    for(int i=0;i<n;i++)
    {
        g[i].resize(n);
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            g[i][j]=INT32_MAX;
        }
    }
    for(int i=0;i<m;i++)
    {
        int from,to,weight;
        cin>>from>>to>>weight;
        g[from][to]=weight;
    }
    vector<int> a(n);
    vector<int> b(n,INT32_MAX);
    b[0]=0;
    vector<vector<int>> c(n);
    while(true)
    {
        int flag=1;
        for(int i=0;i<a.size();i++)
        {
            if(a[i]!=1)
            {
                flag=0;
                break;
            }
        }
        if(flag==1)
        {
            break;
        }
        int min_dist=INT32_MAX;
        int min_idx=-1;
        for(int i=0;i<a.size();i++)
        {
            if(a[i]==0)
            {
                if(min_dist>b[i])
                {
                    min_dist=b[i];
                    min_idx=i;
                }
            }
        }
        a[min_idx]=1;
        for(int i=0;i<n;i++)
        {
            if(g[min_idx][i]!=INT32_MAX&&a[i]!=1)
            {
                int dist=min_dist+g[min_dist][i];
                if(dist==b[i])
                {
                    c[i].emplace_back(min_idx);
                }
                else if(dist < b[i])
                {
                    b[i]=dist;
                    c[i].clear();
                    c[i].emplace_back(min_idx);
                }
            }
        }
    }
    for(int i=0;i<a.size();i++)
    {
        cout<<i<<": "<<b[i]<<endl;
    }
    vector<int> path;
    vector<vector<int>> path_arr;
    backtracking(c,path_arr,path,3);
    for(int i=0;i<path_arr.size();i++)
    {
        for(int j=0;j<path_arr[i].size();j++)
        {
            cout<<path_arr[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

```

图数据

```

4 4
0 1 1
1 3 1
0 2 1
2 3 1

```