DAY13 - 最短路徑算法(二) - iT 邦幫忙::一起幫忙解決難題，拯救 IT 人的一天

2021 iThome 鐵人賽

DAY 13

自我挑戰組

算法與數據結構&力扣例題實戰系列第 13 篇

DAY13 - 最短路徑算法(二)

13th鐵人賽

raychang0901

2021-09-13 21:32:06

862 瀏覽

分享至

今天寫單源最短路徑算法

也是直接放一題例題講解~~

例題&算法

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;
    }
};