算法笔记 - Dijkstra

发表于 | 分类于 ，

哎呀！图片走丢了！

介绍

Dijkstra算法适用于边权为正的图论题中，可以计算正权图上的单源最短路（Single-Source Shortest Paths, SSSP），即从单个源点出发，到所有节点的最短路。Dijkstra同时适用于有向图和无向图。

原理

Dijkstra算法采用了贪心的策略，即尽可能的让没有与源点建立最短通路的点通过当前距离源点最近的点来与源点建立最短通路。

在实现时，我们将已经与源点建立最短通路的点称为标记点，未建立最短通路的点称为未标记点，并用$d[i]$表示第$i$个点到源点的最短距离。

在一次操作中，选取未标记点中距离源点最近的点$i$，将所有与该点相连的未标记点$j$到源点的距离更新为$min(d[j],d[i]+v[i][j])$，然后将点$i$变为标记点，这样的操作称为松弛操作。当操作$n$次后，所有节点都变为标记点，即所有节点都与源点建立了最短通路。

这里有个点需要说明一下：为什么未标记点中$d$值最小的点可以变为标记点？

因为图中所有边的权值均为正（Dijkstra算法适用条件），当$d[i] \le d[1…n]$时，必有$d[i]<d[1…n]+v[1…n][i]$。所以$d[i]$不会再在后续操作中变小，于是可以将点$i$变为标记点。

伪代码

假设起点为0，$v[x][y]$为从$x$到$y$的边的权值。

1
2
3
4
5
6
7
8
清除所有节点的标记
d[0]=0,其他d[i]=INF
循环n次
{
	从所有未标记的顶点中，选出d值最小的节点x
	标记x节点
	对于所有从x出发的边（x，y），更新d[y]=min(d[y],d[x]+v[x][y]);
}
对应程序

再给出伪代码对应的程序，为了方便起见，用$v[x][y]==INF$表示边不存在。

1
2
3
4
5
6
7
8
9
10
11
12
13
memset(vis,0,sizeof(vis));
memset(d,0x3f,sizeof(d));
d[0]=0;
for(int i=0;i<n;i++)
{
	int x,m=INF;
	for(int j=0;j<n;j++)	//找d值最小的点，并用变量x存
		if(!vis[j] && d[j]<=m)
			m=d[x=j];
	vis[x]=1;
	for(int j=0;j<n;j++)
		d[j]=min(d[j],d[x]+v[x][j]);
}

优化

Dijkstra算法中每次需要找出$d$值最小的点，而最暴力的遍历寻找在点非常多的情况下效率非常低，所以我们将优化的重点放在寻找$d$值最小点的方法上。因为会不断的向$d$数列中添加新的数，而且又要随时读取最小值，所以我们可以用优先队列维护$d$数组。

将每次更新后的$d$值放入优先队列，每次弹出队列中第一个点，更新它的出边。因为要得到每个$d$值对应的节点编号，所以需要将$d$值和节点编号“捆绑”在一起放入队列。

STL中的pair就是专门把两个类型“捆绑”在一起的东西。我们可以用
typedef pair<int,int> p自定义一个p类型，则priority_queue<p,vector<p>,greater<p>> q就定义了一个由二元组构成的优先队列。pair默认排序规则是：先排序第一维，相等时才比较第二维，因此要按$(d[i],i)$而不是$(i,d[i])$的方式组合。

另：C++中使用pair需要包含<pair>头文件

再另：当然你自己写优先队列也行，还可以用线段树。

这样一来Dijkstra算法的常用写法就出来了。

对应程序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void Dijkstra(int s)
{
    memset(d,INF,sizeof(d));
    memset(vis,0,sizeof(vis));
    priority_queue<p,vector<p>,greater<p> > q;
    d[s]=0;
    q.push(make_pair(0,s));
    while(!q.empty())
    {
        int x=q.top().second;
        q.pop();
        if(vis[x])
            continue;
        vis[x]=1;
        for(int i=first[x];i;i=Next[i])
        {
            if(d[e[i]]>d[x]+v[i])
            {
                d[e[i]]=d[x]+v[i];
                q.push(make_pair(d[e[i]],e[i]));
            }
        }
    }
}

附录：Dijkstra算法的一些骚操作。

一.打印最短路

Dijkstra算法可以很方便的打印出从起点到终点的最短路，具体方法有两种。

1.采用与打印动态规划的方案相似的方法——从终点出发，沿着$d[i]+v[i][j]==d[j]$的边$(i,j)$从节点$j$倒着走到节点$i$，直到回到起点。

2.用空间换时间。在更新$d$数组时维护一个“父亲指针”。记录下每个节点是从哪个节点走过来的。具体实现时，要将$d[j]=min(d[j],d[x]+v[x][j])$改成

1
2
3
4
5
if(d[j]>d[x]+v[x][j])
{
	d[j]=d[x]+v[x][j];
	fa[j]=x;
}
二.有待发现（嘿嘿嘿）
0%