# 多源最短路徑(All pairs shortest paths/ multiple source shortest paths)

在Dijkstra後，應該了解了圖論的基本內容，所以就能夠繼續延伸幾個常見的圖論相關演算法。
更準確來說Dijkstra是<span style="color:red;">單源最短路徑</span>，也就是說每次使用Dijkstra，通常都是針對<span style="color:red;">某個起點</span>，那如果我們想要一次"處理多個起點和終點"呢？

所以可以簡單歸類為以下幾種

1. single source shortest path without negative cycle
2. multiple source shortest path without negative cycle (All pairs)
3. single source shortest path with negative cycle

那為甚麼沒有"全對全"有負環？

## 核心概念只有五行的演算法 - Floyd-Warshall 演算法

我們現在要找的是任意兩個點之間的最短路徑，也稱作「多源最短路徑」。
先將圖的資訊存到二維矩陣中。
| | 1 | 2 | 3 | 4 |
|---|----|----|----|----|
| 1 | 0 | 2 | 6 | 4 |
| 2 | ∞ | 0 | 3 | ∞ |
| 3 | 7 | ∞ | 0 | 1 |
| 4 | 5 | ∞ | 12 | 0 |

而這邊就要提到一個很重要的概念-<span style="color:red;">鬆弛</span>了
如果我們要求任意兩個點的最短距離，但有些點不能直達，勢必要有經過中間點才行。
我們來看看以下的分析：

4 → 3　為　12
4 → 1 → 3　為　11
4 → 1 → 2 → 3　為　10

- 這表示當兩點之間沒有經過第三點時，兩點間的初始距離就是最短路徑。
- 但若有經過中轉，可能不只一個，能讓總路徑變得更短。
我們只要透過多次的中轉，和初始的路徑比較，如果能讓兩點之間的路徑變短，就更新。好比 4 到 3 的原始距離為 12，4 到 1 的距離為 5，加上 1 到 3 的距離為 6 共 11，比原始 12 小，我們就讓二為矩陣中 4 到 3 的距離更新為 11 。因為我們只看最短路徑，不討論最少的中轉次數，所以可以這麼做。

所以只要「逐步嘗試把每個點 k 當作中繼點，看看經過它會不會更短」
在嘗試全部點後，得出的肯定就是最短路徑。

先來看以下程式碼

FloydWarshallAlgorithm(){
  for k in 0 to n - 1{
    for i in 0 to n - 1{
      for j in 0 to n - 1{
        if (distance[i][j] > distance[i][k] + distance[k][j]){
          distance[i][j] = distance[i][k] + distance[k][j]
}}}}}

最外層就表示
- 表示「現在嘗試的中繼點」
- 第 k 次迭代後，代表我們已經考慮過 <span style="color:red;"> 0 ~ k </span> 這些點，看看能不能經過它們讓距離變短。
我們就來練習看看吧
[Leetcode 1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance](https://leetcode.com/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/description/)

class Solution {
public:
    int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
        vector<vector<int>> dist(n, vector<int>(n, INT_MAX));
        // 自己到自己的距離
        for (int i = 0; i < n; i++) dist[i][i] = ; // TODO
        for (int i = 0; i < edges.size(); i++) {
            int u = edges[i][0], v = edges[i][1], w = edges[i][2];
            dist[u][v] = ; // TODO
            dist[v][u] = ; // TODO
        }
        
        // Floyd–Warshall
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    // 如果使用中繼點的路線比目前的還小，就要更新
                    if () { // TODO
                    }
                }
            }
        }
        
        /*
        現在你已經有了所有的最短路徑矩陣了，只要遍歷全部的起點i，
        計算每個起點在distanceThreshold能達到的城市數量，更新
        最小值就能返回了
        */
        
        int bestCity = -1, bestCnt = INT_MAX;
        
        // TODO
        
        return bestCity;
    }
};

課後練習
[Leetcode 1462. Course Schedule IV](https://leetcode.com/problems/course-schedule-iv/description/?envType=problem-list-v2&envId=9idenloe)

## Bellman-Ford Algorithm
然而Dijkstra不是萬能的，在處理負邊時就會遇到問題，我們來思考以下圖片如果用Dijkstra會怎麼更新，假設從0開始遍歷所有點

Dijkstra(G, w, s):
    # G: graph, w(u,v): edge weight, s: source
    for each vertex v in G.V:
        dist[v] ← ∞
        prev[v] ← NIL
    dist[s] ← 0

    Q ← all vertices in G     # min-priority queue (by dist)

    while Q is not empty:
        u ← Extract-Min(Q)    # vertex with smallest dist
        for each neighbor v of u:
            if dist[v] > dist[u] + w(u, v):
                dist[v] ← dist[u] + w(u, v)
                prev[v] ← u
                Decrease-Key(Q, v, dist[v])

    return dist[], prev[]

首先一開始會將所有點都設為無窮大
| 節點 | 0 | 1 | 2
|-------------|---|---|---
| **Step 0** | 0 | ∞ | ∞

接著Dijkstra更新完這個點的所有邊後，每次都是去遍歷下一個距離最小的點，所以下一個會是從2出發
| 節點 | 0 | 1 | 2
|-------------|---|---|---
| **Step 0** | 0 | 7 | 5

由於2沒有相鄰節點因此不更新
| 節點 | 0 | 1 | 2
|-------------|---|---|---
| **Step 0** | 0 | 7 | 5

而bellman-ford algorithm如下