红魔咖啡馆

头发越掉越多，头发越掉越少

0%

【图论】最短路径

发表于 更新于 分类于 ，
本文字数： 6.6k 阅读时长 ≈ 12 分钟
介绍了最短路的几种算法的原理与实现

最短路径

Dijkstra

思路

基本步骤：

  • 选定一个点，满足：
    • 未被选过
    • 距离最短
  • 对这个点的所有邻接点尝试松弛(如下图，从a到c权值为5，而从a到b到c权值为3，我们用后者代替前者成为最短路，此之为成功的松弛)

从a开始，依次寻找下一个节点，使得从a到当前节点的路径最短，直到找到结尾

遍历时，我们依次寻找a到当前节点的最短路径以及最近节点

当我们得到了最短权值，我们可以反推回a从而获取最短路径

用矩阵表示如下

代码

邻接矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
vector<vector<int>> G;
vector<int> path;
vector<int> dijkstra(vector<vector<int>> &G, int s){
  int n = G.size();
  vector<int> dis(n,0x3f3f3f3f);
  vector<int> vis(n,0);
  dis[s] = 0;
  for (int i = 0;i<n-1;i++){
    int node = -1;
    for (int j = 0;j<n;j++){
      if (!vis[j]&&(node==-1||dis[j]<dis[node])){
        node = j;
      }
    }
    for (int j = 0;j<n;j++){
      if (dis[node]+G[node][j]<dis[j]){
        dis[j] = dis[node]+G[node][j];
        path[j] = node;
      }
    }
    vis[node] = true;
  }
  return dis;

}
// 路径获取
void get_path(int x, vector<int> &P){
  if (!x){
    P.push_back(0);
    return ;
  }
  // 若该节点前有节点，则先获取前面节点的内容
  if (path[x]!=-1)get_path(path[x], P);
  P.push_back(x);

}
void solve() {
  int n, m, s;
  cin >> n >> m >> s;
  path = vector<int>(n,-1);
  G = vector<vector<int>> (n,vector<int>(n, 0x3f3f3f3f));
  for (int i = 0;i<m;i++){
    int u,v,w;
    cin >> u >> v >> w;
    u--,v--;
    if (!G[u][v])G[u][v]=w;
    else G[u][v]=min(G[u][v],w);
  }
  auto dis = dijkstra(G, s-1);
  for (auto it: dis)cout << it <<' ';
  
}
int main()
{
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int tomorin=1;
  //cin >> tomorin;
  while (tomorin--) solve();
  return 0;
}

最小堆优化

上述朴素算法的问题：

  • 寻找最小点时，通过遍历n个点来获得最小点
  • 对该点邻接点进行松弛时，我们也是通过遍历去寻找邻接点

对于以上问题，我们可以选用小根堆与邻接表直接获取，可以实现代码的优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
vector<int> edge, weight, Next, head;
int n, m, s;
int idx=0;
vector<int> dijkstra(int s){
    vector<int> dis(n,0x3f3f3f3f);
    vector<int> vis(n,0);
    dis[s]=0;
    // 最小堆，first记录dis， second记录node
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> mh;
    mh.push({dis[s],0});
    while(!mh.empty()){
        int node = mh.top().second;
        mh.pop();
        if(vis[node]) continue;
        for(int i = head[node];~i;i=Next[i]){
            if (dis[edge[i]]>dis[node]+weight[i]){
                dis[edge[i]]=dis[node]+weight[i];
                mh.push({dis[edge[i]],edge[i]});
            }
        }
        vis[node]=true;
    }
    return dis;
}
void add_edge(int u, int v, int w){
    edge[idx] = v;
    weight[idx] = w;
    Next[idx] = head[u];
    head[u]=idx++;
}
int main(){
    cin >> n >> m >> s;
    head = vector<int> (n,-1);
    edge = weight = Next = vector<int> (m,0);
    while(m--){
        int u, v, w;
        cin >> u >> v >> w;
        u--,v--;
        add_edge(u,v,w);
    }
    auto dis = dijkstra(s-1);
    for(auto it:dis) cout << it <<' ';
    return 0;

}

Floyd

思路

Floyd与Dijkstra都是看节点间的值，但是前者看的是每两点间最短距离

Dis数组，记录两点距离：

这里矩阵中每个位置表示两点间的距离，而D上的下标表示从何处中转得到的距离（-1表示不进行中转）

如此时\(D^0\)为从\(v_0\)进行中转得到的两点间距离，且距离可以根据红色式子表示，即经过中转点后的距离与上一步已有距离的最小值

Path数组，记录经过点(最短路径)

Path数组记录了两点间经过的中转点是哪个点，若为直达则记录终点，如\(P^{-1}\)指的是没有中转，其中记录的都是终点，\(P^0\)指经过\(v_0\)中转，故\(v_1\to v_2\)对应的值为0，表示中转点为\(v_0\)

通过path数组推出最短路径：

如寻找\(v_1\)到\(v_0\)的最短路径：找到第一行第零列的点对应的点，该点即为到达终点的前一个点；再找到该点对应的点，即为到达该点的前一个点，直到推到起点

代码

(邻接矩阵)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <bits/stdc++.h>
using namespace std;
const int N = 100;
const int M = 200;
const int MAX = 0x10000;
typedef char VertexType ;
typedef int EdgeType;

struct mat_grph{
  VertexType vertex[N];
  EdgeType arc[N][N];
  int vertex_num;
  int edge_num;
};

void createGraph(mat_grph* G){
  
  G->vertex_num = 9;
  G->edge_num = 15; 
  for (int i = 0; i<G->vertex_num;i++){
    G->vertex[i] = i;
  }
  for (int i = 0;i<G->vertex_num;i++){
    for (int j = 0;j<G->vertex_num;j++){
      if(i==j) G->arc[i][j] = 0;
      else G->arc[i][j]=MAX;
    }
  }
  G->arc[0][1] = 1;
  G->arc[0][2] = 5;
  G->arc[1][2] = 3;
  G->arc[1][3] = 7;
  G->arc[1][4] = 5;
  G->arc[2][4] = 1;
  G->arc[2][5] = 7;
  G->arc[3][4] = 2;
  G->arc[3][6] = 3;
  G->arc[4][5] = 3;
  G->arc[4][6] = 6;
  G->arc[4][7] = 9;
  G->arc[5][7] = 5;
  G->arc[6][7] = 2;
  G->arc[6][8] = 7;
  G->arc[7][8] = 4;
  for (int i = 0;i<G->vertex_num;i++){
    for (int j = 0; j<G->vertex_num;j++){
      G->arc[j][i] =  G->arc[i][j];
    }
  }
}
void floyd(mat_grph G){
  int path[N][N];
  int dis[N][N];
  for (int i = 0;i<G.vertex_num;i++){
    for (int j = 0;j<G.vertex_num;j++){
      dis[i][j] = G.arc[i][j]; // 最初的dis数组
      path[i][j] = j; // 最初的path数组
    }
  }
  for (int i = 0;i<G.vertex_num;i++){
    for (int j = 0;j<G.vertex_num;j++){
      for (int k = 0;k<G.vertex_num;k++){
        if(dis[j][k]>dis[j][i]+dis[i][k]){
          dis[j][k] = dis[j][i]+dis[i][k];
          path[j][k] = path[j][i];
        }
      }
    }
  }
  int k;
  for (int i = 0; i<G.vertex_num;i++){
    for (int j = i+1; j<G.vertex_num;j++){
      printf("v%d->v%d weight:%d ", i, j, dis[i][j]);
      k = path[i][j];
      printf("path:v%d", i);
      while(k!=j){
        printf("->v%d", k);
        k = path[k][j];
      }
      printf("->v%d\n", j);
    }
    printf("\n");
  }
}

int main(){
  mat_grph G;
  createGraph(&G);
  floyd(G);
  return 0;
}

A*

解决问题：给定原点与目标点，最少代价路径是什么

特点：与dijkstra不同，A*算法考虑从原点到当前点的距离+当前点到目标点距离的估计距离，最后排大小

如该方格，起点为G，终点为U

从G到U预估走4步，G到G走0步，故参与排序为0+4，放入小根堆，并将原点到当前点距离放入distance表中

G 4取出，G到L,N,H,F为1，放入distance，并分别算出到U的预估距离，相加放入小根堆

在取出堆顶并重复上述操作

dij可以看作A*每次预估距离都为0，是一个特例

预估函数

预估函数是一种吸引力，合适的预估函数（越接近真实距离）会大大提升速度

要求：预估距离小于等于到终点的真实距离

预估距离经常选择：曼哈顿距离、欧氏距离、对角线距离等

如：若允许走斜线，曼哈顿距离就不能保证正确性了，此时可以取行与行、列与列间差值最大值

板子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
vector<int> edge, weight, Next, head;
int n, m, s, t;
int idx=0;
vector<int> idis; // 根据需求填入计算合适理想距离
vector<int> astar(int s){
    vector<int> dis(n,0x3f3f3f3f);
    vector<int> vis(n,0);
    dis[s]=0;
    // 最小堆，first记录dis， second记录node
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> mh;
    mh.push({dis[s]+idis[s],s});
    while(!mh.empty()){
        int node = mh.top().second;
        mh.pop();
        if(vis[node]) continue; 
        if (s==t) return dis;
        for(int i = head[node];~i;i=Next[i]){
            if (dis[edge[i]]>dis[node]+weight[i]){
                dis[edge[i]]=dis[node]+weight[i];
                mh.push({dis[edge[i]]+idis[edge[i]],edge[i]});
            }
        }
        vis[node]=true;
    }
    return dis;
}
void add_edge(int u, int v, int w){
    edge[idx] = v;
    weight[idx] = w;
    Next[idx] = head[u];
    head[u]=idx++;
}
int main(){
    cin >> n >> m >> s >> t;
    head = vector<int> (n,-1);
    edge = weight = Next = vector<int> (m,0);
    idis = vector<int> (n,0);

    while(m--){
        int u, v, w;
        cin >> u >> v >> w;
        u--,v--;
        add_edge(u,v,w);
    }
    auto dis = astar(s-1);
    for(auto it:dis) cout << it <<' ';
    // if (it==0x3f3f3f3f) cout <<2147483647<<' ';
    // else cout << it <<' ';
    return 0;

}