Catshao

用户名：Catshao

访问量：28829

签　名：

stO KHIN Orz

等　　级
排　　名	161
经　　验	7130
参赛次数	6
文章发表	46
年　　龄	12
在职情况	学生
学　　校	双语
专　　业

　　自我简介：

TA的其他文章

[ω] 最大子段乘积
浏览：108

蓝桥杯2020年第十一届省赛真题-整数小拼接
浏览：1472

蓝桥杯2020年第十一届省赛真题-BST插入节点问题
浏览：547

你可能喜欢

A+B for Input-Output Practice (IV) （C++代码）

C语言训练-求1+2!+3!+...+N!的和（C语言代码）

【小白向】Johnson 全源最短路详解

　　作者: Catshao　　　　发表时间：2021-02-04 16:36:04 浏览：222　|　评论：0　

[TOC]

# Part -1 前置算法

在学习johnson之前，你需了解**dijkstra**算法与**bellman_ford**算法（floyd学了后效果会更好）。

| 内容  | 资料  |
| ------------ | ------------ |
| dijkstra  |  [小灰的文章](https://mp.weixin.qq.com/s?__biz=MzIxMjE5MTE1Nw==&mid=2653197626&idx=1&sn=fca7472af006a7f8890ee84ad7cf1116&chksm=8c99e7e0bbee6ef6faa1a34160a5e135503425e37552e90dfca2fbc10f223dbf3b875e84e418)  ; [可视化dijkstra](https://www.cs.usfca.edu/~galles/visualization/Dijkstra.html)|
| bellman_ford  | [算法导论 bellman_ford](#bellman_ford)；[bellman_ford详解](https://blog.dotcpp.com/a/76339)  |

# Part 1 起因

nlogn的堆优化dijkstra跑n次也要比n^3的floyd快。用**dijkstra跑全源最短路**应该不是一个坏主意。于是我询问了学长：

![请教神犇](http://cat-shao.gitee.io/mypic/c5c7bddaec238999292c13b5a7d72ee.png)

![请教神犇2](http://cat-shao.gitee.io/mypic/92e29ad7280ae8aea063dd4c912495e.png)

询问得知，**dijkstra处理不了权值为负数的边**

### 为什么dijkstra处理不了负边？

负边分为两种情况，一种是负环，另一种非负环

#### [负环](https://blog.dotcpp.com/a/76339#%E8%B4%9F%E7%8E%AF)

![负环](http://cat-shao.gitee.io/mypic/fuhuan.png)

上面这个图，绕一圈权值会更小，我们对这种现象称为负环。这种图的对某些点式没有最短路径的（绕不出来），所以我们需要对其特判。

为了防止程序无休止地绕下去，通过**bellman_ford**可以判定负环：

> 前面说过，最多只需要更新`n - 1`次，那么，如果在第`n`次更新了，必然是图中有负环。由于负环可以一直绕下去，所以有负环的图最短路是无解的。

#### 负边

![算法笔记部分](http://cat-shao.gitee.io/mypic/%E7%AE%97%E6%B3%95%E7%AC%94%E8%AE%B0-dij%E4%B8%8D%E8%83%BD%E5%A4%84%E7%90%86%E8%B4%9F%E8%BE%B9.png)

### 加大数让dijkstra处理负边

**将图中每一项都加一个非常大的数。**可以将负边换掉
但是这会使**答案错误**。举一个例子：

![反例](http://cat-shao.gitee.io/mypic/%E5%8A%A0%E6%9E%81%E5%A4%A7%E5%80%BC%E5%8F%8D%E4%BE%8B.jpg)
如图，当我们加上1时，本来的最短路为 `1->2->3->4`，长度为3；加上数后明显从`1->4`是最短的，长度为5，原最短路长度为6。

# Part 2 概述

![原图](http://cat-shao.gitee.io/mypic/%E6%A0%B7%E4%BE%8B.jpg)

首先我们添加一个新节点，使这个节点与图上的每一个定点都联通，权值均为0。

![第一步：加入节点](http://cat-shao.gitee.io/mypic/%E6%B7%BB%E5%8A%A0%E8%8A%82%E7%82%B9.jpg)

这时候，我们对新节点用**bellman_ford求最短路**（bellman_ford可以处理负边，**堆优化的SPFA不能处理负边**）。得到的结果非0即负，用一个`数组h`将结果存起来。

![第二步：bellman-ford](http://cat-shao.gitee.io/mypic/bellman_ford%E4%B9%8B%E5%90%8E.jpg)

这个时候，我们使用下面这个公式，来更新每一条边的边权。（w即为weight，权重。等号左边为新权值，等号右边为**原权值+h[起点]-h[终点]**）

我们通过这个公式来更新权值：
```
新权值 = 原权值 + h[起点] - h[终点]
```

>补丁：3->4的路径为-2+(-3-(-5)) = 0，少打了一个负号

![第三步：更新权值](http://cat-shao.gitee.io/mypic/%E5%B8%A6%E5%9B%9E%E5%8E%9F%E5%9B%BE.jpg)

此时图上已经**没有负边**了，我们可以放心大胆地dijkstra了。

针对每一个定点进行dijkstra，但是得到的距离表并不是原权值，而是经过bellman_ford的权值，所以我们需要进行**换算**。

```
距离 = 新权值 + h[终点] - h[起点] 
```

# Part 3 正确性证明

![算法导论地证明+注释](http://cat-shao.gitee.io/mypic/%E6%9C%80%E7%9F%AD%E8%B7%AF%E7%AE%97%E6%B3%95%E8%AF%81%E6%98%8E.png)

# Part 4 题目&代码

大家可以去尝试[洛谷的johnson模板题](https://www.luogu.com.cn/problem/P5905)。

注意：
1. **边权可能为负**，且图中可能存在**重边和自环**。
2. 数据卡spfa。
3. 这题卡long long了，printf别忘了用lld。

## 代码
（由于数据过大，所以dis表必须开成全局变量，在函数内开不出来。）
```cpp
//
// Created by Cat-shao on 2021/2/7.
//

#include <cstdio>
#include <deque>
#include <queue>
#include <climits>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;

const long long INF = 1000000000;
const int MAX_N = 3010;

class edge {
public:
    int to;
    long long cost;
    edge() {
    }

edge(int _to, long long _cost) {
        to = _to;
        cost = _cost;
    }

bool operator < (const edge &e) const {
        return cost > e.cost;
    }
};

typedef deque<edge> graphType;

void dij(graphType graph[], long long dis[], int path[], int n, int s)
{
    bool mark[MAX_N];
    priority_queue<edge> q;
    for (int i = 1; i <= n; ++i) {
        dis[i] = INF;
    }
    memset(path, 0, sizeof(path));
    memset(mark, 0, sizeof(mark));

dis[s] = 0;
    q.push(edge(s, 0));
    while (!q.empty()) {
        int index = q.top().to;
        q.pop();
        if (mark[index]) {
            continue;
        }

mark[index] = true;
        for (graphType::iterator it = graph[index].begin(); it != graph[index].end(); it++) {
            if (dis[index] + it->cost < dis[it->to]) {
                dis[it->to] = dis[index] + it->cost;
                path[it->to] = index;
                q.push(edge(it->to, dis[it->to]));
            }
        }
    }
}

bool bellmanFord(graphType graph[], long long dis[], int n, int s)
{
    fill(dis, dis + MAX_N, INF);
    dis[s] = 0;
    for (int k = 1; k <= n; ++k) {
        bool update = false;
        for (int i = 1; i <= n; ++i) {
            for (graphType::iterator it = graph[i].begin(); it != graph[i].end(); it++) {
                if (dis[i] + it->cost < dis[it->to]) {
                    dis[it->to] = dis[i] + it->cost;
                    update = true;
                    if (k == n) {
                        return false;
                    }
                }
            }
        }
        if (!update) {
            return true;
        }
    }
    return true;
}

bool johnson(graphType graph[], long long dis[MAX_N][MAX_N], int n)
{
    graphType newGraph[MAX_N];
    long long h[MAX_N];
    int path[MAX_N];
    for (int i = 1; i <= n; ++i) {
        newGraph[i] = graph[i];
    }
    for (int i = 1; i <= n + 1; ++i) {
        newGraph[n + 1].push_back(edge(i, 0));
    }
    if (bellmanFord(newGraph, h, n + 1, n + 1)) {
        for (int i = 1; i <= n; ++i) {
            for (graphType::iterator it = newGraph[i].begin(); it != newGraph[i].end(); it++) {
                it->cost = it->cost + h[i] - h[it->to];
            }
        }

for (int i = 1; i <= n; ++i) {
            memset(path, 0, sizeof(path));
            dij(newGraph, dis[i], path, n, i);
            for (int j = 1; j <= n; ++j) {
                if (dis[i][j] != INF) {
                    dis[i][j] = dis[i][j] - h[i] + h[j];
                }
            }
        }
        return true;
    } else {
        return false;
    }
}

//long long DIS[MAX_N][MAX_N]; // 开不出来
int johnsonMain()
{
    long long DIS[MAX_N][MAX_N];
    int n, m, u, v, w;
    graphType graph[MAX_N];
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        scanf("%d%d%d", &u, &v, &w);
        graph[u].push_back(edge(v, w));
    }
    if (johnson(graph, DIS, n)) {
        for (int i = 1; i <= n; ++i) {
            long long sum = 0;
            for (int j = 1; j <= n; ++j) {
                sum += j * DIS[i][j];
            }
            printf("%lld\n", sum);
        }
    } else {
        printf("-1");
    }
    return 0;
}

int main()
{
    johnsonMain();
}
```

--------------
**如果发现了代码或图中的问题，请及时在评论中贴出！谢谢！**

参考：
1. [《算法笔记》](https://book.douban.com/subject/26827295/)
2. [《算法导论（原书第3版）》](https://book.douban.com/subject/20432061/)
3. [《dijkstra算法为什么不能有负边？》](https://www.cnblogs.com/FengZeng666/p/11245243.html)
4. [《Johnson 全源最短路径算法》](https://www.cnblogs.com/gaochundong/p/johnson_algorithm.html)

0.0分

3 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

Catshao

TA的其他文章

你可能喜欢

A+B for Input-Output Practice (IV) （C++代码）

C二级辅导-等差数列（C语言代码）

C语言训练-求1+2!+3!+...+N!的和（C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C++代码）

【小白向】Johnson 全源最短路详解

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

兰顿蚂蚁（C++代码）

C语言训练-大、小写问题（C语言代码）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

Hello, world! （C++代码）

字符串输入输出函数（C语言代码）

妹子杀手的故事（C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

字符逆序（C语言代码）

Catshao

TA的其他文章

你可能喜欢

A+B for Input-Output Practice (IV) （C++代码）

C二级辅导-等差数列 （C语言代码）

C语言训练-求1+2!+3!+...+N!的和 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C++代码）

【小白向】Johnson 全源最短路详解

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

兰顿蚂蚁 （C++代码）

C语言训练-大、小写问题 （C语言代码）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

Hello, world! （C++代码）

字符串输入输出函数 （C语言代码）

妹子杀手的故事 （C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

字符逆序 （C语言代码）

C二级辅导-等差数列（C语言代码）

C语言训练-求1+2!+3!+...+N!的和（C语言代码）

　　评论区

兰顿蚂蚁（C++代码）

C语言训练-大、小写问题（C语言代码）

字符串输入输出函数（C语言代码）

妹子杀手的故事（C语言代码）

字符逆序（C语言代码）