Dijkstra(迪杰斯特拉)是一个非常基础的算法,也是最常用的,被用于求解图论的最短路问题。但看网上好多教程都写的很复杂,我争取用最易懂的对新手友好的语言来解释清楚这个算法。

使用范围

求解有向带边权图的最短路问题,给定起点,给定边权和起止点,求到达每一个点的最短距离。

算法概述

从起点(由输入给出)开始,遍历所有的和起点直接相连的点,比如现在我们假设1号是起点。

拿上面这张图举例子
首先,把除了起点以外的点的距离都初始化为无限大(INF)(i到起点距离用dist[i]表示)
dist[1] 0 dist[2] INF dist[3] INF dist[4] INF dist[5] INf dist[6] INF
和1直接相连的点是2,那么我们现在把2到起点的距离处理一下,应该是5
dist[1] 0 dist[2] 5 dist[3] INF dist[4] INF dist[5] INf dist[6] INF
以此类推,每次把与 已确定距离的点 相连的点的dist值处理一下就好了
最后我们可以得到下面这张表:
dist[1] 0 dist[2] 5 dist[3] 5+2=7 dist[4] 5+1=6 dist[5] 5+3=8 dist[6] 5+2=7
看上去你已经理解Dijkstra算法的大体思路了,看上去很简单,任何困难的事情都是一点一点做成的。

那么,如果我的图变成这样呢?
我可没有保证没有环

我加了几条边,产生了环,(没错那条边边权就是0)
这样带来的问题就是,每一个点将会有不止一种方法到达。
那我们到底应该怎么办?很简单啊,选到达方式中最优的方案。
我再来手动模拟一下,,,(前半部分和前一个例子相同)

[重点]每一次处理一个点(简称 这个点)时,我们需要枚举它可以到达的点(简称
那个点)的dist值,如果当前算出的距离比那个点原来记录下来的dist值小,就把那个点的dist赋值成当前算出的那个点到起点的距离。

首先,把除了起点以外的点的距离都初始化为无限大(INF)(i到起点距离用dist[i]表示)
我们再引入一个叫vis的数组来记录一个点是否被处理过
dist[1] 0 dist[2] INF dist[3] INF dist[4] INF dist[5] INf dist[6] INF
和1直接相连的点是2,那么我们现在把2到起点的距离处理一下,应该是5
dist[1] 0 dist[2] 5 dist[3] INF dist[4] INF dist[5] INf dist[6] INF
这时候就不同了,我们可以看到,2号点连着4条边,这时

Dijkstra算法要求我们从中按到起点距离的大小 从小到大依次处理这些点。

so,我们应该处理4号点了,这样的话,可以得到下表
dist[1] 0 dist[2] 5 dist[3] dist[4]+3=9 dist[4] dist[2]+1=6 dist[5] INF
dist[6] INF

按顺序,我们处理完4号点该处理3号点了,但我们发现3号点已经有dist值了(9),但我们现在计算出来3号点距离应该是dist[2]+2=7,比原来的要优,所以我们将dist[3]赋值为7。这个操作叫“更新”。
那么我们就可以依次将所有点处理完了。
最后得到:
dist[1] 0 dist[2] 5 dist[3] 7 dist[4] 6 dist[5] 7 dist[6] 7
那么,现在你已经理解了基础的Dijkstra了。

code
//by floatiy #include<iostream> #include<cstdio> #include<vector> using
namespace std; //别问我为什么用longlong 这是洛谷的单源最短路的模板 const long long INF=2147483647;
const int MAXN=10000; const int MAXM=500000; int n,m,s;//n个点 m条边 从第s号点开始 int
node;//当前正在处理的节点 long long minn; long long dist[MAXN];//每个点到起点的距离 bool
vis[MAXN];//是否处理过 struct Edge{//边的结构体 int w;//边权 int pre,to;//pre是出发点 to是终点
这个是有向边 }l[MAXM]; struct Node{//节点的结构体 int num;//以这个点为起点的边的个数 vector<int> about;
//利用stl存以这个点为起点的边的编号,不知道的就把ta当成动态数组吧 }a[MAXN]; int find_new()//每次处理完找新节点的函数 {
for(int i=1;i<=n;i++)//找新的开始点 { if(vis[i]==0 && minn>dist[i])
//从没有处理过的点里找离起点最近的进行处理 { minn=dist[i];//贪心找最小 node=i;//node其实就是下一步要被处理的点的编号 } }
}long long min_(long long x,long long y)//手写min函数更快~ { return x>y?x:y; } int
main() {cin>>n>>m>>s; for(int i=1;i<=n;i++) { dist[i]=INF;//初始化 所有点到起点的距离设成无限大
// cout<<dist[i]<<endl;//DEBUG } int x,y,z; for(int i=1;i<=m;i++)//输入边 { scanf(
"%d%d%d",&x,&y,&z);//依次是 起点 终点 边权 l[i].pre=x,l[i].to=y; l[i].w=z; a[x].num++;
//起点的出度+1 a[x].about.push_back(i);//记录这个边 } dist[s]=0;//起点距离设成0 node=s;//从起点开始处理
while(!vis[node]) { vis[node]=1;//已经处理过了 minn=INF;//每次记得让minn变成无限大
//这里比较难懂,因为我奇怪的双结构体存图方法,我不会前向星。。。 //总之下面这个循环就是枚举一下每一条从node节点出去的边,然后处理它们所连的点的dist
for(int i=0;i<a[node].num;i++)//枚举每条从这个点出去的边在这个点的所有出边中的编号i { if(dist[l[
a[node].about[i] ].to] > dist[node]+l[ a[node].about[i] ].w)//如果出边连到的那个点到起点的距离
//比 //现在这个点到起点的距离+这条边的边权 //要大 //我们就更新连到的这个点的dist值 dist[l[ a[node].about[i]
].to]=dist[node]+l[ a[node].about[i] ].w; } node=find_new();//做完一个点,找下一个点 } for(
int i=1;i<=n;i++) printf("%d ",dist[i]); }
大家尽量去理解,我这个双结构体真的不好理解,建议大家换一种存图的方法。
我太弱了qwq,不会前向星。

堆优化介绍

大家想想,上面的程序有哪里可以大幅度节约时间呢?
每个点的处理是必要的
输入输出也找不到能大幅度降低时间复杂度的办法
那么?


没错,在我们查找新节点的时候,采取的是将每个点都枚举一遍的办法,显然这样会让时间复杂度变成n^2,但我们有一个叫堆的好东西,emmm如果不知道堆排序可以看一下这个,原理很简单的:
堆排序 <https://blog.csdn.net/floatiy/article/details/78805831>
我们建一个小根堆,这样就能很方便的在nlogn的时间内找出最小值了
或者。。如果懒的话可以用一个东西,叫优先队列(STL里的priority_queue)
写一份代码:
这个是在上一份代码的基础上改的,故不加备注了,stl的友元函数重载我也不是很懂,,,大家可以baidu一下。。。
//Dijkstra 堆优化 #include<iostream> #include<cstdio> #include<queue> using
namespace std; const int MAXN=1005; const int MAXM=100005; const int INF=
0xfffffff; int n,m,s; struct Edge{ int to; int next; int w; }l[MAXM]; int
head[MAXN],cnt;int dis[MAXN]; bool vis[MAXN]; struct Node{ int no; int dis;
friend bool operator < (Node x,Node y) { return x.dis < y.dis; } }a[MAXN];
priority_queue<Node> q;void add(int x,int y,int z) { cnt++; l[cnt].to=y;
l[cnt].w=z; l[cnt].next=head[x]; head[x]=cnt; }int main() { cin>>n>>m>>s; int
x,y,z;for(int i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&z); add(x,y,z); add(y,x,z);
}for(int i=1;i<=n;i++) a[i].dis=INF,a[i].no=i; a[s].dis=0; q.push(a[s]);//忘了扔起点
出锅*1 int cur=s; while(!q.empty()) { cur=q.top().no; q.pop(); if(vis[cur])
continue;//注意是看cur是否处理过,而非看to是否处理过 出锅*2 vis[cur]=1; for(int
i=head[cur];i;i=l[i].next) {if(a[l[i].to].dis > a[cur].dis+l[i].w) {
a[l[i].to].dis=a[cur].dis+l[i].w; q.push(a[l[i].to]); } } }for(int i=1
;i<=n;i++) {printf("%d : %d\n",i,a[i].dis); } return 0; }