DAY12 - 最短路径算法(一)

终於写完基本DFS跟BFS了~~
今天开始进入正题(?
今天讲的是多源最短路径算法

例题&算法

直接用一题例题来解释：
743. 网络延迟时间
题目叙述：
一张有向图，权重代表传递时间(大於0)，给定一个起点，求起点出发，要多久时间才能使所有节点收到讯号??

输入：times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
输出：2
((图与测试资料来自力扣))
这题要求每一个节点与起点的最短路径，并返回最大的那一个，就是最短的时间内所有节点收到讯号的时间~~

[法一]Floyd-Warshall

思路：i->j的路径如果i->k->j比i->j快，那就选择i->k->j。
实现就是遍历所有节点k，找寻是否有i->j可以松弛

for(int k=0; k<n; ++k){
    for(int i=0; i<n; ++i){
        for(int j=0; j<n; ++j){
            dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
        }
    }
}

WHY?

为什麽遍历所有节点k，找寻是否有i->j可以松弛，路径就已经都是最短了??
对於节点k来说，如果这个节点要去对边松弛，那就必须找到一个i->k->j比i->j快(短)，也是这个演算法的思路。当每个k都已经把所有i->j的可能((k节点可能松弛的边))找完了，那这个k节点就不可能再去松弛边了，当所有节点都不可能再对边松弛了，那每个i->j都是最短路径了~~

例题完整程序码

#define vt vector
#define pb push_back
#define iipair pair<int, int>
#define cipair pair<char, int>
#define icpair pair<int, char>
#define ispair pair<int, string>
#define sipair pair<string, int>
#define MOD 1e9+7
#define iMat vector<vector<int>>
#define cMat vector<vector<char>>
#define ll long long
#define mp make_pair
class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int N, int K) {
        vt<vt<int>> adj(N+1, vt<int>(N+1, 6001));
        for(int i = 1; i<=N; ++i){
            adj[i][i] = 0;
        }
        for(int i = 0; i<times.size(); ++i){
            adj[times[i][0]][times[i][1]] = times[i][2];
        }
        for(int k = 1; k<=N; ++k){
            for(int i = 1; i<=N; ++i){
                for(int j = 1; j<=N; ++j){
                    adj[i][j] = min(adj[i][j],adj[i][k]+adj[k][j]);
                }
            }
        }
        int res = 0;
        for(int i = 1; i<=N; ++i){
            if(adj[K][i]==6001) return -1;
            res = max(res, adj[K][i]);
        }
        return res;
    }
};

这是属於多源的最短路径算法，明天讲单源最短路径~~