參考：
https://www.youtube.com/watch?v=ypE6a1Kk-6Q&list=PLe68gYG2zUeVNPEr9XPqeejGHihtQD6tl&index=31&t=0s
https://leetcode.com/discuss/general-discussion/655708/graph-for-beginners-problems-pattern-sample-solutions/562734

1. 問題分類

• 單源最短路徑問題：從某固定源點(diǎn)出發(fā)，求其到所有其他頂點(diǎn)的最短路徑
• 多源最短路徑問題：求任意兩頂點(diǎn)間的最短路徑。

2. 無權(quán)圖的單源最短路算法

• 按照遞增（非遞減）的順序找出到各個(gè)頂點(diǎn)的最短路
  頂點(diǎn)是一個(gè)一個(gè)的收羅進(jìn)來的，順序是從v3開始，其實(shí)就是BFS

  
  

dist[W] = S到W的最短距離；
dist[S] = 0;
path[W] = S到W的路上經(jīng)過的某頂點(diǎn)；
void Unweighted(Vertex S)
{
    Enqueue(S, Q);
    while(!IsEmpty(Q)){
        V = Dequeue(Q);
        for(V 的每個(gè)鄰接點(diǎn) W){
            if(dist[W] == -1){
                dist[W] = dist[V] +1; // W的最短路徑是V的最短路徑+1
                path[W] = V; 
                Enqueue(W, Q);
            }
        }
    }
}

3. 有權(quán)圖的單源最短路算法（Dijkstra算法）

不考慮負(fù)值圈問題

Dijkstra算法流程：

void Dijkstra(Vertex s){
    while(1){
        V = 未收錄頂點(diǎn)中dist最小者；
        if(這樣的V不存在)
            break;
        collected[V] = true;
        for(V 的每個(gè)鄰接點(diǎn) W){
            if(collectd[W] == false){
                // 如果W的現(xiàn)在最短距離小于上一節(jié)點(diǎn)V+VW之間的距離，那么W的最短距離就被更新！
                if(dist[V] + E<V,W> < dist[W]){
                    dist[W] = dist[V] + E<V,W>;
                    path[W] = V;
                }
            }
        }
    }
}

動(dòng)圖演示：

原點(diǎn)的dist為0，并且與原點(diǎn)相連的節(jié)點(diǎn)的dist為權(quán)值。

選擇V2，V2指向V4（但是V4已經(jīng)訪問了），剩下的是V5（保持V5原來的路徑不變）

從V3到V6的距離小于之前的V4到V6的距離

4. leetcode 743. Network Delay Time

https://leetcode.com/problems/network-delay-time/

使用優(yōu)先隊(duì)列來存儲(chǔ)pair<int, int> (dist[V], V)，按照距離來升序；

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int N, int K) {
        vector<vector<pair<int, int>> > graph(N+1);
        for(int i=0; i<times.size(); ++i){
            pair<int, int> p(times[i][1], times[i][2]);
            int idx = times[i][0];
            graph[idx].push_back(p);
        }
        
        vector<int> dist(N+1, INT_MAX);
        dist[K] = 0;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int,int>> > pq;
        
        pq.push(make_pair(0, K));
        
        while(!pq.empty()){
            pair<int, int> p;
            p = pq.top();
            pq.pop();
            
            int u = p.second;
            for(auto it = graph[u].begin(); it != graph[u].end(); ++it){
                int v = it->first;
                int w = it->second;
                
                if(dist[v] > dist[u] + w){
                    dist[v] = dist[u] + w;
                    pq.push(make_pair(dist[v], v));
                }
            }
        }
        
        int res = 0;
        
        for(int i=1; i<N+1; ++i){
            res = max(res, dist[i]);
        }
        
        return res == INT_MAX ? -1 : res;
    }
};

5. Leetcode 1631. Path With Minimum Effort

https://leetcode.com/problems/path-with-minimum-effort/
關(guān)鍵在于diff，將diff和對應(yīng)的坐標(biāo)放入到優(yōu)先隊(duì)列中，按照diff升序排列，每次pop出diff最小的坐標(biāo)，再遍歷上下左右位置，將effort輸入。

class Solution {
public:
    typedef pair<int, pair<int,int> > PIP;
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    
    int minimumEffortPath(vector<vector<int>>& heights) {
        int rows = heights.size(), cols = heights[0].size();
        vector<vector<int>> visited(rows, vector<int>(cols, 0));
        visited[0][0] = 1;
        
        priority_queue<PIP, vector<PIP>, greater<PIP>> pq;
        pq.push(make_pair(0, make_pair(0,0)));
        
        int diff = 0;
        
        while(!pq.empty()){
            PIP h = pq.top();
            pq.pop();
            
            int x = h.second.first;
            int y = h.second.second;
            visited[x][y] = 1;
            diff = max(diff, h.first);
            cout << x << " " << y << " " << diff << endl; 
            if(x == rows-1 && y == cols-1)
                return diff;
            
            for(int i=0; i<4; ++i){
                int nx = x + dx[i];
                int ny = y + dy[i];
                if(nx >= 0 && nx < rows && ny >= 0 && ny < cols && visited[nx][ny] != 1) {
                        pq.push(make_pair(abs(heights[nx][ny] - heights[x][y]), make_pair(nx, ny)));
                }
            }
        }
        return 0;
    }
        
};