参考：
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. 问题分类
- 单源最短路径问题：从某固定源点出发，求其到所有其他顶点的最短路径
- 多源最短路径问题：求任意两顶点间的最短路径。
2. 无权图的单源最短路算法
-
按照递增（非递减）的顺序找出到各个顶点的最短路
顶点是一个一个的收罗进来的，顺序是从v3开始，其实就是BFS
dist[W] = S到W的最短距离；
dist[S] = 0;
path[W] = S到W的路上经过的某顶点；
void Unweighted(Vertex S)
{
Enqueue(S, Q);
while(!IsEmpty(Q)){
V = Dequeue(Q);
for(V 的每个邻接点 W){
if(dist[W] == -1){
dist[W] = dist[V] +1; // W的最短路径是V的最短路径+1
path[W] = V;
Enqueue(W, Q);
}
}
}
}
3. 有权图的单源最短路算法（Dijkstra算法）
不考虑负值圈问题
Dijkstra算法流程：
void Dijkstra(Vertex s){
while(1){
V = 未收录顶点中dist最小者；
if(这样的V不存在)
break;
collected[V] = true;
for(V 的每个邻接点 W){
if(collectd[W] == false){
// 如果W的现在最短距离小于上一节点V+VW之间的距离，那么W的最短距离就被更新！
if(dist[V] + E<V,W> < dist[W]){
dist[W] = dist[V] + E<V,W>;
path[W] = V;
}
}
}
}
}
动图演示：
原点的dist为0，并且与原点相连的节点的dist为权值。
选择V2，V2指向V4（但是V4已经访问了），剩下的是V5（保持V5原来的路径不变）
从V3到V6的距离小于之前的V4到V6的距离
从V7到V6是更短的路径，所以V6的最短距离
4. leetcode 743. Network Delay Time
https://leetcode.com/problems/network-delay-time/
使用优先队列来存储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/
关键在于diff，将diff和对应的坐标放入到优先队列中，按照diff升序排列，每次pop出diff最小的坐标，再遍历上下左右位置，将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;
}
};
