8. 拓扑排序和Dijkstra

阅读信息

约 263 个字 4 分钟本页总访问量：加载中... 次

Class Eight

拓扑排序

例子: 不同课程之间有依赖关系,有些课程需要其他课作为前置课程.用图表示依赖关系,有以下关系:
形成无回路的有向图(DAG,有向无环图)
用点或边表示要素(AOV)
目标: 根据课程的依赖关系,列出不矛盾的选课的顺序.
拓扑排序方法:

找到第一门:入度为零的点

每找到一个点后,删除该点.(每次处理后图发生一点改动.)修改下一个点的入度.

每次随机选取入度为零的点,重复前两步.

部分有序(partial order) 有些点有序,有些点无序
代码:

C
void topSort(图 g) {
  for (int cnt = 0; cnt < 点的总数; cnt++) {
    int v = 找到一个入度为零的点;
    print(v);
    for (所有v指向的点w)
      w的入度--; // 从一个点出发,根据这个点修改周围点的信息
  }
}

怎么查找入度为零的点? 构建队列.每次修改入度时如果改后为零,加入队列.

C
void topSort(图 g) {
  队列 Q;
  for (遍历所有点v) {
    if (v的入度 == 0)
      enqueue(v, Q);
  }
  while (Q非空) {
    v = dequeue(Q);
    print(v);
    for (所有v指向的点w) {
      if (--w的入度 == 0)
        enqueue(w, Q);
    }
  }
}

最短路径问题

单源最短路问题:Dijkstra

初始化所有点的路径为无穷大

找出没有被拓展过且距离源点最近的点

将这个点标记为已经拓展过

(利用该点修改与它相连的点的信息.)判断新添加的路径长度是否小于原有长度,如果小于则更新长度

C++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e3 + 5;
const ll inf = 4e18;

struct Node {
    int x, w;  // x表示出点，w表示权值
};
vector<Node> g[N];
ll d[N], n, m;

void dijkstra(int st) {
    memset(d, 0x3f, sizeof(ll) * (n + 1));  // 初始化为无穷大
    d[st] = 0;
    bitset<N> vis;  // vis表示是否拓展过,每个点只被拓展一次

    for (int i = 1; i <= n; i++) {
        // 找出距离源点最近的点
        int u = 1;
        for (int j = 1; j <= n; j++) {
            if (vis[u] || (!vis[j] && d[j] < d[u]))
                u = j;
        }

        vis[u] = true;  // 表示u已经拓展过

        // 此时d[u]已经为最优
        for (auto& [v, w] : g[u]) {
            if (!vis[v] && d[v] > d[u] + w)
                d[v] = d[u] + w;
        }
    }
}

// 用优先队列代替寻找最近点的过程
void dijkstra1(int st) {
    memset(d, 0x3f, sizeof(ll) * (n + 1));
    d[st] = 0;
    bitset<N> vis;  // vis表示是否拓展过

    priority_queue<Node> pq;
    pq.push((Node){st, d[st]});  // 起点作为拓展点

    while (pq.size()) {
        int x = pq.top().x;
        pq.pop();

        if (vis[x])
            continue;
        vis[x] = true;

        for (auto& [y, w] : g[x]) {
            if (!vis[y] && d[y] > d[x] + w) {
                d[y] = d[x] + w;
                pq.push((Node){y, d[y]});
            }
        }
    }
}

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        if (u != v)
            g[u].push_back({v, w});
    }

    dijkstra1(1);

    cout << (d[n] >= 4e18 ? -1 : d[n]) << '\n';
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _ = 1;
    while (_--)
        solve();
    return 0;
}

不适用于负边情况:被拓展过一次后不再拓展负边代码:

C
void dijkstra(图 g) {
  队列 Q;
  enqueue(源点, Q);
  while (Q非空) {
    v = dequeue(Q);
    for (v指向的点w) {
      if (v的距离 + 边长度 < w的距离) {
        w的距离 = v的距离 + 边长度;
        if (w不在Q中)
          enqueue(w, Q);
      }
    }
  }
}