$ \text{Dijkstra} $ 算法用于解决单源最短路问题的算法之一，是图论较为基础的部分。
- 提示：本文为作者早期时所写，部分内容可能描述不清，过于复杂，包含错误等。
前言
$ \text{Dijkstra} $ 算法用于解决单源最短路问题的算法之一，是图论较为基础的部分。
实现方法：
1.定义ans[100000]，ans[i]代表到达i点的最小花费
2.定义bool数组visit，代表是否来过这里
2.ans[起点]=0,其余的赋值为inf
3.定义一个curr变量，visit[current]=1（访问过），代表现在的位置，初始值为起点。
4.列举所有与curr相联通的的点，将这些点(i)的ans值更新：
$ ans[i]=min(ans[i],ans[curr]+ $ 到这些点需要的花费 $)$
5. 列举所有访问过的的点，找到ans值最小的点，赋值给curr，visit[current]=1（访问过）
6 所有点都访问过（visit[i]都==1），程序结束。此时，ans[i]代表从起点到i的最短路径
伪代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| bool vis[1000000];
int ans[1000000];
int curr=起点;
memset(ans,0x7fffffff,sizeof(ans))
while(vis[curr]==0)
{
vis[curr]=1;
for(int i;列举所有curr连通的点）
{
ans[i]=min(ans[i],ans[curr]+k)
}
int minn=2147483647;
for(int i=1;i<=m;i++)
{
if(vis[i]==1&&ans[i]<minn)
{
minn=ans[i];
curr=i;
}
}
}
|
存图方式
链式前向星
以下是关于链式前向星的介绍 ，会的可以跳过：
边的存储
这种存图方式只需要开一个数组存储每个点引出的第一条边，然后存储每个点作为起点的每条边，这样就可以做到不重不漏。
在链式前向星存图中，我们需要定义一个结构体：
1
2
3
4
5
| struct EDGE
{
int next;
int to;
}edge[1000000];
|
和一个数组：
和一个变量：
你会发现竟然没存起点！！其实起点是用$head$存的
举例：
如图：这样的一个有向图，输入是：
逐步分析：
1.输入1 2，代表1连向2。
1
2
3
| cnt++;
head[1]=cnt;
edge[cnt].to=2;结点1的儿子是2
|
此时：
$cnt=1$
| $edge$ |
$cnt=1$ |
$cnt=2$ |
$ cnt=3$ |
$cnt=4$ |
| $to $ |
$2$ |
$0$ |
$ 0$ |
$0$ |
| $next$ |
$ 0 $ |
$0 $ |
$0$ |
$0$ |
| $head $ |
下标$=1 $ |
下标$=2$ |
下标$=3 $ |
下标$=4 $ |
| 值 |
$1 $ |
$ 0 $ |
$ 0 $ |
$ 0 $ |
2.输入1 3，代表1连向3。
1
2
3
4
5
6
7
8
9
10
| cnt++;
head[1]=cnt;
edge[cnt].to=3;结点1的儿子是3
cnt++;
edge[cnt].to=3;
edge[cnt].next=head[1];
head[1]=cnt;
|
此时：
$cnt=2$
| $edge$ |
$cnt=1$ |
$cnt=2$ |
$ cnt=3$ |
$cnt=4$ |
| $to $ |
$2$ |
$3$ |
$ 0$ |
$0$ |
| $next$ |
$ 0 $ |
$1 $ |
$0$ |
$0$ |
| $head $ |
下标$=1 $ |
下标$=2$ |
下标$=3 $ |
下标$=4 $ |
| 值 |
$2 $ |
$ 0 $ |
$ 0 $ |
$ 0 $ |
3.输入1 4，代表1连向4。
此时：
$cnt=3$
| $edge$ |
$cnt=1$ |
$cnt=2$ |
$ cnt=3$ |
$cnt=4$ |
| $to $ |
$2$ |
$3$ |
$ 4$ |
$0$ |
| $next$ |
$ 0 $ |
$1 $ |
$2$ |
$0$ |
| $head $ |
下标$=1 $ |
下标$=2$ |
下标$=3 $ |
下标$=4 $ |
| 值 |
$3 $ |
$ 0 $ |
$ 0 $ |
$ 0 $ |
4.输入2 3，代表2连向3。
此时：
$cnt=4$
| $edge$ |
$cnt=1$ |
$cnt=2$ |
$ cnt=3$ |
$cnt=4$ |
| $to $ |
$2$ |
$3$ |
$ 4$ |
$3$ |
| $next$ |
$ 0 $ |
$1 $ |
$2$ |
$0$ |
| $head $ |
下标$=1 $ |
下标$=2$ |
下标$=3 $ |
下标$=4 $ |
| 值 |
$3 $ |
$ 4 $ |
$ 0 $ |
$ 0 $ |
注意：$edge[cnt].next$ 和$head[1]$存贮的都是结构体下标（即$cnt$的值）若要访问指向的边的编号，分别用$edge[edge[cnt].next].to$，$edge[head[1]].to$
若需要记录权值，在结构体中加入一个元素即可
代码：(带权值）
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
| #include<iostream>
using namespace std;
struct edge
{
int next;
int to;
int wei;
}edge[MAXM];
int head[MAXN];
int cnt=0;
void addedge(int u,int v,int w)
{
edge[++cnt].next=head[u];
edge[cnt].to=v;
edge[cnt].w=w;
head[u]=cnt;
}
int main()
{
int n;
for(int i=1;i<=n;i++)
{
int a,b,wei;
addedge(a,b,wei);
}
}
|
注意：
这里的next指的是遍历时的下一条边，head指的是遍历时的第一条边，而存边时相当于反过来操作，所以next记录上一条边，而head记录最后一条边。
边的遍历
在遍历以x为起点的所有边时，只需要这样就行
for(int i=head[x];i!=0;i=edge[i].next)
这个循环的结束条件是i等于0，因为最后一条边，也就是存边时第一条边，在把head值存进next时，head还没有更新过，也就是0。所以当next返回0时，就说明这些边遍历完毕了。
优势与特点
既可以存图，也可以存树，比起邻接矩阵，链式前向星的空间复杂度是O（n），大大节省了存储空间，因为按边存储省掉了很多两点无边的空间。并且在遍历的时候，那些与起点无边相连的点也不需要进行处理，可以说时间和空间都占优势，这就是被OIer们广泛使用的原因。
代码
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
| #include<iostream>
using namespace std;
int head[100000],cnt;
long long ans[1000000];
bool vis[1000000];
int m,n,s;
struct edge
{
int to;
int nextt;
int wei;
}edge[1000000];
void addedge(int x,int y,int z)
{
edge[++cnt].to=y;
edge[cnt].wei=z;
edge[cnt].nextt=head[x];
head[x]=cnt;
}
int main()
{
cin>>m>>n>>s;
for(int i=1;i<=n;i++)
{
ans[i]=2147483647;
}
ans[s]=0;
for(int i=1;i<=n;i++)
{
int a,b,c;
cin>>a>>b>>c;
addedge(a,b,c);
}
int pos=s;
while(vis[pos]==0)
{
long long minn=2147483647;
vis[pos]=1;
for(int i=head[pos];i!=0;i=edge[i].nextt)
{
if(!vis[edge[i].to]&&ans[edge[i].to]>ans[pos]+edge[i].wei)
{
ans[edge[i].to]=ans[pos]+edge[i].wei;
}
}
for(int i=1;i<=m;i++)
{
if(ans[i]<minn&&vis[i]==0)
{
minn=ans[i];
pos=i;
}
}
}
for(int i=1;i<=m;i++)
{
cout<<ans[i]<<' ';
}
}
|
以上是Dijkstra的基础介绍，上面的这份代码是不加优化的Dijkstra，能通过
P3371单源最短路径（弱化版）
不过在这道题中会TLE。
优化
在上面第五步中：
5. 列举所有访问过的的点，找到ans值最小的点
这一步由于每次都要遍历一遍所有点，复杂度为$O(n)$
不过可以用堆（STL：优先队列）进行优化，复杂度为$O(logn)$
简单介绍优先队列
一种数据结构，支持找出数列中最大值，弹出最大值
重载运算符后还可以维护最小值
头文件
定义
加入
弹出最大值
查询最大值
详细的可看P3378 【模板】堆
代码
对以上代码加入堆优化：
由于每个点有两个值需要存储（$ans$值，点的编号）,所以要用结构体
由于要找最小的点，所以用优先队列时需要重载运算符：
1
2
3
4
5
6
7
8
9
| struct node
{
int ans;
int id;
bool operator <(const node &x)const
{
return x.ans<ans;
}
};
|
代码：
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
70
71
72
73
74
75
76
| #include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int head[100000],cnt;
long long ans[1000000];
bool vis[1000000];
int m,n,s;
struct edge
{
int to;
int nextt;
int wei;
}edge[1000000];
struct priority
{
int ans;
int id;
bool operator <(const priority &x)const
{
return x.ans<ans;
}
};
void addedge(int x,int y,int z)
{
edge[++cnt].to=y;
edge[cnt].wei=z;
edge[cnt].nextt=head[x];
head[x]=cnt;
}
priority_queue<priority> q;
int main()
{
cin>>m>>n>>s;
for(int i=1;i<=n;i++)
{
ans[i]=2147483647;
}
ans[s]=0;
for(int i=1;i<=n;i++)
{
int a,b,c;
cin>>a>>b>>c;
addedge(a,b,c);
}
int u;
q.push((priority){0,s});
while(!q.empty())
{
priority temp=q.top();
q.pop();
u=temp.id;
if(!vis[u])
{
vis[u]=1;
for(int i=head[u];i;i=edge[i].nextt)
{
int v=edge[i].to;
if(ans[v]>ans[u]+edge[i].wei)
{
ans[v]=ans[u]+edge[i].wei;
if(!vis[v])
{
q.push((priority){ans[v],v});
}
}
}
}
}
for(int i=1;i<=m;i++)
{
cout<<ans[i]<<' ';
}
}
|
