DAY13 - 最短路径算法(二)

今天写单源最短路径算法

也是直接放一题例题讲解~~

例题&算法

815. 公交路线
题目叙述：
给一个数组，表示公车行经的路径
ex.[[1,2,7],[3,6,7]]
表示第0辆公车路径为1->2->7，第1辆公车路径为3->6->7
给定一个起点，一个终点
ex.source = 1, target = 6
最後返回需要搭乘公车的最少数量

[法一]Disjkstra思路

假设图无负权重
思路：基於贪心思想，从起点找一个离起点最近的节点->这一个边无法再松弛
->用这一个边去对其他边松弛
从初始节点开始向外一层一层的扩展，将路径逐渐松弛
先用一个Kdis数组纪录每个点与初始点k的距离(k到这些点)
选择Kdis中，最小的那一个节点idx(说明这个节点已经比其他节点到初始点的距离都相对小)来进行扩展
则可得

if(Kdis[idx]+adj[idx][j]<Kdis[j])    
    Kdis[idx]+adj[idx][j] = Kdis[j]

((一步步向外扩张))
含有将边松弛的概念，也一层层向外扩张能到达的区域

贪心的思路

选择Kdis中最小的节点(也就是离初始点最近的节点)来操作就是贪心的思路，已经没有其他节点相对该节点离初始点近，就先拿该节点对其他边进行松弛(可以想成其他边都直接连到初始点)，要经过一些节点让路径更好，也就是松弛

class Solution {
public:
    int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {
        if(source == target) {
            return 0;
        }
        int n = routes.size();
        vector<vector<int>> dis(n, vector<int>(n, 1e7));
        unordered_map<int, vector<int>> stop2rt;
        // for(int i=0; i<n; i++) {
        //     dis[i][i] = 0;
        // }
        for(int i=0; i<n; ++i) {
            for (int stop : routes[i]) {
                for(auto j:stop2rt[stop]){
                    dis[i][j] = 1;
                    dis[j][i] = 1;
                }
                stop2rt[stop].push_back(i);
            }
        }
        int res = 1e7;
        for(auto rt:stop2rt[source]){//要遍历所有souce所在的路线
            vector<int> dis_start2rt(n, 1e7);
            vector<int> vis(n, 0);
            dis_start2rt[rt] = 0;
            //dijkstra
            for(int i = 0; i<n; ++i){
                int min_idx = -1, mmin = 1e7;
                for(int j = 0; j<n; ++j){
                    if(!vis[j]&&dis_start2rt[j]<mmin){
                        mmin = dis_start2rt[j];
                        min_idx = j;
                    }
                }
                if(min_idx==-1){
                    break;
                }
                vis[min_idx] = 1;
                for(int k = 0; k<n; ++k){
                    if(!vis[k]){
                        dis_start2rt[k] = min(dis_start2rt[k], mmin+dis[min_idx][k]);
                    }
                }
            }
            for (auto end : stop2rt[target]) {
                res = min(res, dis_start2rt[end]); 
            }
        }
        return res==1e7?-1:res+1;
    }
};

[法二]Bellman-Ford思路

思路：
以边为单位，每个边都尝试对路径松弛，松弛n-1次後(程序码写n次，但其实n-1次就可松弛完毕)为最佳路径~~
如果有一个边叫做u->v，并以一个数组纪录起始点到节点的距离dis_start2rt，那可以做这种访问：

if(dis_start2rt[v]>dis_start2rt[u]+dis[u][v]){
    dis_start2rt[v] = dis_start2rt[u]+dis[u][v];
}

这种演算法还可以处理负权重，方法是如果n-1次松弛後，如果还有边可以松弛，说明有负权重~~

class Solution {
public:
    int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {
        if(source == target) {
            return 0;
        }
        int n = routes.size();
        vector<vector<int>> dis(n, vector<int>(n, 1e7));
        unordered_map<int, vector<int>> stop2rt;
        vector<vector<int>> edges(n);
        for(int i=0; i<n; ++i) {
            for (int stop : routes[i]) {
                for(auto j:stop2rt[stop]){
                    dis[i][j] = 1;
                    dis[j][i] = 1;
                    edges[i].push_back(j);
                    edges[j].push_back(i);
                }
                stop2rt[stop].push_back(i);
            }
        }
        int res = 1e7;
        for(auto rt:stop2rt[source]){//要遍历所有souce所在的路线
            vector<int> dis_start2rt(n, 1e7);
            vector<int> vis(n, 0);
            dis_start2rt[rt] = 0;
            queue<int> q;
            q.push(rt);
            vis[rt] = 1;
            while(!q.empty()){
                int u = q.front();
                q.pop();
                vis[u] = false;
                for(int k = 0; k<edges[u].size(); ++k){
                    int v = edges[u][k];
                    if(dis_start2rt[u]+1<dis_start2rt[v]){
                        dis_start2rt[v] = dis_start2rt[u]+1;
                        if(!vis[v]){
                            q.push(v);
                            vis[v] = true;
                        }
                    }
                }
            }
            for (auto end : stop2rt[target]) {
                res = min(res, dis_start2rt[end]); 
            }
        }
        return res==1e7?-1:res+1;
    }
};

整理一下：

743. 网络延迟时间用这两天讲的方法做一次

#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) {
        return bellman(times, N, K);
    }
    int floyd(vector<vector<int>>& times, int N, int K){
        iMat dis(N+1, vt<int>(N+1, 1e7));
        for(auto edge:times){
            dis[edge[0]][edge[1]] = edge[2];
        }
        for(int i = 0; i<N+1; ++i){dis[i][i] = 0;}
        for(int k = 1; k<N+1; ++k){
            for(int i = 1; i<N+1; ++i){
                for(int j = 1; j<N+1; ++j){
                    dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j]);
                }
            }
        }
        int res = 0;
        for(int i = 1; i<N+1; ++i){
            res = max(res, dis[K][i]);
        }
        return res==1e7?-1:res;
    }
    int dijkstra(vector<vector<int>>& times, int N, int K){
        iMat dis(N+1, vt<int>(N+3, 1e7));
        vt<int> vis(N+1, 0);
        vt<int> K2node(N+1, 1e7);
        K2node[K] = 0;
        for(auto edge:times){
            dis[edge[0]][edge[1]] = edge[2];
        }
        for(int i = 0; i<N; ++i){//进行n次松弛(但其实n-1次就够)
            //先找到距离起点最短，未被访问的节点 -->[K->mmin_idx]
            int mmin_idx = -1;
            int mmin_dis = 1e7;
            for(int j = 1; j<N+1; ++j){
                if(K2node[j]<mmin_dis&&!vis[j]){
                    mmin_dis = K2node[j];
                    mmin_idx = j;
                }
            }
            if(mmin_idx==-1){
                break;
            }
            vis[mmin_idx] = 1;
            //利用这条边对路径松弛
            for(int j = 1; j<N+1; ++j){
                K2node[j] = min(K2node[j], mmin_dis+dis[mmin_idx][j]);
            }
        }
        int res = 0;
        for(int i = 1; i<N+1; ++i){
            res = max(res, K2node[i]);
        }
        return res==1e7?-1:res;
    }
    int bellman(vector<vector<int>>& times, int N, int K){
        iMat dis(N+1, vt<int>(N+3, 1e7));
        vt<int> K2node(N+1, 1e7);
        K2node[K] = 0;
        for(auto edge:times){
            dis[edge[0]][edge[1]] = edge[2];
        }
        for(int i = 0; i<N; ++i){ //松弛N次(其实N-1次就够)
            //以边为单位
            for(auto edge:times){
                int u = edge[0];
                int v = edge[1];
                K2node[v] = min(K2node[v], K2node[u]+edge[2]);
            }
        }
        int res = 0;
        for(int i = 1; i<N+1; ++i){
            res = max(res, K2node[i]);
        }
        return res==1e7?-1:res;
    }
};