最短路三连
最常见的三种最短路算法分别是 Floyd,Dijkstra 和 Bellman 算法
Floyd
Floyd 用于解多源最短路 复杂度为 \(O(n^{3})\) 主要解决稠密图, 可以解决负权边的问题
- void floyd(int n) {
- for (int k = 1; k <= n; k++) {
- for (int i = 1; i <= n; i++) {
- for (int j = 1; j <= n; j++) {
- // mp[i][j] 的值为 i 直接到 j 的值和 i 通过 k 到 j 的值中的较小值
- mp[i][j] = min(mp[i][j], mp[i][k] + mp[k][j]);
- }
- }
- }
- }
- Dijkstra
用于解单源最短路问题, 复杂度为 \(O((m+n)logn)\) 可以看到比起 Floyd 有了质的飞跃, 主要用于解决稠密图
- void dij(int n) {
- // 初始化 dis 数组
- for (int i = 1; i <= n; i++) {
- dis[i] = mp[1][i];
- }
- vis[1] = 1;
- int min;
- int u;
- int v;
- for (int i = 1; i <= n - 1; i++) {
- min = INF;
- for (int j = 1; j <= n; j++) {
- // 如果 j 点没有访问过并且距离小于当前最小值
- if (!vis[j] && dis[j] <min) {
- min = dis[j];
- u = j; // 得到距离点 1 最近的点 u
- }
- }
- vis[u] = 1; // u 标记为已经访问
- for (int v = 1; v <= n; v++) {
- // 遍历其他点, 对于从 u 到 v 有路的, 查看通过点 u 中转的距离近, 还是直接走近
- // 其实就是二维的 Floyd
- if (mp[u][v] < INF && dis[v]> dis[u] + mp[u][v]) {
- dis[v] = dis[u] + mp[u][v];
- }
- }
- }
- // 输出结果
- for (int i = 1; i <= n; i++) {
- cout <<dis[i] << endl;
- }
- }
- Bellman
- int dis[MAX]; // 路径长度
- int u[MAX]; // 边的起始点
- int v[MAX]; // 边的结束点
- int w[MAX]; // 边的权值
- int n; // n 个点
- int m; // m 条边
- void init(void) {
- dis[1] = 0; // 点 1 到自身的距离是 0
- for (int i = 2; i <= n; i++) {
- dis[i] = INF; // 点 1 到其他点初始化成 INF
- }
- }
- // Bellman 类似于广搜, 实际上利用队列可以优化 Bellman,
- // 和广搜不同的是, 广搜一次就不会再进入了, 而 bellman 如果后面又松弛了一次, 那么又会再次入队
- void bellman(void) {
- for (int k = 1; k < n; k++) { // 至多需要 k-1 次松弛
- for (int i = 1; i <= m; i++) { // 对该轮松弛, 尝试每一条边
- if (dis[v[i]]> dis[u[i]] + w[i]) {
- dis[v[i]] = dis[u[i]] + w[i];
- }
- }
- }
- }
来源: http://www.bubuko.com/infodetail-3495815.html