程序员面试常问的小算法总结 _算法

图的最短路径算法
Floyd最短路算法（多源最短路）
参考：https://www.cnblogs.com/ahalei/p/3622328.html

文章插图

在这里插入图片描述
上图中有4个城市8条公路，公路上的数字表示这条公路的长短。请注意这些公路是单向的。我们现在需要求任意两个城市之间的最短路程，也就是求任意两个点之间的最短路径。这个问题这也被称为“多源最短路径”问题。
现在需要一个数据结构来存储图的信息，我们仍然可以用一个4*4的矩阵（二维数组e）来存储。

文章插图

在这里插入图片描述
核心代码：
这段代码的基本思想就是：
最开始只允许经过1号顶点进行中转，接下来只允许经过1和2号顶点进行中转……允许经过1~n号所有顶点进行中转，求任意两点之间的最短路程。用一句话概括就是：从i号顶点到j号顶点只经过前k号点的最短路程。
Dijkstra最短路算法（单源最短路）
参考：http://blog.51cto.com/ahalei/1387799
【程序员面试常问的小算法总结】指定一个点（源点）到其余各个顶点的最短路径，也叫做“单源最短路径” 。例如求下图中的1号顶点到2、3、4、5、6号顶点的最短路径。

文章插图

在这里插入图片描述
仍然使用二维数组e来存储顶点之间边的关系，初始值如下。

文章插图

在这里插入图片描述
我们还需要用一个一维数组dis来存储1号顶点到其余各个顶点的初始路程，如下。

文章插图

在这里插入图片描述
将此时dis数组中的值称为最短路的“估计值” 。
既然是求1号顶点到其余各个顶点的最短路程，那就先找一个离1号顶点最近的顶点。通过数组dis可知当前离1号顶点最近是2号顶点。当选择了2号顶点后，dis[2]的值就已经从“估计值”变为了“确定值”，即1号顶点到2号顶点的最短路程就是当前dis[2]值。
既然选了2号顶点，接下来再来看2号顶点有哪些出边呢。有2->3和2->4这两条边。先讨论通过2->3这条边能否让1号顶点到3号顶点的路程变短。也就是说现在来比较dis[3]和dis[2]+e[2][3]的大小。其中dis[3]表示1号顶点到3号顶点的路程。dis[2]+e[2][3]中dis[2]表示1号顶点到2号顶点的路程，e[2][3]表示2->3这条边。所以dis[2]+e[2][3]就表示从1号顶点先到2号顶点，再通过2->3这条边，到达3号顶点的路程。
这个过程有个专业术语叫做“松弛” 。松弛完毕之后dis数组为：

文章插图

在这里插入图片描述
接下来，继续在剩下的3、4、5和6号顶点中，选出离1号顶点最近的顶点4，变为确定值，以此类推。

文章插图

在这里插入图片描述
最终dis数组如下，这便是1号顶点到其余各个顶点的最短路径。

文章插图

在这里插入图片描述

M：边的数量
N：节点数量

通过上面的代码我们可以看出，这个算法的时间复杂度是O(N^2) 。其中每次找到离1号顶点最近的顶点的时间复杂度是O(N)
优化:

这里我们可以用“堆”（以后再说）来优化，使得这一部分的时间复杂度降低到O(logN) 。
另外对于边数M少于N^2的稀疏图来说（我们把M远小于N^2的图称为稀疏图，而M相对较大的图称为稠密图），我们可以用邻接表来代替邻接矩阵，使得整个时间复杂度优化到O( (M+N)logN) 。
请注意！在最坏的情况下M就是N^2，这样的话MlogN要比N^2还要大。但是大多数情况下并不会有那么多边，因此(M+N)logN要比N2小很多。

用邻接表代替邻接矩阵存储
参考：http://blog.51cto.com/ahalei/1391988
略微难懂，请参考原文
总结如下：
可以发现使用邻接表来存储图的时间空间复杂度是O(M)，遍历每一条边的时间复杂度是也是O(M) 。如果一个图是稀疏图的话，M要远小于N^2 。因此稀疏图选用邻接表来存储要比邻接矩阵来存储要好很多。