求图的最短路径（详谈Floyd和Dijkstra）
（注：在这一部分起点、源点意思相近；点的距离、边的长度、权值意思相近）
（再注：这里面包含一个隐含知识点，遇到有关图的问题时部分同学会感到无从下手，无法把握数据规模，其实一个包含n个点的图，最多包含n*（n-1）条通路，知道了这一点，也就对数据规模有所把握了。笔者看多许多教参都没有提到这一点，所以想在最开始讲最短路前提一下这一点。这一点也非常好证明，每个点可能有若干的入度和出度，但是每条边只有一个出度一个入度这样两个维度，所以边的数量的规模最大就是n的平方，想要加深理解的话还可以化成一张n行n列的二维表格（一个包含n个点的图），行坐标表示边的入度（出发点），列坐标表示出度（目标点），[i][j]所在的格子就是连接i和j的边，边的数量最多不多于格子的数量即n*n，n的平方）
（1）最短路径的概念
什么是最短路径问题，这个问题有着大量的生产实际背景。事实上大至海陆空各种运输小至一个人每天上班，都会遇到这一问题。甚至有些问题从表面上看与最短路问题没有什么关系，却也可以归结为最短路问题。
设有一个铁路系统连接着若干城市，x0是系统中的一个固定城市（比如首都或者省会城市），在该系统中试求x0到其他各城市的最短路线，这个问题就称为最短路问题。
我们用一个带权图表示这个铁路系统，权值表示城市之间的铁路里程，于是最短路问题就归结为在带权图中找出顶点x0到其他顶点y且具有最小权的路径。
更一般的最短路问题的提法是：设（D，w）是有正值加权的简单有向图，x0是D中的一个固定顶点，寻找从x0到其他顶点y且具有最小权的有向图。
（2）求图的最短路径算法
求图中两点的最短路径问题，可归结为①源点（起点）固定，终点不确定的两点间最短路径②求图中任意两点间的最短路径。
对于第一类问题，我们经常采用Dijkstra算法；对于第二类问题，我们可以采用Floyd算法。
理论上来说先有Dijkstra算法（1959年）后有Floyd算法（1962年），上面的实际问题也是从第一类问题向第二类问题推广，但是我还是准备先讲Floyd算法再讲Dijkstra算法。因为从“特殊”到“一般”（类似于数学中的“数学归纳法”）需要强大的归纳能力，而从学习者的角度出发从“一般”到“特殊”则要简单许多。
我们先来比较一下两种算法：
Floyd算法是多源最短路算法，时间复杂度为（n的三次方），通常用在点比较少，源点（起点）不固定的问题中，能够解决权值为负的情况。
Dijkstra算法是单源最短路算法，时间复杂度通常为（n的平方），不能够解决权值为负的情况。
Floyd算法
Floyd算法比较简单，就是暴力枚举了所有的可能，将所有可能找遍就知道了两点之间的最短路
参数解释
Chara数组 ：储存两点间的距离，Chara[i][j]的值就是点i到点j的距离。
n：总共有n个点。
p[i][j]:代表对应顶点的最小路径的前驱矩阵
MAX：定义最大值，路不通的情况距离就是MAX
算法思想
很容易理解，我们从一个点i到另一个点j,无非就两种走法
直接从i到j
通过中间点k中转，i->k->j
所以我们就遍历所有情况，如果通过某个中转点距离小于直接到达的距离，就更新这两点间的距离。
if(Chara[i][j] > Chara[i][k] + Chara[k][j])
Chara[i][j] = Chara[i][k] + Chara[k][j];
代码
#define MAX 65535
int Chara[N][N],p[N][N];
int n,m;
void Floyd()
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
p[i][j]=j;//初始化
}
}
for(int k=0;k<n;k++)//中介点
{
for(int i=0;i<n;i++)//起始点源点
{
for(int j=0;j<n;j++)//目标点终点
{
if(Chara[i][k] == MAX || Chara[k][j] == MAX) continue;//暂时不通
if(Chara[i][j] > Chara[i][k] + Chara[k][j])
{
//如果经过下标k顶点路径比原两点间路径更短
//将当前两点权值设为更小的那一个
Chara[i][j] = Chara[i][k] + Chara[k][j];
p[i][j]=p[i][k];//路径设置经过下标k的顶点
}
}
}
}
注：
这里的三重循环相当于先确立（假定）一个中介点，然后穷举源点和终点
每个Chara[i][j]里存放的值是i到j的距离，注意哦i和j是可以不直接相连的甚至可以有多种通路。
Floyd最终穷举了整张图，得到一个n*n的二维表格Chara，整张表格你可以视为是以行坐标i为源点，列坐标j为终点，每个Chara[i][j]的值就是从i到j的最短路的距离。
Dijkstra算法
Dijkstra算法算是贪心思想实现的，首先把起点到所有点的距离存下来找个最短的，然后松弛一次再找出最短的，所谓的松弛操作就是，遍历一遍看通过刚刚找到的距离最短的点作为中转站会不会更近，如果更近了就更新距离，这样把所有的点找遍之后就存下了起点到其他所有点的最短距离，下面仔细讲。
算法思想
在具体讲Dijkstra之前，我们先来做个对比，Floyd算法是穷举了整张图，得到一张二维表，n个点一共n行，第i行的一系列值就表示表示以i为起点到其他各点的最短路径。单源最短路Dijkstra是源点确定时该源点到其他各点的最短路径。聪明的同学一定发现了，哎，这么说来，假如Dijkstra中的源点为i0，那么我在Floyd的二维表找到第i0行不就解决问题了吗？恭喜你，答对了，就是这样。事实上Floyd中的第i0行就是我们所要求的结果。但是在最开始的两种算法的比较中也提到了Floyd的时间复杂度是n的三次方，他把每一行全都求出来了，而许多实际问题中我们只需要特定的那一行，并且在数据较大的时候，在算法竞赛中非常容易超时，此时就需要用到Dijkstra算法了。（由此可见Dijkstra其实就是Floyd的一种特殊情况，所以笔者想采用从一般到特殊的叙述方式）
回想一下刚刚的Floyd是怎么做的，三重循环首先选出中介值k然后穷举起始点i和目标点j。Dijkstra里目标点i确定只需要循环k和j即可，二重循环时间复杂度自然是n的平方了。
那么问题来了，直接在Floyd的三重循环里面删除其中的源点循环就可以了吗？答案是否定的。如果部分同学对上文Floyd有一定疑惑的，此时正好可以讲解，为什么从i到j无非就是两种走法呢？就是因为源点在循环，假设现在有另一种最短的情况是 i可以先走到i2再走到k再走到j，需要经过两个中介点，那么显然在i直接到k的路要比i走到i2再走到k的路要长，所以你才回选择多走一个中介点嘛，这肯定是经过了一次源点为i中介点为i2终点为k的循环。此时你获得了一个方案1【i】【j】=【i】【k】+【k】【j】（其中【i】【k】=【i】【i2】+【i2】【k】经过那次循环【i】【k】里的值得到了更新）。但这不是唯一方案哦，另一种方案2是【i】【j】=【i】【i2】+【i2】【j】（其中【i2】【j】=【i2】【k】+【k】【j】），看，就算是四个点两种方案，但最终都变成了形如if(Chara[i][j] > Chara[i][k] + Chara[k][j]) Chara[i][j] = Chara[i][k] + Chara[k][j];的式子。所以无论怎么走最终都会只有两种情况，即Chara[i][j]和Chara[i][k] + Chara[k][j]。 这个案例中因为要两个中介点都经过所以这两种方案的最终值是相等的。
如果还是这四个点i，i2，k，j，但这次我们的走法是i，i2，j不经过k才是最短路径，那么我们的方案应该是【i】【j】=【i】【i2】+【i2】【j】（【i2】【j】小于【i2】【k】+【k】【j】）这种方案我们单单去掉Floyd算法中的源点循环就会发生错误啦。因为，这里需要判断【i2】【j】小于【i2】【k】+【k】【j】，在Floyd中必然需要做一次源点为i2中介值为k终点为j的判断，但是我们单纯的删掉了源点的循环，源点永远在i永远不会出现在i2的位置上，我们就会与这种方案失之交臂了。
所以我们不能单纯的删除源点的循环，而是要完善思路。
我们提出的改良方案就是在中介点的这个循环时，中介点不能是任取的。在Floyd中这个中介点可以说是任取的，因为我们直接按编号从1到n循环着来取得，并没有去考虑权值的问题。改良的核心思路是（当然了学术史上Dijkstra并非Floyd的改良，这里是从学习者的角度看）按从源点i到其余每个顶点的最短路径升序依次求出从源点到各顶点的最短路径。也就是说现在循环这个中介点的顺序必须是按距离源点的距离升序顺序排列的！接下来的操作就和Floyd类似了，下面请看代码。
参数解释
Chara数组 ：储存两点间的距离，Chara[i][j]的值就是点i到点j的距离。
dis数组：储存起点到各个点的距离，dis[i]就是起点到i点的距离。
vis数组：标记点是否访问过
INF：宏定义的最大值路不通
有两个数组，dis和vis含义参见上面，初始时vis中只有起点，更新dis中的起点到所有点的距离.
遍历所有节点，找到距离起点最近的一个点K，将这个点加入vis中标记
进行松弛操作，遍历没有在vis数组中的其他所有点，比较起点——>该点和起点——>K点——>该点的距离，
重复2-3操作，直到所有的点遍历完
代码
#define INF 65535
int n,m,s,t;
int Chara[N][N],dis[N],vis[N],p[i];
void Dijkstra(int src) //src传入的起点
{
for(int i=0; i<m; i++) //初始化起点到所有点的距离
{
dis[i] = Chara[src][i]; //起始位置到i点的距离
vis[i] = 0;//初始化visit
p[i]=0;
}
dis[src] = 0; //到自身距离为0
vis[src] = 1; //标记 注src=0
for(int i=0; i<m; i++)//i为此二维表的层数（m个点最多m*m条路 i为m层）
{
int ans = INF,k; //INF最大距离 表示不通
for(int j=0; j<m; j++) // 寻找未被访问过距离起点v0最近的点
{
if(!vis[j] && dis[j] < ans)
{
k = j;
ans = dis[j];
}
}//此点为K
vis[k] = 1; //标记已访问
if(ans == INF) break; //表示剩下所有点都不通
for(int j =0; j<m; j++) //松弛操作，更新起点到所有未访问点的距离
{//j为目标点（共有m列）
if(!vis[j] && dis[k] + Chara[k][j]<dis[j] )
{
dis[j] = dis[k] + Chara[k][j];
p[j]=k;//存放前驱节点
}
}
}
}//最后这张表m行 每行一个点 行数越多的点距离越远 即所谓升序排列。
网友评论