浅谈算法之Dijkstra

Dijkstra算法是典型的单源最短路径算法,也就是用于计算一个节点到其他节点的最短路径的算法。它的主要特点为以起始点中心,层层扩展。利用贪心的思想不断更新最短路。

算法主要思路

取起点$s$,引入集合$S$和$U$,$S$中为已求出最短路径的节点(最短路径已确定),$U$中为未求出最短路径的节点。记节点$v$到$s$的距离为$dis[v]$

易知初始时$S$中只有一个元素$s$,$dis[s]=0$,其余节点均在$U$中,$U$中与$s$相邻的节点到$s$的距离为边权,与$s$不相邻的节点到s的距离未知,视为$+\infty$。

此时从$U$中找到$dis[k]$最小的节点$k$,显然$k$的最短路径已求出,则将$k$从$U$中移到$S$中。

于是可以用$k$更新$U$中节点距离,由于与$k$相邻且不与$s$相邻的其它节点距离均为$+\infty$,故能更新。(实际实现中,称为松弛)

重复以上步骤,直至$U$为空集。

图解

dij.png

(该图为LuoguP4779样例图示,graphviz制作)

工作量稍大先坑着了。

代码实现

松弛,严格来讲并不属于最短路算法,却是该算法的核心部分

1
2
if(dis[u]+G[u][i].w < dis[v])
dis[v] = dis[u]+G[u][i].w//G[u][i]是一条从u指向v的边

堆优化代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
using std::vector;
using std::priority_queue;
const int MAXN = 100010;
const int MAXM = 200010;
int dis[MAXN];
int m,n,s;
struct edge
{
int u,v,w;

};vector<edge> G[MAXM];
struct node
{
int u,d;
bool operator <(const node& rhs) const {
return d>rhs.d;
}
};
void addEdge(int u,int v,int w)
{
edge newe;
newe.u = u,newe.v = v,newe.w = w;
G[u].push_back(newe);
}
void dijkstra()
{
for(int i = 1;i <= n;i ++)
dis[i] = 1000000000;
dis[s] = 0;
priority_queue<node> Q;
Q.push((node){s,0});
while(!Q.empty())
{
node nown = Q.top();
Q.pop();
int &u = nown.u,&d = nown.d;
if(d != dis[u])//证明在此节点被取出之前u的最短路已被更新,则跳过这个节点
continue;
for(int i = 0;i < G[u].size();i ++)
{
int &w = G[u][i].w,&v = G[u][i].v;
if(dis[u]+G[u][i].w < dis[v])
{
dis[v] = dis[u]+w;
Q.push((node){v,dis[v]});
}
}
}
}
int main()
{
scanf("%d%d%d",&n,&m,&s);
for(int i = 0;i < m;i ++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
addEdge(u,v,w);
}
dijkstra();
for(int i = 1;i <= n;i ++)
{
printf("%d ",dis[i]);
}
return 0;
}