圖論最短路徑

algo c++

學習算法

1.如何建立圖

  1. 鄰接矩陣
  • 使用:稠密圖
  • O:n^2
  • 實現:2D數組
  1. 鄰鏈表
  • 使用:稀疏圖
  • O:e(e代表邊數量)
  • 實現:數組模擬鏈表,vector

圖分類鄰接矩陣

  1. 無權圖
  • 新增g[y][x]=1為無向圖
int main(){
  int n,m;cin >>n>>m;
  while(m--){
    int x,y;cin>>x>>y;
    g[x][y]=1;
  }
}
  1. 帶權圖
  • 新增g[y][x]=w為無向圖
int main(){
  int n,m;cin >>n>>m;
  while(m--){
    int x,y,w;cin>>x>>y>>w;
    g[x][y]=w;
  }
}

圖分類鄰接表

鏈式前向星

  • 使用前向星實現
    • 雙向:add(y,x,w)
  • 使用h當作頭指針數組，將會紀錄上一個指針的下標
    • 初始化:h[i]=i紀錄每一個點的頭指針
    • 過程:讓新的邊後繼指針指向e[h[i]]後把h[i]換成當前的下標
struct edge
{
 int v,w,nxt;
}e[1001];
int h[1001];
inline void add(int a,int b,int c)
{
    e[++p].nxt = h[a];
    h[a] = p;
    e[p].v = b;
    e[p].w = c;
}
int main()
{
 cin>>n>>m;
 while(m--)
 {
  int x,y,w;
  cin>>x>>y>>w;
  add(x,y,w);
 }
 return 0;
}
  • 遍歷
int cur = start;
for(int i = head[cur];i != 0; i = edge[i].next)

詳解鏈式前向星

  • 基本結構體存node
struct Edge {
  int next;
  int to;
}edge[1000000];
  • 儲存起點
int head[20000];
  • 指針
int cnt;

逐步分析

  • 輸入1,2代表1連向2
cnt ++; //當作結構體下標
head[1] = cnt;
edge[cnt].to = 2; //節點1的兒子是2
  • 輸入1,3但表1連向3
cnt ++;
head[1] = cnt;
edge[cnt].to = 3;
  • 此時會發現如果這樣寫,原本的2就被擠掉,因此要改成
cnt ++;
edge[cnt].to = 3; //1連向3
edge[cnt].next = head[1]; //3的兄弟是2
head[1] = cnt;//更新head

Vector

  • 使用vector
  • 雙向:v[y].push_back(edge(x,w));
struct edge
{
    int node,weight;
    edge(int node_,int weight_):
        node(node_),weight(weight_){}
};
vector<edge> v[1001];
int n,m;
int main()
{
   cin>>n>>m;
   while(m--)
   {
    int x,y,w;
    cin>>x>>y>>w;
    v[x].push_back(edge(y,w));
   }
   return 0;
}

2.DFS

  • 使用遞迴和回朔來便利每一條邊直到滿足條件,是一種單源最短路
  • 優點: 好寫
  • 缺點: 容易TLE
void dfs(int x,int step)
{
 dis[x]=step;//更新數據
 for(int i=1;i<=n;++i)
     if(g[x][i])
        {
         g[x][i]=0;
          dfs(i,step+1);
          g[x][i]=1; //回朔回原來狀態
         }
}

3.BFS

  • 單源最短路徑算法
  • bfs會需要queue來做輔助,將每次從queue中取一點,如果訪問過就pop否則標記,接著便利每一點值到終點
  • BestCase:起點和中點一樣O(1)
  • WorstCase:目標點最後被搜尋到O(n+e)
  • 鄰接表bfs模板
queue<pair<int,int>> q; //前面是點編號,後面是step數
q.push(make_pair(s,0)); //起點
while(!q.empty()){
  int t = q.front().first;
  int step = q.front().second;
  if(t==f) //終點直接為起點
  {
    cout << step << endl;
    return;
  }
  if(vis[t]) //標記過的不再走一遍
    continue;
  vis[k]=1; //標記
  // 迭代器遍歷所有與當前點相鄰的點vector是鄰接表
  for(vector<int>::iterator it=v[k].begin();it!=v[k];++it){
    q.push(make_pair(*it,step+1));
  }
}

2D BFS

  • 需要釐清的是平面和直角坐標系不同,2D前面的為y後面為x,下加上減，右加左減
cosnt int d[4][2]={
  {1,0},
  {-1,0},
  {0,1},
  {0,-1}
};
// ...
while(!q.empty()){
  //...
  for(int i=0;i<4;i++){
    int nx = x+d[i][0];
    int ny = x+d[i][1];
    if(//判斷越界)
    q.push(make_pair(nx,ny));
  }
}

Leetcode 407

  • 先儲存邊界的高度和位址,從外往裏計算
  • 當前block的存水量為minihigh - 當前block高度,小於0的話當作0
  • 每一次往隊列丟的都是minihigh或當前block高度的較大者
#include <bits/stdc++.h>
using namespace std;
 
class Solution {
public:
    int trapRainWater(vector<vector<int>>& heightMap) {
        int n = heightMap.size();
        int m = heightMap[0].size();
        priority_queue<tuple<int,int,int>,vector<tuple<int,int,int>>,greater<>> pq;
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                if(i == 0 || i== n-1 || j == 0 || j == m-1){
                    pq.push({heightMap[i][j],i,j});
                    heightMap[i][j] = -1;
                }
 
        vector<pair<int, int>> dict = {
            {0, -1},
            {0, 1},
            {-1, 0},
            {1, 0}};
        
        int ans = 0;
        while(!pq.empty()){
            auto [minhigh,x,y] = pq.top();
            pq.pop();
            for(auto [dx,dy] : dict){
                int nx = x + dx;
                int ny = y + dy;
                if(nx >= 0 && nx < n && ny >= 0 && ny < m && heightMap[nx][ny] >= 0){
                    ans += max(minhigh-heightMap[nx][ny],0);
                    pq.push({max(minhigh,heightMap[nx][ny]),nx,ny});
                    heightMap[nx][ny] = -1;
                }
            }
        }
        return ans;
    }
};

01 BFS

  • 適合在邊權值為0or1時使用,O(E+VlogV)比Dijkstra有效率
  • process: we only put a vertex in the queue if it has been relaxed by a previous vertex (distance is reduced by travelling on this edge)and we also keep the queue sorted by distance from source at every point of time
  • for edge 0 means they lie on the same level, 1 means they lie on the below
  • our queue contains elements of level L[u] or L[u] + 1. And we also know that for an edge (u,v) , L[v] is either L[u] or L[u] + 1
  • Thus , if the vertex "v" is relaxed and has the same level ,we can push it to the front of our queue and if it has the very next level ,we can push it to the end of the queue

implement

  • use STL deque to implement
  1. Remove top element To get vertex for BFS
  2. Insert At the beginning To push a vertex with same level
  3. Insert At the ended To push a vertex on next level
for all v in vertices:
 dist[v] = inf
dist[source] = 0;
deque d
d.push_front(source)
while d.empty() == false:
 vertex = get front element and pop as in BFS.
 for all edges e of form (vertex , u):
  if travelling e relaxes distance to u:
   relax dist[u]
   if e.weight = 1:
    d.push_back(u)
   else:
    d.push_front(u)

Leetcode 2290

  • 將障礙物當成1,空格當成0可以推導出權只有0或1,使用01BFS會比Dijkstra快
  • 找出從頭到尾的最短路徑即可
#include <climits>
#include <deque>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
  int minimumObstacles(vector<vector<int>> &grid) {
    int r = grid.size();
    int c = grid[0].size();
    deque<pair<int, int>> dq{{0, 0}};
    vector<vector<int>> dist(r, vector<int>(c, INT_MAX));
    dist[0][0] = 0;
    vector<int> dx = {1, -1, 0, 0};
    vector<int> dy = {0, 0, 1, -1};
    while (!dq.empty()) {
      auto [x, y] = dq.front();
      dq.pop_front();
      for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx >= 0 && nx < r && ny >= 0 && ny < c) {
          int d = dist[x][y] + grid[nx][ny];
          if (d < dist[nx][ny]) {
            dist[nx][ny] = d;
            grid[nx][ny] == 0 ? dq.push_front({nx, ny})
                              : dq.push_back({nx, ny});
          }
        }
      }
    }
    return dist[r - 1][c - 1];
  }
};

Leetcode 1368

  • 同一row都當作0,非同一row都皆為1
class Solution {
public:
    int minCost(vector<vector<int>>& grid) {
        int r = grid.size();
        int c = grid[0].size();
 
        vector<vector<int>> dict = {
            {1,0},
            {-1,0},
            {0,1},
            {0,-1}
        };
        deque<pair<int,int>> dq{{0,0}};
        vector<vector<int>> dist(r,vector<int>(c,INT_MAX));
        dist[0][0] = 0;
 
        while(!dq.empty()){
            auto [x,y] = dq.front();
            dq.pop_front();
            for(int i=0;i<4;i++){
                int nx = x + dict[i][1];
                int ny = y + dict[i][0];
                if(nx >= 0 && nx < r && ny >=0 && ny < c){
                    int d = (i+1 == grid[x][y]) ? 0 : 1;
                    if(d + dist[x][y] < dist[nx][ny]) {
                        dist[nx][ny] = d + dist[x][y];
                        d == 0 ? dq.push_front({nx,ny})
                               : dq.push_back({nx,ny});
                    }
                } 
            }
        }
        return dist[r-1][c-1];
    }
};

4.Floyd

  • 為多源最短路,可以處理負權邊但沒辦法處理負環,本質上就是暴力解
  • 使用鄰接表存最短路徑dis[i][j]表示i到j的最短路徑,外層枚舉中間點,中間枚舉起點,內層枚舉終點
  • 當三個點互不相同的時候進行鬆弛操作,如果中間點之後的路程比原路更短,更新距離,接著更新中間點進行n次得到答案
  • 時間複雜度因為三層for為O(n^3)
  • dis要初始化成正無窮,否則鬆弛會失效

模板

for(int k=1;k<=n;k++) //枚舉中間點
  for(int i=1;i<=n;i++) //枚舉起點
    if(i != k)
      for(int j=1;j<=n;j++)//枚舉終點
        if(i!=j && k!=j)
          dis[i][j] = min(dis[i][j],dis[i][k]+dis[k][j]); //狀態轉移方程,也就是鬆弛操作

P1119

  • 模板題
#include <cstring>
#include <iostream>
using namespace std;
 
int n, m;
int t[201];
int dis[201][201];
int q;
 
const int INF = 0x3f3f3f;
 
int main() {
  cin >> n >> m;
  memset(dis, INF, sizeof(dis));
  int inf = dis[0][0];
  for (int i = 1; i <= n; i++)
    dis[i][i] = 0;
  for (int i = 1; i <= n; i++)
    cin >> t[i];
  for (int i = 1; i <= m; i++) {
    int x, y, w;
    cin >> x >> y >> w;
    dis[x + 1][y + 1] = dis[y + 1][x + 1] = w;
  }
 
  cin >> q;
  int k = 1;
  while (q--) {
    int x, y, w;
    cin >> x >> y >> w;
    for (; t[k] <= w && k <= n; k++)
      for (int i = 1; i <= n; i++)
        if (i != k)
          for (int j = 1; j <= n; j++)
            if (i != j && j != k)
              dis[i][j] = dis[j][i] = min(dis[i][j], dis[i][k] + dis[k][j]);
    if (t[x + 1] > w || t[y + 1] > w)
      cout << "-1" << endl;
    else {
      if (dis[x + 1][y + 1] < inf)
        cout << dis[x + 1][y + 1] << endl;
      else
        cout << "-1" << endl;
    }
  }
}

P1359

#include <bits/stdc++.h>
using namespace std;
 
int a[201][201];
 
int main(){
    int n;cin >> n;
    memset(a,0x3f,sizeof(a));
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++){
            if(i == j) a[i][j] = 0;
            else {
                int v = 0;cin >> v;
                a[i][j] = v;
            }   
        }
    }
 
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                a[i][j] = min(a[i][j],a[i][k]+a[k][j]);
            }
        }
    }
    cout << a[1][n] << endl;
}

5. Dijkstra

  • 計算非負權重圖形可以使用來找最短路徑
  1. 選擇源點到哪個點的距離最近且未被訪問
  2. 標記該最近點
  3. 更新訪問節點到源點的距離

模板

void dijkstra(){
  memset(dis,127/3,sizeof(dis));
  v[1] = 1;
  dis[1] = 0;
  for(int i=1;i<=n;i++){
    int k = 0;
    for(int j=1;j<=n;j++) //找出距離最近的點
      if(!v[j] && (k == 0 || dis[j] < dis[k]))
        k = j;
    // 紀錄點
    v[k] = 1;
    for(int j=1;j<=n;j++)
      if(!v[j] && dis[k]+a[k][j] < dis[j])
        dis[j] = dis[k]+a[k][j]; //鬆弛
  }
}
  • 從模板可以發現為O(n^2)後續會介紹Dijkstra的優化

P1359

  • 使用鏈式前向星儲存
struct Edge {
  int node; //連向的node
  int val; // 當前邊權重
  int next; //更新node
}edge[100000]
 
int head[20000];
  • 鬆弛
if(!vis[edge[i].node] && dis[edge[i].node] > dis[cur]+edge[i].val)
                dis[edge[i].node] = dis[cur]+edge[i].val;
  • 完整代碼
#include <bits/stdc++.h>
using namespace std;
 
#define ten 1000000
#define two 20000
 
struct Edge {
    int node;
    int val;
    int next;
}edge[ten];
 
int head[two];
int cnt = 0;
 
void add(int a,int b,int c){
    cnt++;
    edge[cnt].node = b;
    edge[cnt].val = c;
    edge[cnt].next = head[a];
    head[a] = cnt;
}
 
int main(){
    bool vis[two] = {0};
    long long dis[two];
    int n,m,s;cin >> n >> m >> s;
    for(int i=1;i<=n;i++) dis[i] = INT_MAX;
    for(int i=0;i<m;i++){
        int u,v,w;
        cin >>u>>v>>w;
        add(u,v,w);
    }
    dis[s] = 0;
    int cur = s;
    long long mindist;
    while(!vis[cur]){
        vis[cur] = true;
        for(int i=head[cur];i != 0;i=edge[i].next){
            if(!vis[edge[i].node] && dis[edge[i].node] > dis[cur]+edge[i].val)
                dis[edge[i].node] = dis[cur]+edge[i].val;
        }
        mindist = INT_MAX;
        for(int i=1;i<=n;i++){
            if(!vis[i] && mindist > dis[i]){
                mindist = dis[i];
                cur = i;
            }
        }
    }
    for(int i=1;i<=n;i++)
        printf("%lld ",dis[i]);
    cout << endl;
}