最短路问题

最短路问题又可以分为单源最短路和多源最短路两种，其中单源最短路指的是一个从一个起点出发到达其他所有的点的问题，多源最短路指的是从每个点出发到达其他点的最短路。对每个点求一遍单源最短路就可以求得多源最短路

最短路算法的一些技巧

对于不同的算法有不同的存图方式，一般采用邻接链表和邻接矩阵的方法
对于图中不可到达的两个点一般赋值为 $\infty$ ,在一般的程序中可以用 $0x3f3f3f3f$ 代替，选用这个数字的好处是，这个数字的两倍仍然没有超过 $int$ 类型所能表示的最大范围，如果你用的python当我没说

floyd算法

floyd算法是一种多源最短路算法，用于求解任意点之间得最短路问题。
floyd算法需要使用邻接矩阵来存图

floyd算法的主要过程

枚举 $k$ 为中点，判断 $i$ 到 $k$ 加上 $k$ 到 $j$ 的距离是否小于 $i$ 到 $j$ ，小于 $i$ 到 $j$ 则更新 $i$ 到 $j$ 的距离

for k 是图G中的点：
    for i 是图G中的点:
        for j 是图G中的点：
            shorestpath[i][j]=min(shorestpath[i][j],shorestpath[i][k]+shorestpath[k][j])

floyd算法的正确性

按照动态规划的思想来解释floyd算法
我们假设 $dp[k][i][j]$ 表示用前 $k$ 个点来优化 $i,j$ 之间最短路能够得到的最短距离
那么 $dp[k][i][j]=\min(dp[k-1][i][k]+dp[k-1][k][j],dp[k][i][j])$
也就是说用前 $k$ 个点来优化 $i,j$ 间最短路的答案就是用前 $k-1$ 个点优化后再用第 $k$ 个点来优化
对于数组的第一维，我们发现只与 $k$ 和 $k-1$ 有关，也就是始终只是在两张图之间转移
可以用滚动数组的方法来优化掉。因为枚举第 $k$ 个点时使用的正是第 $k-1$ 个点优化完的图
图片说明

floyd算法的时间复杂度

很明显算法用到了三重循环，所以算法的复杂度是 $O(n^3)$

Dijkstra最短路算法(以下简称Dijkstra算法)

Dijksta算法是单源最短路算法，用于求解从一个起点到其他所有起点的最短路距离
Dijkstra算法可以用邻接矩阵存图，但是为了追求效率，可以用邻接表存图
一般情况下Dijkstra不可以处理含有负边权的图

Dijkstra算法的主要流程

用 $edge$ 表示边， $dis_i$ 表示点 $i$ 到起点之间的距离
定义两个集合，一个集合 $A$ 表示已经找到最短路的集合，另一个 $B$ 没有，一开始集合 $A$ 中只有起点一个元素，集合 $B$ 则含有其他的所有点
1.从 $B$ 集合中选择一个直接连向起点，且距离起点最近的点,以下记作 $i$
2.将这个点从集合 $B$ 中删去，加入集合 $A$ 中，并用这个点更新所有点到起点的距离 $dis_j=min(dis_j,dis_i+edge.weight)$
3.重复前面的操作直到 $B$ 集合为空

while 集合B中还有点：
    p 是任意一个集合B中的点
    for i 是集合B中的点
        if dis[i]<dis[p]:
            p=i//这一步是找出距离起点最近的点
    将p放入集合A中
    for edge 是与p相连的所有边,q是edge相连的另一个端点
        dis[q]=min(dis[q],dis[p]+edge.weight)

在实际代码中可以用数组标记点是否在集合A中，相对的不在集合A中的点就在集合B中

vis[i]表示点i是否在集合A中
vis[start]=true
while 还有点在集合A外：
    p 是任意一个集合B中的点
    for i 是集合B中的点
        if !vis[i] && dis[i]<dis[p]:
            p=i//这一步是找出距离起点最近的点
    vis[p]=true
    for edge 是与p相连的所有边,q是edge相连的另一个端点
        dis[q]=min(dis[q],dis[p]+edge.weight)

Dijkstra算法的图示

给出一张图,求a,h之间的最短路

从a开始，距离a最近的点是b，距离为2，将b加入集合，并用b更新其他点到a的距离，此时d到a的距离变为3

此时d是集合外距离a最近的点，将d加入集合，并用d更新其他点到a的距离，此时c到a的距离为4，f到a的距离为2

此时c是集合外距离a最近的点，将c加入集合，并用c更新其他点到a的距离，发现没有可以更新的点

此时f是集合外距离a最近的点，将f加入集合，并用f更新其它点到a的距离，此时e到a的距离变为7

此时e是集合外距离a最近的点，将e加入集合，并用e更新其他点到a的距离，此时g到a的距离为9

此时g是集合外距离a最近的点，将g加入集合，并用g更新其他点到a的距离，此时h到a的距离为12

将h加入集合，此时集合A中含有途中所有的点，算法结束

此时 $dis_h$ 就是a到h的最短距离

Dijkstra算法的时间复杂度分析

假设图中点的个数是 $n$
因为要将 $n$ 个点加入集合A中算法才能结束，所以这一部分有 $O(n)$ 的复杂度
每次都要加入一个距离起点最近的点，同时更新每个点到起点的距离，这一步需要枚举所有的点，复杂度也是 $O(n)$ ，最后总的复杂度是 $O(n^2)$

Dijkstra算法的正确性证明

数学不好，就用非形式化的语言证明一下了
一开始，从点 $a$ 到另一个点 $b$ 的最短路可以分为两种情况

$\quad$ 1.从 $a$ 直接到达点 $b$

$\quad$ 2.从 $a$ 经过其他若干的点到达点 $b$
因为在一开始限定了Dijkstra算法只能用于不具有负边的图中，所以如果 $ab$ 之间的边是与 $a$ 相连的所有边总最短的一条边，那么想要经过其他的点到达 $b$ 点，一定得先经过 $a$ 的其他连边，而一旦经过这些边，结果就已经大于 $ab$ 之间的连边了此时 $b$ 就明确了一条到 $a$ 之间的最短路，之后用 $b$ 点更新所有 $b$ 能够连向的点到 $a$ 点的距离
此时 $a$ 由一个点变为了一个集合，同理从a所在集合到达c点可以分为两种情况，

$\quad$ 1.从a所在集合直接到达点 $c$

$\quad$ 2.从a所在集合经过其他若干的点到达点 $c$
同样的，此时通过 $ab$ 之间的最短边到达 $c$ 是最优的情况

需要注意的是，是最短边决定了哪个点是 $b$ ，而不是 $b$ 决定了哪条边，也就是先找出最短的边，那条边所连的点，就是下一个加入集合的点

Dijkstra算法的优化

发现算法算法在寻找最短的边上浪费了非常多的时间，可以将所有更新的边加入一个小顶堆，每次从堆顶取一条边，可以保证这条边是最短的边，小顶堆的插入复杂度为 $O(\log(n))$ ,查询复杂度为 $O(1)$ ,可以将Dijkstra最短路算法的时间复杂度降低到 $O(n\log(n))$
对每一个点进行一次Dijkstra最短路算法，可以求得多源最短路，堆优化后的时间复杂度为 $O(n^2\log(n))$

算法课-最短路算法