# Leetcode刷題學習筆記 -- Dijkstra algorithm
## Introduction
參考leetocde explort中的[dijkstra](https://leetcode.com/explore/learn/card/graph/622/single-source-shortest-path-algorithm/3862/)
**==目的: 找出graph中每個點到start point的最短路徑。==**

目標是從起點到終點，找到最短的路徑。
1. 使用priority_queue，來排序每次都會拿到最短的路徑。
2. 使用BFS

### [743. Network Delay Time](https://leetcode.com/problems/network-delay-time/)

class Solution {
    map<int, vector<pair<int, int>>> m;
    void dijstra(vector<int>& arr, int k) {
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        // 把weight放在pair第一個，是因為要讓priority_queue來排序。
        // 其中weight是start point到此點的距離。
        // 因為dijkstra最後是算出start point到每個點的最短距離
        pq.push(make_pair(0, k));
        arr[k] = 0;
        while(!pq.empty()) {
            int cur  = pq.top().second;
            int curt = pq.top().first;
            pq.pop();
            //if(curt > arr[cur]) continue;
            for(auto& adj : m[cur]) {
                if(arr[cur] + adj.first < arr[adj.second]) { // 從cur走到adj時間比原本還小
                    arr[adj.second] = arr[cur] + adj.first;
                    pq.push(make_pair(arr[adj.second], adj.second));
                }
            }
        }
    }
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        for(auto& time : times)
            m[time[0]].push_back(make_pair(time[2], time[1]));
        
        vector<int> arr(n + 1, INT_MAX);    // index從1開始方便記錄
        dijstra(arr, k);
        
        auto it = max_element(arr.begin() + 1, arr.end()); // 找max必須跳過第一個
        return *it == INT_MAX ? -1 : *it;
    }
};

### [1631. Path With Minimum Effort](https://leetcode.com/problems/path-with-minimum-effort/)
定義：一個路徑(從起點到終點)的effort為從起點到終點，所經過的最大高度差。
找出最小的effor。

1. 使用priority_queue(min-heap) 保證每次取到都是最小的effort
2. 使用一個vector<vector<int>> dist紀錄到達此點的最小effort。
3. 使用BFS來從起點擴散到終點

class Solution {
    vector<vector<int>> dirs = {
                {-1,0},
        {0,-1},         {0,1},
                {1, 0}
    };
    
public:
    int minimumEffortPath(vector<vector<int>>& heights) {
        using pipii = pair<int, pair<int, int>>; // effort, y, x
        priority_queue<pipii, vector<pipii>, greater<pipii>> pq; // min-heap 每次都拿最小的effort路徑來更新
        pq.push({0, {0, 0}});
        
        int row = heights.size();
        int col = heights[0].size();
        vector<vector<int>> dist(row, vector<int>(col, INT_MAX));
        // 原點不需要effort
        dist[0][0] = 0;
        
        while(!pq.empty()) {
            auto p = pq.top(); pq.pop();
            int effort = p.first;
            int y = p.second.first;
            int x = p.second.second;
            // 已經有比這個路徑過來還要輕鬆的路
            if(dist[y][x] < effort) continue;
            if(y == row - 1 && x == col - 1) return effort;
            for(auto& d : dirs) {
                int nexty = d[0] + y;
                int nextx = d[1] + x;
                if(nexty < 0 || nextx < 0 || nexty == row || nextx == col) continue;
                int neweffort = abs(heights[y][x] - heights[nexty][nextx]);
                neweffort = max(neweffort, effort); // 從{y, x} 到{nexty, nextx} 的最大effort
                if(neweffort >= dist[nexty][nextx]) continue;
                dist[nexty][nextx] = neweffort;
                pq.push({neweffort, {nexty, nextx}});
            }
        }
        
        // never reach
        return 0;
    }
};

###### tags: `leetcode` `刷題`