Catshao

用户名：Catshao

访问量：28830

签　名：

stO KHIN Orz

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

　　自我简介：

TA的其他文章

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

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

蓝桥杯2020年第十一届省赛真题-八次求和
浏览：556

你可能喜欢

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C++代码）不是所有的时候都要按照题目要求才能AC

优质题解

数据结构-Floyd多源最短路径算法详解（C++代码）（小白向）

　　作者: Catshao　　　　发表时间：2021-02-02 18:19:32 浏览：511　|　评论：0　

原题链接：数据结构-Floyd(弗洛伊德)最短路径算法

>重新写了下，看看能不能加精

# Part 1 概述

floyd是一种计算**多源最短路**的算法，多源最短路就是每一个节点到其他的节点的最短路问题。

由于我们要求出所有点到其他点的最短路，所以在图联通的情况下，邻接矩阵的每一项都有值，**使用邻接矩阵不会浪费空间**

# Part 2 过程

我们先分开来看。现在要求`i`到`j`的最短路，可分为两种方式。

![两种连接方式](http://cat-shao.gitee.io/mypic/floydPoint.png)

1. `i`到`j`直接有路。
2. `i`通过`k`跳转到`j`。

`1, 2`不一定哪一种路径最短，于是我们都需要判断。

#### 方式1

我们题目输入的矩阵就是从`i`到`j`的最短路。在处理方式2的时候在方式1上面叠加即可。

```
4
0 3 0 1
0 0 4 0
2 0 0 0
0 0 1 0
```
#### 方式2

`i, j, k`都是图中的任意一个点，于是我们就可以从`1 ~ n`**枚举**这三个点。

```cpp
graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
```

看不懂？我来翻译一下。

从i到j的距离 = 选一个最小的（已有的i到j， 从i到k然后k到j的距离）
	如果 i到k再到j没有之前的路径短，那么min可以过滤掉长的，保留短的。

~~恕我直言，我感觉这就是一个暴力~~

[**可视化动画**](https://www.cs.usfca.edu/~galles/visualization/Floyd.html)

### 时间复杂度

由于枚举了`i, j, k`，自然有三重循环，于是复杂度为`n ^ 3`。

### 与johnson比较

优：floyd代码非常短，然而在打`johnson`之前还要打`dijkstra`与`bellman_ford`。

劣：
1. floyd和johnson都可以处理负边，但是floyd判断不了负环，需要`bellman_ford`帮助判断负环。
2. floyd复杂度为`n ^ 3`，johnson复杂度为`n^2 * logn`

# Part 3 代码

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

const long long INF = INT_MAX;
const int MAX_N = 100;

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 floyd(long long graph[MAX_N][MAX_N], int n)
{
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
            }
        }
    }
}

int floydMain()
{
    long long graph[MAX_N][MAX_N];
    int n;
    while (~scanf("%d", &n)) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                scanf("%lld", &graph[i][j]);
                if (graph[i][j] == 0 && i != j) {
                    graph[i][j] = INF;
                }
            }
        }
        floyd(graph, n);
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (graph[i][j] == INF) {
                    printf("-1 ");
                } else {
                    printf("%d ", graph[i][j]);
                }
            }
            printf("\n");
        }
    }
    return 0;
}

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

-------------

推荐去看[可视化动画](https://www.cs.usfca.edu/~galles/visualization/Floyd.html)，可以

参考：
1. [漫画：图的 “多源” 最短路径](https://mp.weixin.qq.com/s?__biz=MzIxMjE5MTE1Nw==&mid=2653197861&idx=1&sn=ed3140e711821206b5b50cd418614660&chksm=8c99e4ffbbee6de92ae00262ce1230bce3de384d3cadcf99c3f51aca4ca0c5f7f5a9f2e857df&scene=21#wechat_redirect)
2. [可视化动画](https://www.cs.usfca.edu/~galles/visualization/Floyd.html)

0.0分

1 人评分

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

Catshao

TA的其他文章

你可能喜欢

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

蛇行矩阵（C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

不需要数组和指针的做法！！！

C语言程序设计教程（第三版）课后习题8.6 （C++代码）不是所有的时候都要按照题目要求才能AC

数据结构-Floyd多源最短路径算法详解（C++代码）（小白向）

评论区

精彩推荐

众数问题（C++代码）

【蟠桃记】（C语言代码）

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

永远的丰碑（C语言代码）

【出圈】（C语言代码）

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

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

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

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

核桃的数量（C语言代码）

Catshao

TA的其他文章

你可能喜欢

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

蛇行矩阵 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

不需要数组和指针的做法！！！

C语言程序设计教程（第三版）课后习题8.6 （C++代码）不是所有的时候都要按照题目要求才能AC

数据结构-Floyd多源最短路径算法详解（C++代码）（小白向）

评论区

精彩推荐

众数问题 （C++代码）

【蟠桃记】 （C语言代码）

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

永远的丰碑 （C语言代码）

【出圈】 （C语言代码）

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

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

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

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

核桃的数量 （C语言代码）

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

蛇行矩阵（C语言代码）

　　评论区

众数问题（C++代码）

【蟠桃记】（C语言代码）

永远的丰碑（C语言代码）

【出圈】（C语言代码）

核桃的数量（C语言代码）