---
# System prepended metadata

title: 最短路徑

---

# 最短路徑
最短路徑顧名思義，是找尋圖上的最短路徑(從節點a走到節點b的邊權和)，以下介紹5種方法

## BFS

無權圖的最短路可用BFS，詳見[圖的遍歷](https://hackmd.io/-zVN5-S_T1-A98gINkpFLw)。以下的最短路皆為帶權圖中的最短路。

## bellman ford 

### relax

![937718-20160820100015734-431165841](https://hackmd.io/_uploads/H1Ck-WlWR.png)


![937718-20160820100021312-298132088](https://hackmd.io/_uploads/B1kkbZlWC.png)

[圖源](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;
}
```

### 原理

若最短路徑被「按照順序」鬆弛，則能確保它被找出來。

![20111557Lo8gtTYUtj](https://hackmd.io/_uploads/BJkm4-eWA.png)

[圖源](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，有向無環圖

### 拓樸排序

![TopologicalOrdering3](https://hackmd.io/_uploads/By7kTy-bA.png)

[圖源](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)$，挺快，但要注意不能有負邊，當然也不能檢查負環 