---
tags: 2023-i2cp

type: slide

slideOptions:
transition: fade;

---

<style>
.reveal .slides {
text-align: left;
font-size:30px;
}
#red{
color:red;
}
#gre{
color:green;
}
</style>

# Shortest Path

Introduction to Competitive Programming
2/22

----

- Single Source Shortest Paths
- Dijkstra
- Bellman-Ford
- SPFA
- All Pair Shortest Paths
- Floyd Warshall

----

## Single Source Shortest Paths
### 單源最短路徑

給定起點，求出起點到所有點的最短路徑


- Dijkstra
- Bellman-Ford
- SPFA

----

## All Pair Shortest Paths
### 全點對最短路徑
求出圖上所有點對的最短路徑


- Floyd Warshall

----

## 複習一下建圖

初始化 有 n 個點，編號為 0~n-1

int n;
vector<pair<int, int>> edge[MXN];
void init(int _n){
    n = _n;
    for(int i = 0; i < n ;i++){
        edge[i].clear();
    }
}

----

## 複習一下建圖

單向圖 (一條點 u 連向點 v 權重為 w 的邊)

void addEdge(int u, int v, int w){
    edge[u].push_back({v, w});
}

雙向圖 (一條點 u 與點 v 連通權重為 w 的邊)

void addEdge(int u, int v, int w){
    edge[u].push_back({v, w});
    edge[v].push_back({u, w});
}

---

- Single Source Shortest Paths
- <span><!-- .element: class="fragment highlight-red" -->Dijkstra</span>
- Bellman-Ford
- SPFA
- All Pair Shortest Paths
- Floyd Warshall

----

## 想法

設 w[a][b] 為點 a 到點 b 的邊權重
先將所有點到起點的距離設為無限大 ( 用 dis 陣列紀錄 )
而且起點自己本身的距離設為 0

重複以下步驟，直到全部點都走過為止

1. 選從還沒走過的點中，離起點最近的點
2. 將此點設定為走過
3. 窮舉此點所有連到的點，進行鬆弛

----

## 鬆弛 (relaxation)

在計算最短路徑時，
已知從原點到點 $u$ 的最短路徑為 dis[$u$]，到點$v$的距離為 dis[$v$]
對於邊 $e(u, v)$，若我們可以從點 $u$ 出發經過 $e$ 更新點 $v$ 的最短路徑
則我們稱透過 $e$ 進行了一次鬆弛操作

也就是我們用 dis[$u$]+$e$ 使得 dis[$v$] 更小


以上圖為例，我們可以透過邊 (2, 3)，去鬆弛從起點到點3的最短路徑

----

## code

透過點 $u$ 經過一條權重為 $w$ 的邊，去鬆弛點 $v$


void relaxation(int u, int v, int w){
    if(dis[v] > dis[u] + w){
        dis[v] = dis[u] + w;
    }
}

----

## dijkstra

1. <span id="red">選從還沒走過的點中，離起點最近的點</span>
2. 將此點設定為走過
3. 窮舉此點所有連到的點，進行鬆弛

<div style="position: absolute; right: 0%; top:90%;">


</div>

<div style="position: absolute; right: 65%;">

| node | dis[i] | visit[i] |
| ------ | ------ | -------- |
| 1 | 0 | false |
| 2 | INF | false |
| 3 | INF | false |
| 4 | INF | false |
| 5 | INF | false |
| 6 | INF | false |

</div>

----

## dijkstra

1. 選從還沒走過的點中，離起點最近的點
2. <span id="red">將此點設定為走過</span>
3. 窮舉此點所有連到的點，進行鬆弛

<div style="position: absolute; right: 0%; top:90%;">


</div>

<div style="position: absolute; right: 65%;">

| node | dis[i] | visit[i] |
| ------ | ------ | -------- |
| 1 | 0 | <span id="red">true</span> |
| 2 | INF | false |
| 3 | INF | false |
| 4 | INF | false |
| 5 | INF | false |
| 6 | INF | false |

</div>

----

## dijkstra

1. 選從還沒走過的點中，離起點最近的點
2. 將此點設定為走過
3. <span id="red">窮舉此點所有連到的點，進行鬆弛</span>

<div style="position: absolute; right: 0%; top:90%;">


</div>

<div style="position: absolute; right: 60%;">

| node | dis[i] | visit[i] |
| ------ | ------ | -------- |
| 1 | 0 | true |
| 2 | INF | false |
| 3 | INF | false |
| 4 | INF | false |
| 5 | INF | false |
| 6 | ~~INF~~ $\to$ <span id="gre">10</span> | false |

</div>

----

## dijkstra

1. 選從還沒走過的點中，離起點最近的點
2. 將此點設定為走過
3. <span id="red">窮舉此點所有連到的點，進行鬆弛</span>

<div style="position: absolute; right: 0%; top:90%;">


</div>

<div style="position: absolute; right: 60%;">

| node | dis[i] | visit[i] |
| ------ | ------ | -------- |
| 1 | 0 | true |
| 2 | ~~INF~~ $\to$ <span id="gre">5</span> | false |
| 3 | INF | false |
| 4 | INF | false |
| 5 | INF | false |
| 6 | 10 | false |

</div>

----

## dijkstra

1. 選從還沒走過的點中，離起點最近的點
2. 將此點設定為走過
3. <span id="red">窮舉此點所有連到的點，進行鬆弛</span>

<div style="position: absolute; right: 0%; top:90%;">


</div>

<div style="position: absolute; right: 60%;">

| node | dis[i] | visit[i] |
| ------ | ------ | -------- |
| 1 | 0 | true |
| 2 | 5 | false |
| 3 | ~~INF~~ $\to$ <span id="gre">3</span> | false |
| 4 | INF | false |
| 5 | INF | false |
| 6 | 10 | false |

</div>

----

## dijkstra

1. <span id="red">選從還沒走過的點中，離起點最近的點</span>
2. 將此點設定為走過
3. 窮舉此點所有連到的點，進行鬆弛

<div style="position: absolute; right: 0%; top:90%;">


</div>

<div style="position: absolute; right: 60%;">

| node | dis[i] | visit[i] |
| ------ | ------ | -------- |
| 1 | 0 | true |
| 2 | 5 | false |
| 3 | 3 | false |
| 4 | INF | false |
| 5 | INF | false |
| 6 | 10 | false |

</div>

----

## dijkstra

1. 選從還沒走過的點中，離起點最近的點
2. <span id="red">將此點設定為走過</span>
3. 窮舉此點所有連到的點，進行鬆弛

<div style="position: absolute; right: 0%; top:90%;">


</div>

<div style="position: absolute; right: 60%;">

| node | dis[i] | visit[i] |
| ------ | ------ | -------- |
| 1 | 0 | true |
| 2 | 5 | false |
| 3 | 3 | <span id="red">true</span> |
| 4 | INF | false |
| 5 | INF | false |
| 6 | 10 | false |

</div>

----

## dijkstra

1. 選從還沒走過的點中，離起點最近的點
2. 將此點設定為走過
3. <span id="red">窮舉此點所有連到的點，進行鬆弛</span>

<div style="position: absolute; right: 0%; top:90%;">


</div>

<div style="position: absolute; right: 60%;">

| node | dis[i] | visit[i] |
| ------ | ------ | -------- |
| 1 | 0 | true |
| 2 | 5 | false |
| 3 | 3 | true |
| 4 | ~~INF~~ $\to$ <span id="gre">6</span> | false |
| 5 | INF | false |
| 6 | 10 | false |

</div>

----

## dijkstra

1. 選從還沒走過的點中，離起點最近的點
2. <span id="red">將此點設定為走過</span>
3. 窮舉此點所有連到的點，進行鬆弛

<div style="position: absolute; right: 0%; top:90%;">


</div>

<div style="position: absolute; right: 60%;">

| node | dis[i] | visit[i] |
| ------ | ------ | -------- |
| 1 | 0 | true |
| 2 | 5 | <span id="red">true</span> |
| 3 | 3 | true |
| 4 | 6 | false |
| 5 | INF | false |
| 6 | 10 | false |

</div>

----

## dijkstra

1. 選從還沒走過的點中，離起點最近的點
2. 將此點設定為走過
3. <span id="red">窮舉此點所有連到的點，進行鬆弛</span>

<div style="position: absolute; right: 0%; top:90%;">


</div>

<div style="position: absolute; right: 60%;">

| node | dis[i] | visit[i] |
| ------ | ------ | -------- |
| 1 | 0 | true |
| 2 | 5 | true |
| 3 | 3 | true |
| 4 | 6 | false |
| 5 | INF | false |
| 6 | ~~10~~ $\to$ <span id="gre">7</span> | false |

</div>

----

## dijkstra

1. 選從還沒走過的點中，離起點最近的點
2. 將此點設定為走過
3. <span id="red">窮舉此點所有連到的點，進行鬆弛</span>

<div style="position: absolute; right: 0%; top:90%;">


</div>

<div style="position: absolute; right: 60%;">

| node | dis[i] | visit[i] |
| ------ | ------ | -------- |
| 1 | 0 | true |
| 2 | 5 | true |
| 3 | 3 | true |
| 4 | 6 | false |
| 5 | ~~INF~~ $\to$ <span id="gre">10</span> | false |
| 6 | 7 | false |

</div>

----

## dijkstra

1. <span id="red">選從還沒走過的點中，離起點最近的點</span>
2. 將此點設定為走過
3. 窮舉此點所有連到的點，進行鬆弛

<div style="position: absolute; right: 0%; top:90%;">


</div>

<div style="position: absolute; right: 60%;">

| node | dis[i] | visit[i] |
| ------ | ------ | -------- |
| 1 | 0 | true |
| 2 | 5 | true |
| 3 | 3 | true |
| 4 | 6 | false |
| 5 | 10 | false |
| 6 | 7 | false |

</div>

----

## dijkstra

1. 選從還沒走過的點中，離起點最近的點
2. <span id="red">將此點設定為走過</span>
3. 窮舉此點所有連到的點，進行鬆弛

<div style="position: absolute; right: 0%; top:90%;">


</div>

<div style="position: absolute; right: 60%;">

| node | dis[i] | visit[i] |
| ------ | ------ | -------- |
| 1 | 0 | true |
| 2 | 5 | true |
| 3 | 3 | true |
| 4 | 6 | <span id="red">true</span> |
| 5 | 10 | false |
| 6 | 7 | false |

</div>

----

## dijkstra

1. 選從還沒走過的點中，離起點最近的點
2. 將此點設定為走過
3. <span id="red">窮舉此點所有連到的點，進行鬆弛</span>

<div style="position: absolute; right: 0%; top:90%;">


</div>

<div style="position: absolute; right: 60%;">

| node | dis[i] | visit[i] |
| ------ | ------ | -------- |
| 1 | 0 | true |
| 2 | 5 | true |
| 3 | 3 | true |
| 4 | 6 | true |
| 5 | ~~10~~ $\to$ <span id="gre">9</span> | false |
| 6 | 7 | false |

</div>

----

## dijkstra

1. <span id="red">選從還沒走過的點中，離起點最近的點</span>
2. 將此點設定為走過
3. 窮舉此點所有連到的點，進行鬆弛

<div style="position: absolute; right: 0%; top:90%;">


</div>

<div style="position: absolute; right: 60%;">

| node | dis[i] | visit[i] |
| ------ | ------ | -------- |
| 1 | 0 | true |
| 2 | 5 | true |
| 3 | 3 | true |
| 4 | 6 | true |
| 5 | 9 | false |
| 6 | 7 | false |

</div>

----

## dijkstra

1. 選從還沒走過的點中，離起點最近的點
2. <span id="red">將此點設定為走過</span>
3. 窮舉此點所有連到的點，進行鬆弛

<div style="position: absolute; right: 0%; top:90%;">


</div>

<div style="position: absolute; right: 60%;">

| node | dis[i] | visit[i] |
| ------ | ------ | -------- |
| 1 | 0 | true |
| 2 | 5 | true |
| 3 | 3 | true |
| 4 | 6 | true |
| 5 | 9 | false |
| 6 | 7 | <span id="red">true</span> |

</div>

----

## dijkstra

1. <span id="red">選從還沒走過的點中，離起點最近的點</span>
2. 將此點設定為走過
3. 窮舉此點所有連到的點，進行鬆弛

<div style="position: absolute; right: 0%; top:90%;">


</div>

<div style="position: absolute; right: 60%;">

| node | dis[i] | visit[i] |
| ------ | ------ | -------- |
| 1 | 0 | true |
| 2 | 5 | true |
| 3 | 3 | true |
| 4 | 6 | true |
| 5 | 9 | false |
| 6 | 7 | true |

</div>

----

## dijkstra

1. 選從還沒走過的點中，離起點最近的點
2. <span id="red">將此點設定為走過</span>
3. 窮舉此點所有連到的點，進行鬆弛

<div style="position: absolute; right: 0%; top:90%;">


</div>

<div style="position: absolute; right: 60%;">

| node | dis[i] | visit[i] |
| ------ | ------ | -------- |
| 1 | 0 | true |
| 2 | 5 | true |
| 3 | 3 | true |
| 4 | 6 | true |
| 5 | 9 |<span id="red">true</span> |
| 6 | 7 | true |

</div>

----

## 最短路徑表格

<div style="position: absolute; right: 75%; top:90%;">

| node | dis[i] |
| ------ | ------ |
| 1 | 0 |
| 2 | 5 |
| 3 | 3 |
| 4 | 6 |
| 5 | 9 |
| 6 | 7 |

</div>

<div style="position: absolute; right: 20%; top:90%;">


</div>

----

## 性質

每條最短路徑都是其他最短路徑所延伸的，把全部最短路徑畫出來
最後會形成一顆最短路徑樹 (可能不只一種)

<div style="position: absolute; right: 0%; top:90%;">


</div>

<div style="position: absolute; right: 50%; top:200%;">

$\to$

</div>

<div style="position: absolute; right: 60%; top:90%;">


</div>

----

## 實作

0. 初始化
1. 選從還沒走過的點中，離起點最近的點
2. 將此點設定為走過
3. 窮舉此點所有連到的點，進行鬆弛

----

## 初始化

將除了起點的點距離設為無限大
而無限大通常設為一個比可能的最短路徑還大的權重

#define INF 1e18
for(int i=0;i<n;i++){
    if(i == start)
        dis[i] = 0;
    else
        dis[i] = INF;
}

----

1. 選從還沒走過的點中，離起點最近的點
2. 將此點設定為走過
3. 窮舉此點所有連到的點，進行鬆弛

while(1){
    int ind = -1, mx = INF;
    for(int i = 0; i < n; i++){ // 1. 選從還沒走過的點中，離起點最近的點
        if(!vis[i] && dis[i] < mx){
            ind = i, mx  = dis[i];
        }
    }
    if(ind == -1)  // 如果全部點都走過則結束演算法
        break;
    vis[ind] = 1; // 2. 將此點設定為走過
    for(int i = 0; i < edge[ind].size(); i++){  // 3. 窮舉此點所有連到的點，進行鬆弛
        int u = edge[ind].to, w = edge[ind].weight;
        if(dis[u] > dis[ind] + w){
            dis[u] = dis[ind] + w;
        }
    }
}

----

## 複雜度

根據演算法
1. 選從還沒走過的點中，離起點最近的點
2. 將此點設定為走過
3. 窮舉此點所有連到的點，進行鬆弛

每個點會走過一次，會花 $O(N)$ 時間找離起點最近的點
接著再跑過 $M$ 條邊 (每條邊最多被跑過一次)

因此複雜度為 $O(N^2 + M)$

----

來看看題目的範圍大小

[CSES : Shortest Routes I
](https://cses.fi/problemset/task/1671)

算起來約為 $10^{10}$
怎麼看都會 `TLE`

----

## 優化
1. 選從還沒走過的點中，離起點最近的點
2. 將此點設定為走過
3. 窮舉此點所有連到的點，進行鬆弛

每次都是從還沒走過的點中選距離最小的
則我們可以用 pririty_queue 存起來，每次取 top
當有更新邊的時候，則丟進去 priority_queue 裡面

----

## 實作

priority_queue 裡面存有被鬆弛過的點
一開始將原點丟進去，接著一直鬆弛直到沒有邊可以鬆弛為止

----

## 範例程式碼(求出 s 到 t 的最短路徑)

#define ll long long
int n, m, s, t;
ll dis[MXN];
vector<pair<int, ll>> edge[MXN];
priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq; // 為了方便實作，用pair包起來會先比較距離大小
void init(){
    cin >> n >> m >> s >> t;
    for(int i = 0, u, v, w; i < m; i++){
        cin >> u >> v >> w;
        edge[u].emplace_back(v, w);
    }
}
long long dijkstra(){ //求出 s 到 t 的最短路徑
    memset(dis, 0x3f, sizeof(dis)); // 初始化所有距離為無限大
    
    dis[s] = 0; // 起點距離為 0
    pq.push(make_pair(dis[s], s));  // 從起點出發

    while(!pq.empty()){
        auto [d, u] = pq.top(); pq.pop();
        if(vis[u])    continue;  // 確保每個點最多只被走過一遍
        vis[u] = 1;
        for(int i = 0; i < edge[u].size(); i++){  // 窮舉此點所有連到的點
            int v = edge[u][i].to, w = edge[u][i].weight;
            if(dis[v] > dis[u] + w){
                dis[v] = dis[u] + w;  // 鬆弛
                pq.push(make_pair(dis[v], v)); // 如果有更新距離，則丟進 priority_queue
            }
        }
    }
    return dis[t];
}
int main(){
    init();
    cout << dijkstra() << endl;
}

----

## 複雜度

總共 $N$ 個點，每個點只走過一遍
用 priority_queue 優化 $O(N)\to O(\log N)$

每條邊被遍歷過一次 $O(M)$

總複雜度 $O(M + M\log N)$

----

## 限制

dijkstra 演算法只能跑邊權重 $\ge 0$ 的圖
因為核心概念：每次都跑還沒走過的點中最近的

所以如果出現負權邊，則會違反以上條件

----


以上圖為例先用點 1 更新點 2，距離為 3
在更新點 3 時，會發現點3的距離變成 -2，比點 1、2 都還要離起點更近，則違反演算法

----

因此在做 dijkstra 時，要確保邊權重沒有負的，否則正確性會爛掉

----

## Another Problem

NCPC 2021 final

----

## Target

maximum number of unvisited spot along shortest path

- Time Limit: 2 second
- testcase $\le 16$
- $N, M\le 10^5$

dijkstra $\to O(T \cdot M \log N)\approx 2.6\cdot 10^7$

----

## Contest Result

problem J
Accepted: 34/109 teams
First Accepted: 21 min

<div style="position: absolute; right: 20%;top: -8%;">


</div>

----

classic dijkstra

long long dis[N];

this problem

pair<long long, int> dis[N];    //shorter path then more unvisited spot

----

## Number of Shortest Path ([UVa 10917](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=16&page=show_problem&problem=1858))

Given a directed positive weighted graph, count number of shortest path from vertex $S$ to $T$ module 2147483647

- $1\le N, M\le 2\cdot 10^5$


from 1 to 5: {1, 2, 3, 4, 5}, {1, 2, 4, 5}, {1, 5} $\to$ 3 ways

----

### The distance of each vertex


----

### The edge on the shortest path (red edge)


----

從 1 到 5 的最短路徑個數為

所有到 5 的邊中為最短路徑上的邊的來源點

到點 1 的最短路徑數量 + 到點 4 的最短路徑數量


----

會發現所有最短路徑上的邊連成的圖
是一張有向無環圖 $\to$ DP on DAG


----

bool vis[N];
ll dp[N];
ll DP(int x){
    if(vis[x])    return dp[x];
    vis[x] = 1;
    if(x == startPoint){
        dp[x] = 1;
        return dp[x];
    }
    for(auto [from, len] : from[x]){
        if(dis[from] + len == dis[x]){
            dp[x] += DP(from);
            dp[x] %= MOD;
        }
    }
    return dp[x];
}
int main(){
    dijkstra();
    cout << DP(endPoint) << endl;
}

---

- Single Source Shortest Paths
- Dijkstra
- <span><!-- .element: class="fragment highlight-red" -->Bellman-Ford</span>
- SPFA
- All Pair Shortest Paths
- Floyd Warshall

----

## 想法

類似 dijkstra
每次嘗試邊集合去鬆弛最短路徑
直到沒有點可以進行鬆弛為止
<!-- 對圖上的兩個點 A、B，如果可以找到一個邊g[a][b] -->

----

## 嘗試鬆弛

for(int i = 0; i < m; i++){ // 對於所有邊都嘗試鬆弛
    if(dis[ edge[i].to ] > dis[ edge[i].from ] + edge[i].weight){
        dis[ edge[i].to ] = dis[ edge[i].from ] + edge[i].weight;
    }
}

而最差情況下我們需要鬆弛幾輪才能找到全部點的最短路徑?

----

$N$ 個點，最差的情況下需要 $N-1$ 輪鬆弛
每輪鬆弛都只更新到一個點，而最遠的情況下連 $N-1$ 條邊

<span>  <!-- .element: class="fragment" data-fragment-index="1" --></span>
<span>  <!-- .element: class="fragment" data-fragment-index="2" --></span>
<span>  <!-- .element: class="fragment" data-fragment-index="3" --></span>

----

## 複雜度

每輪鬆弛 $O(M)$
最多鬆弛 $N-1$ 輪

因此為 $O(NM)$

for(int j = 0; j < n-1; j++){
    for(int i = 0; i < m; i++){ // 對於所有邊都嘗試鬆弛
        if(dis[ edge[i].to ] > dis[ edge[i].from ] + edge[i].weight){
            dis[ edge[i].to ] = dis[ edge[i].from ] + edge[i].weight;
        }
    }
}

----

## 負環

假設 1 為源點，要求出點 1 到所有點的最短路徑


在有負環 (234) 的情況下，找不到最短路徑
如果用 Bellman-ford，則永遠更新不完

----

## 偵測負環

因此假設我們要找一張圖有沒有負環，則可以使用 Bellman-ford
在沒有負環的情況下，我們最多只需要跑 $n-1$ 次後，則找不到點去鬆弛

因此跑完 $n-1$ 次之後，我們再多跑一次，只要有點可以鬆弛，則代表此圖有負環

---

- Single Source Shortest Paths
- Dijkstra
- Bellman-Ford
- <span><!-- .element: class="fragment highlight-red" -->SPFA</span>
- All Pair Shortest Paths
- Floyd Warshall

----

## SPFA(Shortest Path Faster Algorithm)

Bellman-ford 優化版

----

在Bellman-ford的演算法中，每次鬆弛都會跑過全部的邊
但實際上很多次都是非必要的

假設有一條邊 $x$ 連到 $y$，在點 $x$ 都還沒被鬆弛的情況下，則還沒必要用這條邊來鬆弛 $y$

因此我們可以用一個 queue 來儲存哪些點被鬆弛過，只跑 queue 裡面的點就好

----

寫起來類似 dijkstra

queue<int> que;
que.push(start); // 起點一開始為 0 放進去鬆弛其他點
while(!que.empty()){
    int u = que.front(); que.pop();
    for(int i = 0; i < edge[u].size(); i++){
        if(dis[ edge[u][i].to ] > dis[u] + edge[u][i].weight){
            dis[ edge[u][i].to ] = dis[u] + edge[u][i].weight;
            que.push(edge[u][i].to); // 如果被鬆弛，則可以拿來鬆弛其他點
        }
    }
}

----

接著如果一個點已經在 queue 裡面了，則不需要重複 push 進去
因此我們可以用一個 bool 陣列紀錄是否已經在 queue 裡面

bool inque[N]; // 紀錄是否已經在 queue 裡面
queue<int> que;
que.push(start);
while(!que.empty()){
    int u = que.front(); que.pop();
    inque[u] = 0; // 從 queue 拿出來設成 0
    for(int i = 0; i < edge[u].size(); i++){
        int v = edge[u][i].to, w = edge[u][i].weight;
        if(dis[v] > dis[u] + w){    
            dis[v] = dis[u] + w; // 鬆弛
            if(!inque[v]){
                que.push(v);
                inque[v] = 1; // 放進 queue 裡面設成 1    
            }
        }
    }
}

----

## 利用 SPFA 判斷負環

原本 Bellman-ford 判斷負環的方法是先跑 $N-1$ 輪鬆弛
第 $N$ 輪時檢查是否有點能在被鬆弛

但現在改為用 queue 之後無法判斷
因此我們要設一個 len 陣列，紀錄每個點從起點開始是第幾輪被更新到
超過 $N-1$ 輪還可以更新，則代表有負環的出現

<div style="position: absolute; right: 80%;">


</div>

<div style="position: absolute; right: 40%;">


</div>

----

## 程式碼

int len[N]; // 紀錄每個點是第幾輪被鬆弛到
bool inque[N];
queue<int> que;
que.push(start);
while(!que.empty()){
    int u = que.front(); que.pop();
    if(len[u] > n-1)    return -1; // 超過 n-1 輪，找到負環
    inque[u] = 0;
    for(int i = 0; i < edge[u].size(); i++){
        int v = edge[u][i].to, w = edge[u][i].weight;
        if(dis[v] > dis[u] + w){
            dis[v] = dis[u] + w;
            len[v] = len[u] + 1; // 從來的點 +1輪被鬆弛到
            if(!inque[v]){       // 如果本來沒在 queue 裡就丟進去
                que.push(v);
                inque[v] = 1;    // 紀錄是否在 queue 裡
            }
        }
    }
}

----

## 優化

使用 deque 取代 queue
原本：queue 的 front 取出來，改成：deque 從頭尾判斷哪個的距離比較小

if dis[ deq.front ] <= dis[ deq.back ] 
    pop front
else
    pop back

想法：由於要找負環，所以順序從距離越小越好

----

## 程式碼

deque<int> deq; // 改成 deque
deq.push_back(start);
while(!que.empty()){
    // 取頭尾離起點距離較小的點
    int u = (dis[deq.front()] < dis[deq.back()] ? deq.front():deq.back()); 
    dis[deq.front()] < dis[deq.back()] ? deq.pop_front():deq.pop_back();
    if(len[u] > n-1)    return -1;
    inque[u] = 0;
    for(int i = 0; i < edge[u].size(); i++){
        int v = edge[u][i].to, w = edge[u][i].weight;
        if(dis[v] > dis[u] + w){
            dis[v] = dis[u] + w;
            len[v] = len[u] + 1;
            if(!inque[v]){
                inque[v] = 1;
                que.push(v);
            }
        }
    }
}

----

## 複雜度

號稱 $O(N)$，在一般 random 產出來的圖跑十分的快

但
上面的優化大部分都是想法或常數上的優化
實際上最差的情況下複雜度依舊是 $O(NM)$
並且常數巨大在最差的情況下會跑得比 Bellman-ford 慢

~~不過台灣站的測資大部分很爛~~

----

## Problem

NCPC 2019 final


----

## Target

Ask is there any negative cycle path in the graph?

- testcase $\le 40$
- $N\le 100$
- $M\le ?\to N^2$

SPFA $\to O(T\cdot NM) = 4\cdot 10^7$

----

## Contest Result

AC in Contest: 38/92 teams
First Accepted: 8 mins


<div style="position: absolute; right: 20%;top: -8%;">


</div>

---

- Single Source Shortest Paths
- Dijkstra
- Bellman-Ford
- SPFA
- <span><!-- .element: class="fragment highlight-red" -->All Pair Shortest Paths</span>
- <span><!-- .element: class="fragment highlight-red" -->Floyd Warshall</span>

----

## 想法

如果要求一個點對的最短路徑，可能會經過 $V_1$、$V_2$ ...這些點

我們稱 $V_i$ 這些點為中繼點

只要窮舉每一個中繼點去更新最短路徑，

就可以更新到全部的最短路徑。

----

## 例子

設 `dis[i][j]` 為從點 `i` 到點 `j` 的距離

下圖為例，我們可以知道 `dis[1][2]` 為 `7`，`dis[2][3]` 為 `2`
如果我們想算 `dis[1][3]` 則可以透過中繼點 `2` 來去更新 `1` 到 `3` 的最短路徑

`dis[1][3] = min( dis[1][3], dis[1][2] + dis[2][3]);`


----

以此類推，想算出 `dis[1][4]`
則可以透過點 `3` 來更新

`dis[1][4] = min( dis[1][4], dis[1][3] + dis[3][4]);`


----

依序加一個點當中繼點
接著窮舉所有點對 `(i, j)`，計算 `dis[i][j]` 從 `i` 出發經過中繼點在到 `j` 會不會更短

int dis[N][N];
for(int k = 0; k < n; k++){ // 窮舉中繼點 k
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){ // 窮舉點對 (i, j)
            dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j]);
        }
    }
}

----

## 初始化

先將所有點對距離設為無限大，除了自己到自己距離為 `0`

for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
        if(i != j)
            dis[i][j] = INF;
        else
            dis[i][j] = 0;
    }
}

對於給定的邊 `(u, v, w)`，更新 `dis[u][v] = w`

cin>> u >> v >> w;
dis[u][v] = min(dis[u][v], w);

----

## Complexity

Time Complexity： 3 loops $\to O(N^3)$
Space Complexity： 2D array $\to O(N^2)$

Actually, even if $N$ up to 1000, it can be passed within 1 second!

----

## Problem

NCPC 2019 final

Check Negative Cycle

----

如果存在負環，則繞一圈之後回到自己距離會變更短

----

## Floyd Warshall

dis[u][u] 一開始初始化成 0

如果存在負環，則跑完最短路徑後 dis[u][u] 會 < 0

----

$testcase\le 40$
$n\le 100$

$O(T\cdot N^3) = 4\cdot 10^7\to AC !$

----

## Problem

2020 NCPC preliminary


----

## Target

Given $N\times N$ all pairs shortest path.

There are $K$ operation, each operation update road length
between $u$ and $v$ to $w$.

After each operation print number of pair that reduced shortest path.

- testcase $\le 10$
- $N\le 1000$
- $K\le 50$

----

## Contest Result

problem E
Accpted: only 2/168 teams AC in contest
First Accpted: 142 mins


----

每次有一條邊更新，有影響的最短路有哪些?

----

每次有一條邊更新，有影響的最短路有哪些?

有被影響的只有通過這條新邊的點對 !

----

分別窮舉以這兩個端點為中繼點的最短路徑
判斷是否有更新

----

每次更新 $O(N^2)$，總共 $K$ 筆更新

- testcase $\le 10$
- $N\le 1000$
- $K\le 50$

複雜度 $O(T\cdot N^2K)$ = 5e8

2 second can AC

----

void update(int u, int v, int k){
    dis[u][v] = dis[v][u] = min(dis[v][u], k);
    
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            dis[i][j] = min(dis[i][j], dis[i][v] + dis[v][j]); // update with v
            dis[i][j] = min(dis[i][j], dis[i][u] + dis[u][j]); // update with u
        }
    }
}

---

### Single Source Shortest Path

| Algorithm | Time Complexity |
| -------- | -------- |
| Dijkstra | $O(V^2)$ |
| Dijkstra+PQ | $O(E\log V)$ |
| Bellman Ford | $O(VE)$ |
| SPFA | $O(VE)$ |

### All Pair Shortest Path

| Algorithm | Time Complexity |
| -------- | -------- |
| Floyd Warshall | $O(V^3)$ |

----

## Homework

deadline: 3/1
link: https://vjudge.net/contest/543564