https://www.bilibili.com/video/BV1zz4y1m7Nq/?spm_id_from=333.999.0.0&;vd_source=ee4f2554eda9915089c465f3a21398b7

代碼實現(xiàn)

```

#include <iostream>
#include <vector>

using namespace std;
int main()
{
??? int n,m;//節(jié)點數(shù), 邊數(shù)
??? cin>>n>>m;
??? vector<vector<int>> g;
??? for(int i=0;i<m;i++)
??? {
??????? int from,to,weight;
??????? cin>>from>>to>>weight;
??????? vector<int> edge;
??????? edge.emplace_back(from);
??????? edge.emplace_back(to);
??????? edge.emplace_back(weight);
??????? g.emplace_back(edge);
??? }

??? vector<int> a(n);//是否收錄 0 未收錄 1 收錄
??? vector<int> b(n,INT32_MAX);//從節(jié)點0開始，最短距離
??? b[0]=0;
??? vector<int> c(n,-1);//前面點
??? while(true)
??? {
??????? //檢查是否全部被收錄
??????? int flag=1;
??????? for(int i=0;i<a.size();i++)
??????? {
??????????? if(a[i]!=1)
??????????? {
??????????????? flag=0;
??????????????? break;
??????????? }
??????? }
??????? if(flag==1)
??????? {
??????????? break;
??????? }
??????? //在未收錄的節(jié)點中找到距離最小的節(jié)點
??????? int min_idx=-1;
??????? int min_dist=INT32_MAX;
??????? for(int i=0;i<a.size();i++)
??????? {
??????????? if(a[i]==0)
??????????? {
?????????????? if(b[i]<min_dist)
?????????????? {
??????????????????? min_idx=i;
??????????????????? min_dist=b[i];
?????????????? }
??????????? }
??????? }
??????? //將距離最小的節(jié)點收錄
??????? a[min_idx]=1;
??????? //嘗試更新這個節(jié)點相鄰節(jié)點的距離,和前面點
??????? for(int i=0;i<g.size();i++)
??????? {
??????????? if(g[i][0]==min_idx&&a[g[i][1]]!=1)
??????????? {
??????????????? int dist=b[min_idx]+g[i][2];
??????????????? if(b[g[i][1]]>dist)
??????????????? {
??????????????????? b[g[i][1]]=dist;
??????????????????? c[g[i][1]]=min_idx;
??????????????? }
?????????????? ?
??????????? }
??????? }
??? }
??? cout<<endl;
??? //輸出結(jié)果
??? for(int i=0;i<b.size();i++)
??? {
??????? cout<<i<<": "<<b[i]<<endl;
??????? cout<<i;
??????? int last=c[i];
??????? while(last!=-1)
??????? {
??????????? cout<<"<-"<<last;
??????????? last=c[last];
??????? }
??????? cout<<endl;
??? }
??? return 0;
}

```

數(shù)據(jù)(和視頻中一樣)

```

9 28
0 1 4
1 0 4
0 7 8
7 0 8
1 2 8
2 1 8
1 7 11
7 1 11
7 8 7
8 7 7
7 6 1
6 7 1
2 8 2
8 2 2
8 6 6
6 8 6
2 3 7
3 2 7
2 5 4
5 2 4
6 5 2
5 6 2
3 5 14
5 3 14
3 4 9
4 3 9
5 4 10
4 5 10

```