一、Dijkstra的用途
Dijkstra算法是用来解决边权不是一,并且是单源最短路问题的。好的,大概率这句话没有看懂。没关系的,接下来将通俗地说明一下。
边权是指边的长度,也就两个点之间的距离。单源指的是从同一个起点出发,前往不同的点。
例如下图所示:
那么从起点到某个点的最短路径问题,就是我们的dijkstra算法需要解决的问题。
二、dijkstra算法思路
(以下将采用逆向思维的方式进行叙述,即将起点看作终点,起点到终点和从终点到起点的最短路一定是一致的。)
1、最短路的性质
最短路,顾名思义就是这条路线是所有能从该点带到终点的路线中,最短的。那么我们可以用下面的图示和数学表达式描述该性质:
(该图中只是描述一下一些关键点,不是具体的路线,中间具体的中转点忽视了,所以这里用的虚线,仅仅表示一段路的起点和终点。)
如果我们不从U到V,那么我们必须先到达另外一个点A(这个A点指的是任意一个能到V的,除了U之外的点),再到V。
由于我们的黑色路径是最短路,那么必定满足下面的关系式:
d[u] :从U到V的最短路径
d[A]:从A到V的路径
W:从U到A的路径
只要我们的d[U]是最短的,那么上面这个式子永远成立!
我们可以证明一下:
假设d[U]是从U到V最短的路径,同时存在另外一个点A,使得该定理不成立:
即d[U]>d[A]+W。那么该式子说明,从U到A再到V的路径小于d[U],但是我们的前提是d[U]是最小值,不可能比这个还小,因此,这个假设不成立。即上述的定理是正确的。
如果一段路径不满足上述的定理,那么这段路就不是最短的,也就是说存在一个点使得:d[U]>d[A]+W。我们发现这个式子的右端是一个新的路径,左端是原来的路径,我们的原来路径竟然比新的路径长,这个事实除了说明当前路径不是最短路之外,还能够用来更新我们的d[U]。我们就可以让:d[U]=d[A]+W。这个过程称之为松弛操作,其实我们可以想象成一根橡皮筋。原来的长度是d[U],绷得很紧,长度很长,但是我们换个路径,松弛一下橡皮筋。那么这个橡皮筋就没有那么紧绷了,长度也适当缩小了。
2、算法思路:
基于上面的定理,我们只要找到某条路径恒满足上面的定理,则该路径就是最短路。
以下面的例子为例:
一开始我们不知道最短路径,所及假设所有点到终点的路是无穷大。而两个未连接的点之间距离也初始化为无穷大。
当前我们所了解的最短路径一定是,终点自身到自身,这个距离是0,这一定是最短路,毋庸置疑,因为边都是正的。
从我们的公式:d[U]<=d[A]+w来看,
如果不是最短路,那么一定存在:d[U] > d[A] + w 。边w都是固定死的,所以我们所用的d[A]越小,这个式子越容易成立。因此我们利用d[终点]=0去松弛所有点。
松弛过后的结果,我们发现只有此时的终点的邻接点得到了有效的更新,即图中的蓝线所覆盖的点,其余依然是无穷(因为:0+无穷=无穷)。
我们这里暂时把这个用来松弛所有点的点,称之为中间点。
因此,我们这样松弛一遍后,改变的点一定是中间点的邻接点,那么我们为什么要这样做?
我们以第一次松弛为例子:
远处的点想要到达终点,必会经过终点的邻接点(即蓝色线覆盖的部分),所以我们前面找到的最短路可能是远处点的最短路径中的一部分。所以我们先找找近处的点的最短路,这样可以在找远处点的时候利用一下这些近处的最短路。
蓝色线枚举出了终点的邻接点,此时,我可以很负责的说,A点的最短路已经确定了。
为什么?
那么根据我们刚才的式子:
d[A]是指除了u之外,其余能到终点的点。
无论怎么走,它想到终点必须经过上图中的蓝色线所覆盖的点的其中之一,这是毋庸置疑的。
为什么?因为想到达终点必过它的邻接点,而我们的蓝色线枚举出了所有的A的邻接点。
(这里用dd[]表示上图中从某点到终点的距离)
那么公式中的d[U]就是图中的dd[A],而公式中的d[A],就是图中的,dd[C]或者dd[D]。
由于dd[A]已经小于了dd[C]和dd[D]。又因为边都是正的,也就是w>0。因此,我们的dd[a]必定恒小于
dd[C]+w,dd[D]+w。因此,这条等式恒成立,所以松弛过后,最短的那条路就是从A到终点的最短路。
可能会有人问,那我不走C和D,我可以走别的点呀,你怎么就知道A先到别的点再到终点是不行的呢?
好,我们假设存在这样的一个假象的路径,满足你的疑问,由于我们在枚举出了和A相连的所有点,即
A,C,D。所以你所假想的路径必定是经过这三个点之一的。
那么你假象的路径必定是这样的:A—>k---->(C或A或D)---->终点。即:dd1+dd2+(dd[C]或dd[A]或dd[D])。我从你这三种可能的路径中选一个最短的:即过A,不过C,D。那么你假象的最短路就是:
dd1+dd2+dd[A]。很明显,这条路径的长度大于我们刚才所得出的最短路:dd[A]。
因此,我们的结论成立,dd[A]就是A点到终点的最短路。
那么,你怎么就知道,D和C有可能没到最短路呢?(以点C为例子)
我们不凭空想象,我们依旧来假设验证一下。我们假设存在一个点S,使得当前的:dd[C]>dd[S]+W(S,C)。其中dd[S]=dd[A]+W[S,A],因为我们的S无法直接到终点,所以我们可以让该点借助一下A点。
那么我们就看此时:dd[C]>dd[A]+W(S,C)+W(S,A)。这个有没有可能成立。答案是有可能的,因为我们的dd[C]>dd[A]。所以当我们的W(S,C)+W(S,A)小于dd[C]-dd[A]的时候,这个等式就成立了。因此是有可能存在这个样的一个点S的。
所以我们并不能保证此时的C和D是最短路径。
那么我们的得到怎样的启示呢?
我们只能保证每次松弛过后的路径中的最小的那个,是最短路。
接着,根据我们刚才的思路:要想剩余的点距离得到减小,必定要让他们完成松弛操作,而松弛操作的前提是:
d[U]>d[A]+W。所以我们的d[A]越小,越容易实现松弛,因此我们用刚刚得到的最短路:dd[A]去实现,即让dd[A]去松弛其余的未确定最短路的点。
松弛过后,我们发现,能够得到有效更新的点,也必定是A点的邻接点。即图中的绿色线所示:
由于其他点不过A,A的邻接点借助A到终点的路径长度已经被我们算出来了,而A的最短路已经确定了。那么A点就没用了。我们可以舍去A点,画出下面的等效图。
此时,我们就可以利用相同的套路了。根据我们刚才的定理:
我们只能保证每次松弛过后的路径中的最小的那个,是最短路。
因此,D到终点的最短路就确定了。
接着我们再利用D去松弛所有未确定的点。周而复始n次。因为松弛一次,能够确定一个点的最短路,所以共需要松弛n次。
这就是dijkstra的思路:
利用最短路的起点去松弛所有点,然后取出最小值,再利用该最小值所在路径的起点去松弛剩余点....
3、算法思想:
我们发现我们松弛的时候,是利用当前已知的最短路去松弛的所有点。这是一种贪心思想。即,我每次做出对当下而言最好的选择,每次都做对当下最好的,那么就有一定的可能从局部最优推出整体最优。
三、Dijkstra的实现
1、问题:
2、代码模板:
#include<iostream>
#include<cstring>
using namespace std;
const int N=510;
int g[N][N],dis[N];
bool s[N];
int n,m,a,b,c;
int dijkstra()
{
memset(dis,0x3f,sizeof dis);
dis[1]=0;
for(int i=1;i<=n;i++)
{
int t=-1;
for(int j=1;j<=n;j++)
{
if(!s[j]&&(t==-1||dis[j]<dis[t]))t=j;
}
s[t]=true;
for(int j=1;j<=n;j++)
{
dis[j]=min(dis[j],g[t][j]+dis[t]);
}
}
if(dis[n]==0x3f3f3f3f)return -1;
else return dis[n];
}
int main()
{
memset(g,0x3f,sizeof g);
scanf("%d%d",&n,&m);
while(m--)
{
scanf("%d%d%d",&a,&b,&c);
g[a][b]=min(g[a][b],c);
}
cout<<dijkstra();
}
3、代码分析:
4、问题解决:
(1)为什么用邻接矩阵
邻接矩阵是一个二维数组,他记录了所有可能存在的边,当边数较少的时候,它会存储很多没用的点。但是现在我们发现边的数量是10的5次方。所以基本上每两个点之间都有边,所以用邻接矩阵几乎不会浪费空间。
四、复杂度分析:
外循环n次,内循环2*n次,所以时间复杂度是O(N^2^)