圖里面可能有多條最短路徑，并且我們可能會(huì)想要獲得多條最短路徑

通過(guò)給每一個(gè)節(jié)點(diǎn)維護(hù)一個(gè)前面節(jié)點(diǎn)數(shù)組，當(dāng)新的距離等于這個(gè)節(jié)點(diǎn)當(dāng)前的距離時(shí)，不是拋棄這條路徑，而是將這條路徑保存到數(shù)組中，當(dāng)新的距離小于這個(gè)節(jié)點(diǎn)當(dāng)前的距離時(shí)，清空數(shù)組，將當(dāng)前路徑存入

最后通過(guò)回溯來(lái)獲得所有的路徑(廣度優(yōu)先搜索也行)

代碼

```

#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;
}

```

圖數(shù)據(jù)

```

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

```