最短路径之Dijkstra
最短路径算法
在上一篇文章当中我们讲解了bellman-ford算法和spfa算法,其中spfa算法是我个人比较常用的算法,比赛当中几乎没有用过其他的最短路算法。但是spfa也是有缺点的,我们之前说过它的复杂度是
$O(kE)$,这里的E是边的数量。但有的时候边的数量很多,E最多能够达到$V^2$,这会导致超时,所以我们会更换其他的算法。这里说的其他的算法就是Dijkstra。
Dijkstra算法的前提:
- 首先,Dijkstra处理的是带正权值的
有权图
,那么,就需要一个二维数组(如果空间大用list数组)存储各个点到达(边)的权值大小。(邻接矩阵或者邻接表存储)
- 其次,还需要一个
bool数组
判断那些点已经确定最短长度,那些点没有确定。int数组
记录距离(在算法执行过程可能被多次更新)
。 - 需要
优先队列
加入已经确定点的周围点
。每次抛出确定最短路径的那个并且确定最短,直到所有点路径确定最短为止。(优化后)
算法思想
在上一篇文章当中我们曾经说过Bellman-ford算法本质上其实是动态规划算法,我们的状态就是每个点的最短距离,策略就是可行的边,由于一共最多要松弛V-1次,所以整体的算法复杂度很高。当我们用队列维护可以松弛的点之后,就将复杂度降到了
$O(kE)$,也就是spfa算法。
Dijkstra算法和Bellman-ford算法虽然都是最短路算法,但是核心的逻辑并不相同。Dijkstra算法的底层逻辑是贪心,也可以理解成贪心算法在图论当中的使用。
其实Dijstra算法和Bellman-ford算法类似,也是一个松弛的过程。即一开始的时候除了源点s之外,其他的点的距离都设置成无穷大,我们需要遍历这张图对这些距离进行松弛。所谓的松弛也就是要将这些距离变小。假设我们已经求到了两个点u和v的距离,我们用
dis[u]表示u到s的距离,dis[v]表示v的距离。
假设我们有dis[u] < dis[v],也就是说u离s更近,那么我们接下来要用一个新的点去搜索松弛的可能,u和v哪一个更有可能获得更好的结果呢?当然是u,所以我们选择u去进行新的松弛,这也就是贪心算法的体现。如果这一层理解了,算法的整个原理也就差不多
了。
我们来整理一下思路来看下完整的算法流程:
- 我们用一个数组dis记录源点s到其他点的最短距离,起始时dis[s] = 0,其他值设为无穷大
- 我们从未访问过的点当中选择距离最小的点u,将它标记为已访问
- 遍历u所有可以连通的点v,如果dis[v] < dis[u] + l[u] [v],那么更新dis[v]
- 重复上述2,3两个步骤,直到所有可以访问的点都已经访问过
怎么样,其实核心步骤只有两步,应该很好理解吧?我找到了一张不错的动图,大家可以根据上面的流程对照一下动图加深一下理解。
我们根据原理不难写出代码:
C++版本:
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510;
int g[N][N];
int dis[N];
int st[N];
int n, m;
int dijkstra() {
memset(dis, 0x3f, sizeof dis);
dis[1] = 0;
for (int i = 0; i < n; ++ i) {
int t = -1;
for (int j = 1; j <= n; ++ j) {
if (!st[j] &&(t == -1 || dis[t] > dis[j])) {
t = j;
}
}
st[t] = true;
for (int j = 1; j <= n; ++ j) {
dis[j] = min(dis[j], dis[t] + g[t][j]);
}
}
if(dis[n] == 0x3f3f3f3f) return -1;
return dis[n];
}
int main() {
scanf("%d%d", &n, &m);
memset(g, 0x3f, sizeof g);
while ( m -- ) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
g[a][b] = min(g[a][b], c);
}
printf("%d", dijkstra());
return 0;
}
Pyhon版本:
INF = sys.maxsize
edges = [[]] # 邻接表存储边
dis = [] # 记录s到其他点的距离
visited = {} # 记录访问过的点
while True:
mini = INF
u = 0
flag = False
# 遍历所有未访问过点当中距离最小的
for i in range(V):
if i not in visited and dis[i] < mini:
mini, u = dis[i], i
flag = True
# 如果没有未访问的点,则退出
if not flag:
break
visited[u] = True
for v, l in edges[u]:
dis[v] = min(dis[v], dis[u] + l)
虽然我们已经知道算法没有反例了,但是还是可以思考一下。主要的点在于我们每次都选择未访问的点进行松弛,有没有可能我们松弛了一个已经访问的点,由于它已经被松弛过了,导致后面没法拿来松弛其他的点呢?
其实是不可能的,因为我们每次选择的都是距离最小的未访问过的点。假设当前的点是u,我们找到了一个已经访问过的点v,是不可能存在dis[u] + l < dis[v]的,因为dis[v]必然要小于dis[u],v才有可能先于u访问。但是这有一个前提,就是每条边的长度不
能是负数。
算法优化
和Bellman-ford算法一样,Dijkstra算法最大的问题同样是复杂度。我们每次选择一个点进行松弛,选择的时候需要遍历一遍所有的点,显然这是非常耗时的。复杂度应该是$O(V^2 + E)$,这里的E是边的数量,Dijkstra中每个点只会松弛一次,也就意味着每条
边最多遍历一次。
我们观察一下会发现,外面这层循环也就算了,里面这层循环很没有必要,我们只是找了一个最值而已。完全可以使用数据结构来代替循环查询,维护最值的场景我们也已经非常熟悉了,当然是使用优先队列。
算法流程
- 一般从选定点开始抛入优先队列。(路径一般为0),
bool数组
标记0的位置(最短为0) , 然后0周围连通的点抛入优先队列中(可能是node类),并把各个点的距离记录到对应数组内(如果小于就更新,大于就不动,初始第一次是无穷肯定会更新)
,第一次就结束了 - 从队列中抛出距离最近的那个点B(第一次就是0周围邻居)。这个点距离一定是最近的(所有权值都是正的,点的距离只能越来越长。)标记这个点为true,
并且将这个点的邻居加入队列
(下一次确定的最短点在前面未确定和这个点邻居中产生),并更新通过B点计算各个位置的
长度,如果小于则更新! - 重复二的操作,直到所有点都确定。
C++版本:
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e6 + 10;
int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[N], heap[N];
bool st[N];
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({0, 1});
while (heap.size())
{
PII t = heap.top();
heap.pop();
int ver = t.second; //distance = t.first;
if (st[ver]) continue;
st[ver] = true;
for (int i = h[ver]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[ver] + w[i])
{
dist[j] = dist[ver] + w[i];
heap.push({dist[j], j});
}
}
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
while (m -- )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
}
printf("%d\n", dijkstra());
return 0;
}
Pyhon版本:
import heapq
import sys
# 优先队列
class PriorityQueue:
def __init__(self):
self._queue = []
self._index = 0
def push(self, item, priority):
# 传入两个参数,一个是存放元素的数组,另一个是要存储的元素,这里是一个元组。
# 由于heap内部默认由小到大排,所以对priority取负数
heapq.heappush(self._queue, (-priority, self._index, item))
self._index += 1
def pop(self):
return heapq.heappop(self._queue)[-1]
def empty(self):
return len(self._queue) == 0
que = PriorityQueue()
INF = sys.maxsize
edges = [[], [[2, 7], [3, 9], [6, 14]], [[1, 7], [3, 10], [4, 15]], [[1, 9], [2, 10], [6, 2], [4, 11]], [[3, 11], [5, 6]], [[4, 6], [6, 9]], [[3, 2], [5, 9]]] # 邻接表存储边
dis = [sys.maxsize for _ in range(8)] # 记录s到其他点的距离
s = 1
que.push(s, 0)
dis[s] = 0
visited = {}
while not que.empty():
u, d = que.pop()
if d != dis[u]:
continue
for v, l in edges[u]:
if dis[u] + l < dis[v]:
dis[v] = dis[u] + l
que.push(v, dis[v])
print(dis)
Java版本:
import java.util.ArrayDeque;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
public class dijkstra {
static class node
{
int x; //节点编号
int lenth;//长度
public node(int x,int lenth) {
this.x=x;
this.lenth=lenth;
}
}
public static void main(String[] args) {
int[][] map = new int[6][6];//记录权值,顺便记录链接情况,可以考虑附加邻接表
initmap(map);//初始化
boolean bool[]=new boolean[6];//判断是否已经确定
int len[]=new int[6];//长度
for(int i=0;i<6;i++)
{
len[i]=Integer.MAX_VALUE;
}
Queue<node>q1=new PriorityQueue<node>(com);
len[0]=0;//从0这个点开始
q1.add(new node(0, 0));
int count=0;//计算执行了几次dijkstra
while (!q1.isEmpty()) {
node t1=q1.poll();
int index=t1.x;//节点编号
int length=t1.lenth;//节点当前点距离
bool[index]=true;//抛出的点确定
count++;//其实执行了6次就可以确定就不需要继续执行了 这句可有可无,有了减少计算次数
for(int i=0;i<map[index].length;i++)
{
if(map[index][i]>0&&!bool[i])
{
node node=new node(i, length+map[index][i]);
if(len[i]>node.lenth)//需要更新节点的时候更新节点并加入队列
{
len[i]=node.lenth;
q1.add(node);
}
}
}
}
for(int i=0;i<6;i++)
{
System.out.println(len[i]);
}
}
static Comparator<node>com=new Comparator<node>() {
public int compare(node o1, node o2) {
return o1.lenth-o2.lenth;
}
};
private static void initmap(int[][] map) {
map[0][1]=2;map[0][2]=3;map[0][3]=6;
map[1][0]=2;map[1][4]=4;map[1][5]=6;
map[2][0]=3;map[2][3]=2;
map[3][0]=6;map[3][2]=2;map[3][4]=1;map[3][5]=3;
map[4][1]=4;map[4][3]=1;
map[5][1]=6;map[5][3]=3;
}
}
这里用visited来判断是否之前访问过的主要目的是为了防止负环的产生,这样程序会陷入死循环,如果确定程序不存在负边的话,其实可以没必要判断。因为先出队列的一定更优,不会存在之后还被更新的情况。如果想不明白这点加上判断也没有关系。
我们最后分析一下复杂度,每个点最多用来松弛其他点一次,加上优先队列的调整耗时,整体的复杂度是$O(V \log V+E)$,比之前$O(V^2+E)$的复杂度要提速了很多,非常适合边很多,点相对较少的图。有时候spfa卡时间了,我们会选择Dijkstra。
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!