更新記錄
【1】2020.05.21-00:36
1.完善dijkstra
【2】2020.05.21-11:25
1.完善dijkstra堆優化
【3】2020.06.11-17:43
1.更新內容
正文
鉛制芝士（會一點點就行啦~）
- 動態規劃
- 貪心
- 鏈式前向星
- 堆
持續更新中...
最短路演算法是圖論演算法必學演算法之一
那么既然它這么重要，就更需要我們深入了解，熟練掌握
（默認圖為連通圖）
dijkstra演算法
有點貪心動規的意思
- 我們可以發現，起點到任何一個點的最短路都要經過至少一個的中轉點（起點s也算一個中轉點）
- 那么我們發現，如果想求出這個點的最短路，那么必定要求出它中轉點的最短路
-
- 首先dijkstra演算法不能處理負邊權，所以我們在使用時默認圖無負邊權
-
- 所以1-其中一個中轉點的最短路，一定小于等于1-終點的最短路
-
- 當小于時，中轉點比其先確定最短路
-
- 當等于時，誰先處理都是一樣的結果
- 那么依此類推，最后終將推到一個最最最簡單的問題：兩點間的最短路
這個問題只要你會存圖就會做
（很像動態規劃對不對）
^RT，我們要求出1-5的最短路徑
就必須求出起點到中轉點的最短路徑，中轉點為4
想求出1-4的最短路徑，就先去求1-3的最短路徑
同理求1-2的最短路
而1-2的最短路就是其連接的邊的權值
演算法思路：
定義變數（鏈式前向星的那堆變數就不再重復寫了）：
dis[i]：表示從起點到i的最短距離
f[i]：記錄這條邊有沒有被確定過最短路
s表示起點
初始化：dis[i]=∞;dis[s]=0
遍歷每一個點
- 對于每一個點a，找到一個dis[b]最小的頂點b
- b被確定過最短路
- 遍歷所有以b為起點的邊，更新它們的dis
演算法結束
#include<iostream>
using namespace std;
#define NUM 500050
#define INF 2147483647
struct Edge{
int na,np,w;
}e[NUM];
int head[NUM],dis[NUM],num,n,m,s,u,v,w,minn;
bool f[NUM];
inline void add(int f,int t,int w){
e[++num].na=head[f];
e[num].np=t,e[num].w=w;
head[f]=num;
}
int main(){
cin>>n>>m>>s;
for(int i=0;i<m;i++){
cin>>u>>v>>w;
add(u,v,w);
}
//初始化
for(int i=1;i<=n;i++) dis[i]=INF;
dis[s]=0;
//遍歷每一個點
for(int i=1;i<=n;i++){
//對于每一個點a，找到一個dis[b]最小的頂點b
minn=-1;
for(int o=1;o<=n;o++)
if(f[o]==0&&(dis[minn]>dis[o]||minn==-1)) minn=o;
//b被確定過最短路
f[minn]=1;
//遍歷所有以b為起點的邊，更新它們的dis
for(int o=head[minn];o!=0;o=e[o].na)
if(!f[e[o].np])
dis[e[o].np]=min(dis[e[o].np],dis[minn]+e[o].w);
}
//演算法結束，輸出s到各點的最短距離
for(int i=1;i<=n;i++) cout<<dis[i]<<" ";
}
dijkstra堆優化
我們可以發現，對于原來的dijkstra演算法，每次查找最小值時間復雜度都為O(n)
這顯然很慢啊！！！
那么有什么演算法可以在常數時間內求出最小值呢？
當然是（線段樹）堆啦！
建立一個小根堆，即可迅速求出所有資料的最小值
整個演算法的復雜度也降低了不少
我們發現，對于每次掃描，會有一些資料已經確定過最小值，再次進行掃描會浪費時間
所以我們要使用佇列來實作
最終結論：用優先佇列+二元組實作
明白了這個之后，這道題對你來說+巖漿=黑曜石
#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
#define ll int
#define NUM 500050
#define INF 2147483647
struct Edge{
int na,np,w;
}e[NUM];
ll head[NUM],dis[NUM],num,n,m,s,u,v,w,minn,bf,i;
bool f[NUM];
priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,greater<pair<ll,ll> > >q;
inline void add(int f,int t,int w){
e[++num].na=head[f];
e[num].np=t,e[num].w=w;
head[f]=num;
}
inline int read() {
int X=0,W=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') W=-1; c=getchar(); }
while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
return X*W;
}
int main(){
n=read();m=read();s=read();
for(i=0;i<m;++i){
u=read();v=read();w=read();
add(u,v,w);
}
for(int i=1;i<=n;++i) dis[i]=INF;
dis[s]=0;
//以上全部為初始化
q.push(make_pair(0,s));
//將起點壓進佇列
while(q.size()){
//如果佇列里還有元素
bf=q.top().second;q.pop();
//bf為當前次遍歷的起點，保存后將這個元素彈出
if(f[bf]) continue;
//搜過了就不搜了
f[bf]=1;
//沒搜過就標記一下
for(int i=head[bf];i;i=e[i].na){
//同樣的遍歷
if(dis[bf]+e[i].w<dis[e[i].np]){
//找到了更短的路徑
dis[e[i].np]=dis[bf]+e[i].w;
//更新
q.push(make_pair(dis[e[i].np],e[i].np));
//既然有更優解那就將這個點壓進佇列，用來更新其他點
}
}
}
for(int i=1;i<=n;++i) printf("%d ",dis[i]);
//out
}
那么至于為什么make_pair的引數是最短距離，邊的終點呢？
為什么不反過來存或存其他的引數呢
因為這是個自動排序的優先佇列啊
因為二元組自帶排序規則啊
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/197179.html
標籤：其他
上一篇：深度學習工程師能力模型