# Floyd–Warshall algorithm

## 7
The recursive formula is

We can use $\Phi$ to reconstruct the shortest paths.

The new version of Floyd–Warshall algorithm is

// D is a array of n n×n matries;
// Φ is a array of n n×n matries;
n = W.rows;
D[0] = W ;
Φ[0] = NIL;
for k = 1 to n do:
    let D[k] be a new n×n matrix;
    let Φ[k] be a new n×n matrix;
    for i = 1 to n do:
        for j = 1 to n do
            if D[k-1][i][k] + D[k-1][k][j] < D[k-1][i][j]: 
                D[k][i][j] = D[k-1][i][k] + D[k-1][k][j]
                Φ[k][i][j] = k
            else:
                D[k][i][j] = D[k-1][i][j]
                Φ[k][i][j] = Φ[k-1][i][j]

PRINT-ALL-PAIRS-SHORTEST-PATH(Φ, i, j)

if i == j then:
    print i;
elif Φ[i][j] == NIL:
    print ”no path from ” i ” to ” j ” exists”.;
else:
    PRINT-ALL-PAIRS-SHORTEST-PATH(Φ, i, Φ[i][j] );

## why the triple for-loop starts with k?

for k in range(1, n+1):
    for i in range(1, n+1):
        for j in range(1, n+1):
            dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])
    

### 好懂的解釋
2022-07-10T17-45
本質是：

for k in 1~N:
    用k試圖插入所有邊  插入居中看看  看會不會更短
    當嘗試完k=kk時  對於任兩點都已經是在可以自由取用1~kk以任意順序建構中途路徑下的最短

定義Func(1~kk):
對於任兩點都已經是在可以自由取用1~kk以任意順序建構中途路徑下的最短

Func(1~kk) 可以輕易的從 Func(1~(kk-1)) 推出來 的dp本質


### 知乎
https://www.zhihu.com/question/30955032?sort=created

1
2

## c++

LC-CN
https://leetcode.cn/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/solution/zui-duan-lu-jing-mo-ban-da-ji-he-cban-fl-gs7u/

### fatest

const int INF = 0x3f3f3f3f;
int dist[n][n];
memset(dist,INF,sizeof(dist));

why 0x3f3f3f3f
https://hackmd.io/Vw-WHs4cRuSv7f8CBWwOSw

class Solution {
public:
    int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
        const int INF = 0x3f3f3f3f;
        int dist[n][n];
        memset(dist,INF,sizeof(dist));
        for(int i=0;i<n;i++)
        dist[i][i]=0;
        for(int i=0;i<edges.size();i++){
            dist[edges[i][0]][edges[i][1]]=edges[i][2];
            dist[edges[i][1]][edges[i][0]]=edges[i][2];
        }
        for(int k=0;k<n;k++){
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
                }
            }
        }
        int id=-1, minCnt=INF;
        for(int i=0;i<n;i++){
            int cnt=0;
            for(int j=0;j<n;j++){
                if(dist[i][j]<=distanceThreshold)
                    cnt++;
            }
            if(cnt<=minCnt){
                minCnt=cnt;
                id=i;
            }
        }
        return id;
    }
};

### vector

vector<vector<int>>distances(n,vector<int>(n,INT_MAX)); //全源最短路径矩阵
^^^^^^^
2D vector 初始值

class Solution {
public:
    void Floyd(vector<vector<int>>& distances, int n){
        for (int k=0; k<n; ++k) {
            for (int i=0; i<n; ++i) {
                for (int j=0; j<n; ++j) {
                    if (distances[i][k]!=INT_MAX && distances[k][j] != INT_MAX && distances[i][k] + distances[k][j] < distances[i][j]) {
                        distances[i][j] = distances[i][k] + distances[k][j];
                    }
                }
            }
        }
    }
    int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
        vector<vector<int>>distances(n,vector<int>(n,INT_MAX)); //全源最短路径矩阵
        for (int i=0; i<n; i++) {
            distances[i][i] = 0; //自身到自身的距离为0
        }
        for (vector<int> edge : edges) {
            int u=edge[0], v=edge[1], w=edge[2];
            distances[u][v]=w;
            distances[v][u]=w;
        }
        Floyd(distances, n);
        int idx = -1, minCount = INT_MAX;
        for (int i=0; i<n; ++i) {
            int count = 0;
            for (int j=0; j<n; ++j) {
                if (distances[i][j]<=distanceThreshold && i!=j) {
                    count++;
                }
            }
            if (count <= minCount) {
                minCount = count;
                idx = i;
            }
        }
        return idx;
    }
};


作者：sui-xin-yuan
链接：https://leetcode.cn/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/solution/zui-duan-lu-jing-mo-ban-da-ji-he-cban-fl-gs7u/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。