活跃农民
- 积分
- 441
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2013-3-14
- 最后登录
- 1970-1-1
|
本帖最后由 14417335 于 2019-3-2 00:47 编辑
今天的重点在于复习各种图论算法。一般来说我不会在总结里面写code但是这一章是个例外，因为里面涉及到的算法我实在太不熟了。所以写下code以备随时查阅。我们统一输入， 假设给出某有向带权图d所有边vector<vector<int>> edges, 每个edge用一个vector表示, 包含[u, v, w]也就是起点终点和权重, 节点总数V(编号1->V)。假设起点为A， 我们用d[ u]来表示起点A到u的最短距离。
1. 最短路径问题
所有最短路径问题假设没有负环，不然很显然不存在最短路径。
1.1 bellman-ford
解决单源，有负边图中的最短路径问题。其核心思想设d[ i]是起点A到i的最短路径，则有d[j] = min(d[ i] + w[ij]),其中i是所有和j相连的点。反过来推断，我们可以先求出从A点出发1条边能到达的最短路径，然后求2条边能到达的最短路径，直到求出 V-1 条边能到达的最短路径。因此实际上我们循环 V-1 次，对所有边进行松弛操作即可, 复杂度 O(VE)。这里所谓的松弛操作是指我们利用边 u->v 来优化 d[v]的过程 (d[v] = min(d[v], d[ u] + w[uv]).
为了判断是否存在负环，我们只需要进行V次路径松弛。如果发现最后一次某d[ i]又被更新了，那么证明存在负环（因为如果没有负环，最短路径不可能经过一个点两次，换句话说最短路径最多只有V-1个点）。
代码:
int bellman_ford() {
int d[V+1];
int u, v, w;
for (int i = 1; i <= V; i++) {
d[ i] = INT_MAX;
}
d[A]= 0;
for (int i = 0; i < V-1; i++)
for (vector<int> edge: edges) {
u = edge[0];
v = edge[1];
w = edge[2];
if (d[ u] != INT_MAX && d[v] > d[ u] + w)
d[v] = d[ u] + w;
}
}
最后，注意bellman-ford的一个特例:如果给出的图是DAG的话那么我们可以先计算图的拓扑排序，然后按照拓扑排序的顺序依次进行路径松弛即可。这样的复杂度仅仅为O(E).
1.2 Dijstra
解决单源，无负边图中的最短路径问题。仔细观察一下bellman-ford算法，可以发现其中存在一些时间浪费。比如如果d[ i]不是最短路径，自然d[ i] + w[ij]也不可能是A到j的最短路径。再比如如果d[ i]没有被更新(d[ i]已经是找到的最短路径了)，下次循环我们还是会依次更新所有和i相邻的边。
为了优化，我们可以考虑假设d[ i]已经是A能出发所达到的最短路径，那么我们可以把和i相邻的边依次松弛一遍，然后就不用再考虑i了。因为在没有负边的情况下，d[ i]不可能在以后的更新过程中会变得更小。我们可以简单的在bellman-ford的基础上修改一下。我们首先需要用used数组来记住那些最短路径还没有被确定的点，然后每次松弛的时候都找 used[ i] == False 中d[ i]最小的点i。随后我们只需要松弛点i的邻居节点即可。
代码如下：
int dijstra_v1() {
int d[V+1];
bool used[V+1];
int u, v, w;
fill(used, used+N+1, false);
fill(d, d+N+1, INT_MAX);
d[A] = 0;
int cost[V+1][V+1];
for (int i = 1; i <= V; i++)
for (int j = 1; j <= V; j++) {
if (i == j)
cost[ i][j] = 0;
else
cost[ i][j] = INT_MAX;
}
for (vector<int> edge: edges) {
int u = edge[0];
int v = edge[1];
int w = edge[2];
cost[ u][v] = w;
}
for (int i = 0; i < A-1; i++) {
int v = -1;
for (int j = 1; j <= A; j++) {
if (!used[j] && (v == -1 || d[j] < d[v]))
v = j;
}
for (int j = 1; j <= A; j++) {
if (cost[v][j] != INT_MAX && d[j] > d[v] + cost[v][j]) {
d[j] = d[v] + cost[v][j];
}
}
used[v] = 1;
}
}
看似很复杂，主要是我们需要先初始化这个cost矩阵，其中cost[ i][j]记录着i到j的路径长度，INF表示i和j不直接相连。这样复杂度是O(V*V)。
注意到这里最麻烦的一个操作是找d[ i]中的最小值。为了优化这个过程我们可以把d[ i]加入最小堆中，这样的复杂度就是O(ElogV)了。这里的E是因为我们对每个边都进行了一次松弛操作。然后logV是因为堆中总元素不会超过定点总个数。
int dijstra_v2() {
typedef pair<int, int> P;
int d[V+1];
fill(d, d+V+1, INT_MAX);
d[A] = 0;
vector<P> graph[V+1];
for (vector<int> edge : edges) {
graph[edge[0]].push_back(make_pair(edge[1], edge[2]));
}
priority_queue<P, vector<P>, greater<P> > pq;
pq.push(make_pair(0, A));
P node;
while (!pq.empty()) {
node = pq.top();
pq.pop();
int u = node.second;
if (d[ u] < node.first) continue;
res = max(res, node.first);
cnt += 1;
for (P neigh: graph[ u]){
int v = neigh.first;
int w = neigh.second;
if (d[v] > d[ u] + w) {
d[v] = d[ u] + w;
pq.push(make_pair(d[v], v));
}
}
}
}
注意一些坑，比如某个点可能不止一次被加入并且从pq中pop出来，这是因为对某点v, 我们可能找到经过u1->v的最短路径以及经过u2->v的最短路径，但是只有一条是从起点A->v的最短路径。为了解决这个问题我们在pop出某点v的时候计算下此时的最短距离是否比d[ u]要小，如果是的话忽略即可。
此外，如果有负边的话，dijstra算法是不行的。最简单的例子 A->B:1, A->C:2，C->B:-3. A->B的实际最短路径是-1。可是根据dijstra算法，第一次找到A->B的最短路径后就不会再去考虑它了，这样会得到错误的结果。
dijstra的一个特例是所有边没有权重或者所有边权重相同的情况，这种情况下显然bfs就可以了。复杂度O(E)。
1.3 Floyd-Warshall算法
多源最短路径问题，求所有点到所有点的最短路径。可以处理存在负边的情况。假设D[i,j,k]是从i到j经过1->k号中间节点的最短路径的长度。则考虑两种情况：最短路径不经过节点k，则D[i,j,k] = D[i,j,k-1], 或者最短路径经过节点k，则 D[i,j,k] = D[i,k,k-1] + D[k,j,k-1]。综合起来也就是
D[i,j,k] = min(D[i,j,k-1], D[i,k,k-1] + D[k,j,k-1])
注意k只依赖于k-1的情况，因此空间复杂度可以优化到 O(V^2)，时间复杂度显然是O(V^3)。代码极其简单:
int floyd() {
int dp[V+1][V+1];
for (int i = 1; i <= V; i++)
for (int j = 1; j <= V; j++)
dp[ i][j] = i == j ? 0:INT_MAX;
for (vector<int> edge:edges) {
dp[edge[0]][edge[1]] = edge[2];
}
for (int k = 1; k <= V; k++)
for (int i = 1; i <= V; i++)
for (int j = 1; j <= V; j++) {
if (dp[ i][k] != INT_MAX && dp[k][j] != INT_MAX)
dp[ i][j] = min(dp[ i][j], dp[ i][k] + dp[k][j]);
}
}
因为代码过于简单，在输入规模很小的情况下也可以考虑用 Floyd 算法来计算单源最短距离。
补充内容 (2019-3-3 06:47):
dijstra实现的坑
1. 注意初始化，节点编号1->V,初始化V+1个元素
2. if d[u ] <= node.first 则会出错，因为 u的邻居节点还没有被relax过 |
|
楼主: charleszhou
狗仔卡
楼主
