最短路径问题

最短路径问题

最短路径即给定两个顶点,在一这两个点为起点和终点的路径中,边的权值和最小的路径。

Bellman-Ford 算法

记从起点 s 出发到顶点 i 的最短距离为 d[i],则下述等式成立:

\(d[i]=min\{d[j]+(从j到i的边的权值)|e=(j,i)\in E \}\)

如果给定的图是一个 DAG(无环有向图),则可以按拓扑序给顶点编号,利用这个递推关系计算出 d。但如果有环,则无法以来这样的顺序计算。在这种情况下,记录到顶点 i 的最短路长度为 d[i],并设初值 d[s] = 0, d[i] = INF,在不断使用这条递推关系更新 d 的值,就可以计算出 d,只要途中不存在负圈,这样的操作就是有限的。结束之后的 d 就是所求的最短距离。

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
struct edge {
int from, to, cost;
}

edge es[MAX_E];

int d[MAX_V];
int V, E;

void bellman_ford(int s) {
for (int i = 0; i < V; ++i) {
d[i] = INF;
}
d[s] = 0;

while (1) {
bool update = false;
for (int i = 0; i < E; ++i) {
edge e = es[i];
if (d[e.from] != INF && d[e.to] > d[e.from] + e.cost) {
d[e.to] = d[e.from] + e.cost;
update = true;
}
}
if (!update) {
break;
}
}
}

如果不存在从 s 可达的负圈,那么最短路不会经过同一个顶点两次,即最多通过 \(|V|-1\) 条边,即最多 \(|V|-1\) 次循环,则时间复杂度为 \(O(|V|*|E|)\)

亦可以用此法来检测是否有负圈存在,如果存在从 s 可达的负圈,那么第 |V| 次循环也会更新 d 的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool find_negative_loop() {
memset(d, 0, sizeof(d));

for (int i = 0; i < V; ++i) {
for (int j = 0; j < E; ++j) {
edge e = es[j];
if (d[e.to] > d[e.from] + e.cost) {
d[e.to] = d[e.from] + e.cost;
if (i == V-1)
return true;
}
}
}
return false;
}

Dijkstra 算法

考虑没有负边的情况。在 Bellman-Ford 算法中,若 d[i] 还不是最短距离的话,那么即使进行 d[j] = d[i] + cost(i, j) 的更新,d[j] 也不会变成最短距离。所以做出如下修改:

  • 找到最短距离已经确定的顶点,从它出发更新相邻顶点的最短距离。
  • 此后不需要再关心上一条中的“已经确定的顶点”。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int cost[MAX_V][MAX_V];  // cost[u][v] := e(u,v)的权重,不存在为 INF
int d[MAX_V]; // 顶点 s 出发的最短距离
bool uesd[MAX_V]; // 已经使用过的图
int V; // 顶点数

void dijkstra(int s) {
fill(d, d+V, INF);
fill(used, used+V, false);
d[s] = 0;

while (1) {
int v = -1;
for (int u = 0; u < V; ++u) {
if (!used[u] && (v == -1 || d[u] < d[v]))
v = u;
}

if (v == -1) break;
used[v] = true;
for (int u = 0; u < V; ++u) {
d[u] = min(d[u], d[v]+cost[v][u]);
}
}
}

使用邻接矩阵实现的 Dijkstra 算法的复杂度是 \(O(|V|^2)\),使用邻接表的话,更新最短距离只需要访问每条边一次即可,但复杂度还是 \(O(|V|^2)\)

使用 STL 的 priority_queue,元素共有 \(O(|V|)\) 个,更新和取出值的操作有 \(O(|E|)\) 次,整个算法的时间复杂度为 \(O(|E|*log|V|)\)

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
struct edge {
int to, cost;
}

typedef pair<int ,int> P; // first 是最短距离,second 是顶点编号

int V;
vector <edge> G[MAX_V];
int d[MAX_V];

void dijkstra(int s) {
priority_queue<P, vector<P>, greater<P> > que;
fill(d, d+V, INF);
d[s] = 0;
que.push(P(0, s));

while (!que.empty()) {
P p = que.top();
que.pop();
int v = p.second;
if (d[v] < p.first) continue;
for (int i = 0; i < G[v].size(); ++i) {
edge e = G[v][i];
if (d[e.to] > d[v] + e.cost) {
d[e.to] = d[v] + e.cost;
que.push(P(d[e.to], e.to));
}
}
}
}

在图中存在负边的情况下,Dijkstra 算法无法正确求解。

Floyd-Warshall 算法

求解任意两点间的最短路径,

只使用顶点 0~k 和 i、j 的情况下,记 i 到 j 的最短路径长度为 \(d[k+1][i][j]\)。k = -1 时,认为只使用 i 和 j,所以 \(d[0][i][j] = cost[i][j]\)

只使用 0~k 时,i 到 j 的最短路径分为两种情况,正好经过顶点 k 一次和完全不经过顶点 k。不经过顶点 k,\(d[k][i][j]=d[k-1][i][j]\)。通过点顶点 k 的情况下,\(d[k][i][j]=d[k-1][i][k]+d[k-1][k][j]\)。则 \(d[k][i][j]=min(d[k-1][i][j],d[k-1][i][k]+d[k-1][k][j])\)。这个 DP 可以使用同一个数组,不断进行$ d[i][j]=min(d[i][j],d[i][k]+d[k][j])$ 的更新来实现。

1
2
3
4
5
6
7
8
9
int d[MAX_V][MAX_V];  // d[u][v] := e(u,v)的权值,不存在为 INF, d[i][i] = 0
int V;

void floyd_warshall() {
for (int k = 0; k < V; ++k)
for (int i = 0; i < V; ++i)
for (int j = 0; j < V; ++j)
d[i][j] = min(d[i][j], d[i][k]+d[k][j]);
}
# C++

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×