最短路径算法

七月 03, 2018 4144

较简单的图论算法

最短路算法有很多种，比较著名的有

  • Bellman-Ford
  • SPFA（队列优化版 Bellman-Ford）
  • Dijkstra
  • Floyd（基于DP思想）

其中 Floyd 只适用于多源最短路径，SPFA 和 Bellman-Ford 代码易于理解但是效率低，Dijkstra 效率高但是不适用于图中有负边权的情况

至于其他算法……我见过某个dalao用线段树写最短路

本文只介绍单源最短路径中的 SPFA 和 Dijkstra （ Bellman-Ford 由于速度慢于 SPFA 所以忽略）。

SPFA

SPFA 可以处理图含有负边权的情况，同时又因为它效率较低，所以它更适合处理稀疏图

这里给出数组版代码

代码实现：

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;

const int MAXINT = 2147483647;
const int MAXN = 2500 + 5;
const int MAXM = 6200 + 5;

struct Edge {
  int v, next, w;
}edge[MAXM * 2];

int head[MAXN];
int cnt;
int dis[MAXN];
bool inQueue[MAXN];

inline void addEdge(int u, int v, int w) {
  edge[++cnt].v = v;
  edge[cnt].w = w;
  edge[cnt].next = head[u];
  head[u] = cnt;
}

inline int SPFA(int s, int t, int n) {
  for (int i = 1; i <= n; ++i) dis[i] = MAXINT;
  dis[s] = 0;
  inQueue[s] = true;
  std::queue<int> q;
  q.push(s);
  while (!q.empty()) {
    int v = q.front();
    q.pop();
    inQueue[v] = false;
    for (int e = head[v]; e; e = edge[e].next) {
      if (dis[edge[e].v] > edge[e].w + dis[v]) {
        dis[edge[e].v] = edge[e].w + dis[v];
        if (!inQueue[edge[e].v]) {
            q.push(edge[e].v);
            inQueue[edge[e].v] = true;
        }
      }
    }
  }
  return dis[t];
}

int main(int argc, char const *argv[]) {
  int n, m, s, t;
  /*
    n for the nodes' count
    m for the edges' count
    s for the start node
    t for the end node
  */
  scanf("%d %d %d %d\n", &n, &m, &s, &t);
  for (int i = 0; i < m; ++i) {
    int u, v, w;
    scanf("%d %d %d\n", &u, &v, &w);
    addEdge(u, v, w);
    addEdge(v, u, w);
  }
  printf("%d\n", SPFA(s, t, n));
  return 0;
}

Dijkstra

Dijkstra 不能解决图中有负边权的情况，算法效率较高，适合在不含负边权的稠密/稀疏图中使用

这里还是给出数组写法

代码实现：

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

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
#define mp std::make_pair
using namespace std;

const int MAXN = 1000 + 7;
const int MAXM = 1000000 + 7;
const int INF = 0x7fffffff;

typedef long long int ll;
typedef std::pair<int, int> Pair;

int n, m;

inline int getint() {
  int s = 0, x = 1;
  char ch = getchar();
  while (ch > '9' || ch < '0') {
    if (ch == '-') x = -x;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    s = s * 10 + ch - '0';
    ch = getchar();
  }
  return s * x;
}

struct Node {
  int v, next, w;
}edge[MAXM];

int num = 0, head[MAXN];

bool inQueue[MAXN];

ll dis[MAXN]; // dis[i] --> the distance from i to n

inline void addEdge(int u, int v, int w) {
  edge[++num].v = v;
  edge[num].w = w;
  edge[num].next = head[u];
  head[u] = num;
}

inline int dijkstra(int s, int t, int n) { // s for start, t for end, n for the count of the nodes
  for (int i = 1; i <= n; ++i) dis[i] = INF;
  std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int> >, std::greater<std::pair<int, int> > > q;
  inQueue[s] = true;
  dis[1] = 0;
  q.push(mp(s,0)); 
  while (!q.empty()) {
    int v = q.top().first;
    int value = q.top().second;
    q.pop();
    for (int e = head[v]; e; e = edge[e].next) {
      if (dis[edge[e].v] > value + edge[e].w) {
        dis[edge[e].v] = (value + edge[e].w) ; 
        q.push(mp(edge[e].v, dis[edge[e].v]));
      }
    }
  }
  return dis[t];
}

int main(int argc, char const *argv[]) {
  n = getint(), m = getint();
  for (int i = 0; i < m; ++i) {
    int x, y, z;
    x = getint(), y = getint(), z = getint();
    addEdge(x, y, z);
  }
  printf("%d\n", dijkstra(1, n, n)); 
  return 0;
}