图论（一）图的存储和Floyd算法

大家好，我是BUG，最近我正在研究各种算法。所以我就为大家发少量算法博客。

让我们先从这里开始

如果你是Java或者Python开发者，你可能只能看伪代码，由于通篇博客使用C++撰写。毕竟，使用面向过程的算法博客能让代码显得简单明了，多范式语言C++就支持面向过程，因而我们使用C++。

图论？

记住Floyd Warshall，他是图论的一个重要开创人
Floyd提出的算法可以实现任意两个点的最短路径
当然我们还有别的最短路径算法，我们一起基本理解一下，具体见表

名称	作用	时间复杂度	解决负权边
Floyd-Warshall	任意两个点最短路径		可以
Dijkstra	单原最短路径		不可以
Bellman-Ford	单原最短路径		可以

最后补充几个概念

1. 方向

   • 有向图（边有方向的图）
     有向图一条边就是一条边，由于有向图指定了一个方向
   • 无向图 （边没有方向的图）
     无向图一条边可以认为是两条边，由于无向图一条边有两个方向

   • 搞不懂？看一张图：

     原谅我的手绘

2. 组成

   • 代表点
   • 代表边

3. 权值

   • 边的大小叫做权值

4.图要连通，且一个点能由多个点发出，这就是和树的本质性区别

图模拟

我在Google上精挑细选了一幅图
现在我们用一个二维数组存储这个图

我们先查看点1能够到达的点：它能到达点2、4、5
理论上点1能够到达自己，但是权值为零，点1到不了的点，权值为无穷大
C++可以以这样定义无穷大

#define inf 99999999

Java，Python等语言如下

final int inf = 99999999;//Javainf = 99999999//Pythonval inf = 99999999//Scala and Kotlin

所以表升级如下：

1行列是点1到点的权值
现在我填满这张表（建议你先自己试试看）

实在无法想象，这就是刚才那幅图的模型。其实构建一个矩阵很简单，赶紧动手模拟吧

Floyd-Warshall实现

Floyd算法就是用这样的矩阵实现的。在此先提供三个链接

Youtube上的视频，英文的
上不了Youtube也没关系，刚才那段视频的百度网盘链接在此，提取码: 15wb
不想听英语？看这个链接（优酷）

现在我们开始学习Floyd算法了。
如何让1号到3号路径缩短?
首先要保证我们得出任意两个点的最短路径，就必需选择一个点中转，（上例选择2号）让最短路径缩小。那么我们选择哪个点呢？首先我们只经过一号顶点，逐步允许经过二号，三号……

for(int i = 1; i <= V; i++){//顶点个数V}

而后只需选择起始点和终止点（上例选择起始点j为1号，终止点k为3号），优化最短路径就可。

for(int i = 1; i <= V; i++){//顶点个数V        for(int j = 1; j <= V; j++){                for(int k = 1; k <= V; k++){                        if(e[j][k]>e[i][k]+e[j][i])                                e[j][k]=e[i][k]+e[j][i];                }        }}

我们看到，上例的最短路径从无穷大缩小到了5。关键是，Floyd的代码竟然只有五行！
这篇文章就到此为止了，希望你能有收获哦