# 最短路徑
最短路徑顧名思義，是找尋圖上的最短路徑(從節點a走到節點b的邊權和)，以下介紹5種方法
## BFS
無權圖的最短路可用BFS，詳見[圖的遍歷](https://hackmd.io/-zVN5-S_T1-A98gINkpFLw)。以下的最短路皆為帶權圖中的最短路。
## bellman ford
### relax
[圖源](https://www.cnblogs.com/Ash-ly/p/5789746.html)
又稱為鬆弛，簡單來說就是**檢查走這邊會不會比較快**。
```cpp
vector<int> dis; //目前的最短路徑
bool relax(int u,int v,int weight){
if(dis[u]+weight<dis[v]){
dis[v]=dis[u]+weight;
return 1;
}
return 0;
}
```
### 原理
若最短路徑被「按照順序」鬆弛，則能確保它被找出來。
[圖源](https://ithelp.ithome.com.tw/articles/10209748)
在一張頂點數為V的圖中，最短路徑的長必不超過V-1(因為不可能有環)，那麼就暴力把所有邊都鬆弛V-1次，就能確保最短路徑有被被「按照順序」鬆弛，時間複雜度$O(VE)$
```cpp
int V; //頂點數
vector<vector<pair<int,int>>> g; //pair<連到的點,權重>
void Bellman_Ford(int s){ //s=出發點
for(pair<int,int> e:g[s]){ //初始化
dis[e.first]=e.second; //連到起點的設為權重，其他為無限大
}
for(int i=1;i<V;i++){
for(int u=1;u<=V;u++){
for(pair<int,int> e:g[u]){
relax(u,e.second,e.first);
}
}
}
}
```
### 負環
如果圖上有負環，則不可能有最短路徑(因為可以無限繞圈，而路徑會一直縮短)。如果已經relax V-1次的圖還能relax的話，代表它的最短路卡在負環之中。
```cpp
bool b=0;
for(int u=1;u<=V;u++){
for(pair<int,int> e:g[u]){
b=relax(u,e.second,e.first);
}
}
if(b) cout<<"有負環";
```
## SPFA
基本上是bellman ford的優化。用一個queue紀錄被relax的點，然後再更新它連出去的邊，這樣就不必每個邊都relax V-1次了。
```cpp
void SPFA(int s){
queue<int> q; //儲存待更新頂點
q.push(s); //初始化
dis[s]=0;
while(!q.empty()){ //直到沒有要更新的點
int cur=q.front();
q.pop();
for(pair<int,int> e:g[cur]){
if(relax(cur,e.first,e.second)){
q.push(e.first);
}
}
}
}
```
### 負環
用一個陣列儲存每個點被relax的次數。若超過V-1則有負環
## DAG
Directed Acyclic Graph，有向無環圖
### 拓樸排序
[圖源](https://web.ntnu.edu.tw/~algo/DirectedAcyclicGraph.html)
有向無環圖中，因為**有向**而且**無環**，所以只能照著一個方向往前走。所以可以排出一個順序:「若節點A指向節點B，則A排在B前面」，稱為拓樸排序
(註:拓樸排序可能不只一種)
### 實作
**DFS結束的順序**就是一種拓樸排序。因為DFS會一直往深處前進，所以比較晚結束的就會是排在前面的點。
```cpp
vector<vector<int>> g; //連到的點
vector<int> vis; //訪問狀態
deque<int> topo; //拓樸排序
void dfs(int k){
vis[k]=1;
for(int i:g[k]){
if(vis[i]==1){
cout<<"有環";
exit(0);
}
if(vis[i]==0) dfs(i);
}
vis[k]=2;
topo.push_front(k);
}
```
### 最短路徑
用陣列儲存每個點的最短路徑，再依照拓樸排序鬆弛。總複雜度$O(V+E)$，若確定是DAG就先用這個方法。
註:排序$O(V+E)$，鬆弛$O(E)$
```cpp
vector<int> dis(n+1,1e9); //各點的最短路徑
int w[n+1][n+1]; //w[a][b]=a連到b的權重
for(int i:topo){
for(int j:g[i]){
if(dis[j]+w[i][j]<dis[i]){
dis[i]=w[i][j]+dis[j];
}
}
}
```
## Dijkstra's
速度很快，但不能處理負邊
### 原理
紀錄每個點**候補**的最短距離，並且取出最小的距離成為確定值。因為從別的點繞過去，距離只會增加(沒有負邊)
### priority queue
優先權貯列，可以想成內部有排序的queue，每次只能取出最大或最小值，但實際上大多是heap(堆積)。可以log(n)插入和刪除，log(1)讀取。
```cpp
priority_queue<int, vector<int>,greater<int>> q1; //宣告(儲存的資料型態,指定容器,排序方法)
priority_queue<int> q2; //預設用vector,小排到大
priority_queue<int, vector<int>,cmp> q3; //自訂比較方式
```
關於自訂比較方式，與sort不同，不是使用bool函式來比較，而是需要重載()運算子
```cpp
struct cmp{
bool operator()(int a,int b){
return a>b;
}
};
```
### 實作
將所有候選距離存到priority queue之中，再一一取出，並relax取出的節點的相鄰節點(新的候補)
```cpp
#define f first
#define s second
vector<vector<pair<int,int>>> g; //{連到的點,權重}
vector<ll> dis; //確定的最短距離(預設為無限大)
vector<bool> complete; //是否已確定最短距離
struct cmp{ //自訂priority queue的比較法
bool operator()(pair<int,ll>& a,pair<int,ll>& b){
return a.s>b.s;
}
};
void dij(int s){ //s為起點
priority_queue<pair<int,int>,vector<pair<int,int>>,cmp> q; //紀錄候選路徑{點,距離}
dis[s]=0; //起點的距離為0
q.push({s,0}); //把起點加入候選
pair<int,int> cur; //現在處理的點，即每次取出的點
while(!q.empty()){ //持續到沒有候選
cur=q.top();q.pop(); //取出最短的點
if(complete[cur.f]) continue;
complete[cur.f]=1;
for(pair<int,int> i:g[cur.f]){ //鬆弛所有cur的相鄰節點
if(relax(cur.f,i.f,i.s)){ //若成功(路徑變短)，加入候選
q.push({i.f,dis[i.f]});
}
}
}
}
```
### 分析
複雜度$O((E+V)logV)$，挺快，但要注意不能有負邊，當然也不能檢查負環
Sign in with Wallet
Connect another wallet