最短路径问题及算法

哥尼斯堡七桥问题：从一个点出发经过每一条边只走一次回到起点。

转化成图论问题，证实发现当一个点连接的边有偶数条时可以一笔画完（等同于从起点走完回到起点）。

基础知识

关联矩阵

关联矩阵描述的是点和边之间的关系，一般点和边相连则矩阵上的数字不为$0$，反之则为$0$。

对无向图$G$，其关联矩阵$M=(m{ij}){v×e}$，其中

$m_{ij}= \begin{cases} 1,&\text{若$v_i$与$e_j$相关联}\\ 0,&\text{若$v_i$与$e_j$不关联} \end{cases}$ 注：假设图为简单图

简单图

则关联矩阵为

$M= \begin{pmatrix} 1 & 0 & 0 & 0 & 1 \\ 1 & 1& 0 & 1 & 0 \\ 0& 0 & 1& 1& 0\\ 0& 1& 1& 0 & 1 \\ \end{pmatrix}$

横坐标表示点$v_1$, $v_2$ , $v_3$, $v_4$，纵坐标表示边$e_1$,$e_2$,$e_3$,$e_4$,$e_5$

对有向图$G$，其关联矩阵 $M=(m{ij}){v×e}$，其中：

$m_{ij}= \begin{cases} 1,&\text{若$v_i$是$e_j$的起点}\\ -1,&\text{若$v_i$是$e_j$的终点} \\ 0,&\text{若$v_i$与$e_j$不关联} \end{cases}$

邻接矩阵

邻接矩阵描述的是点和点之间的关系，一般如果点和点之间有线连接，则矩阵上的数字不为$0$，反之为$0$。

对无向图$G$，其关联矩阵 $A=(a{ij}){v×v}$，其中：

$m_{ij}= \begin{cases} 1,&\text{若$v_i$与$v_j$相邻}\\ 0,&\text{若$v_i$与$v_j$不相邻} \end{cases}$

无向图

则邻接矩阵为：

$M= \begin{pmatrix} 0 & 1 & 0 & 1 \\ 1 & 0& 1 & 1 \\ 0& 1 & 0& 1\\ 1& 1& 1& 0 \\ \end{pmatrix}$

横坐标表示点$v_1$,$v_2$,$v_3$,$v_4$，纵坐标也表示点$v_1$,$v_2$,$v_3$,$v_4$

对有向图 $G=(V,E)$，其邻接矩阵 $A=(a{ij}){v×v}$，其中：

$a_{ij}= \begin{cases} 1,&\text{若$(v_i,v_j){\in}E$}\\ 0,&\text{若$(v_i,v_j){\notin}E$} \end{cases}$

对有向赋权图$G$，其邻接矩阵$A={(a{ij})}{v×v}$，其中：

$a_{ij}= \begin{cases} w_{ij},&\text{若$(v_i,v_j){\in}E$，且$w_{ij}$为其权}\\ 0,&\text{若$i=j$} \\ ∞,&\text{若$(v_i,v_j){\notin}E$} \end{cases}$

无向赋权图的临界矩阵可类似定义。

Dijkstra算法

用法

求赋权图中给定点到任意一点的最短路径

算法思想

Dijkstra算法是基于贪心算法的，该算法每次保证在当前是最优解，在下一次迭代进行求解是，是在上一轮最优解的基础上进行求解，所以每次迭代结果都能够保证是最优解

首先是给定一个点，然后求出该点到其他的最短路径
对于Dijkstra算法求最短路径，我们假设初始集合（也就是初始条件）是不存在任何顶点的，即所有顶点之间是不存在任何路径的，即我们认为所有顶点之间的距离都是无穷大的。
开始加入新的条件，因为我们已知源点距源点距离最小，所以加入进去，并加入它的边，在该条件下，更新该源点到其余顶点的最短距离，选出没有加入到已知集合的距源点距离最小的点，此点最短距离也被确定了（因为其他路径都比这条路径大，无法通过其他路径间接到达这个顶点使得路径更小），然后加入该点与其余还未加入已知条件顶点的边，并以该点迭代刷新最短距离。再重复以上操作，直至所有顶点都加入已知条件集合。
简单来说，就是每次加入一个点就判断其他的点是否会因为加入该点之后距离会比原来的情况下变得更短，并且比较所有已经加入集合的点到未加入集合点的最短路径，将形成最短路径且未加入集合点的点加入集合并且更新距离，依次加到终点即可

步骤

选出一个点 $V_0$ 作为起点，加入集合 $S$，并列出该点到集合${U-S}$的其它点的距离
找该点到其他点的最短路径，并将该点$V_1$加入集合$S$
比较集合加入点$V_1$之后$V_0$到其它点的距离，找出从点$V_1$和$V_0$出发到其他点的最短距离，并将与之连接的点$V_2$加入集合$S$
以此类推，按照第三步重复进行，直至集合$U-S$变成空集为止
最后得到的距离就是$V_0$到其他各点的最短路径

动态展示

Dijastra算法

Floyd算法

Floyd算法（Floyd-Warshall algorithm）又称为弗洛伊德算法、插点法，是解决给定的加权图中顶点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。

用法：求赋权图中任意两点之间的最短路径

时间复杂度$O(n^3)$

适应范围：无负权回路即可

步骤

如下放下讲述采用的是邻接矩阵

初始化$map$数组，如果$i$可以直接到$j$，则$map[i][j]=权值$，反之则$map[i][j]=∞$，如果$i=j$，则$map[i][j]=0$。
依次将每个点加入，假设加入的点是$map[k][k]$，表示点$k$，如果$map[i][j]>map[i][k]+map[k][j]$，则变化数组里面的值，反之则不变，此时点$k$已经在我们纳入的点之内了。
重复第二步，将$k+1$这个点加入，判断在$k+1$作为中介点的情况下，点$i$到点$j$的距离。
最后将所有的点都遍历完求得的矩阵表示的数值就是最短距离。

图像演示

第一步

第二步

第三步

第四步

第五步

第六步

第七步

第八步

基本代码

for(k=1;k<=n;k++) //中转节点 
     for(i=1;i<=n;i++) 第二层循环
         for(j=1;j<=n;j++)  第三层循环
                if(e[i][j]>e[i][k]+e[k][j] )如果直接到达比通过k这个中转接点到达的距离短   
                     e[i][j]=e[i][k]+e[k][j];那么就更新松弛

有向图构建最短路径：

有向图可以通过添加path矩阵来进行寻找路线

第一步

第二步

第三步

第四步

第五步

第六步

第七步

第八步

核心代码：

for(k=1;k<=n;k++) //中转节点 
     for(i=1;i<=n;i++) 第二层循环
         for(j=1;j<=n;j++)  第三层循环
                if(dist[i][j]>dist[i][k]+dist[k][j] )
                    dist[i][j]=dist[i][k]+distk][j];
                    path[i][j]=k; //记录路径的数组