最短路径之Dijkstra

最短路径算法

  在上一篇文章当中我们讲解了bellman-ford算法和spfa算法,其中spfa算法是我个人比较常用的算法,比赛当中几乎没有用过其他的最短路算法。但是spfa也是有缺点的,我们之前说过它的复杂度是
$O(kE)$,这里的E是边的数量。但有的时候边的数量很多,E最多能够达到$V^2$,这会导致超时,所以我们会更换其他的算法。这里说的其他的算法就是Dijkstra。

Dijkstra算法的前提:

  1. 首先,Dijkstra处理的是带正权值的有权图,那么,就需要一个二维数组(如果空间大用list数组)存储各个点到达(边)的权值大小。(邻接矩阵或者邻接表存储)
  2. 其次,还需要一个bool数组判断那些点已经确定最短长度,那些点没有确定。int数组记录距离(在算法执行过程可能被多次更新)
  3. 需要优先队列加入已经确定点的周围点。每次抛出确定最短路径的那个并且确定最短,直到所有点路径确定最短为止。(优化后)

算法思想

  在上一篇文章当中我们曾经说过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去进行新的松弛,这也就是贪心算法的体现。如果这一层理解了,算法的整个原理也就差不多
了。

我们来整理一下思路来看下完整的算法流程:

  1. 我们用一个数组dis记录源点s到其他点的最短距离,起始时dis[s] = 0,其他值设为无穷大
  2. 我们从未访问过的点当中选择距离最小的点u,将它标记为已访问
  3. 遍历u所有可以连通的点v,如果dis[v] < dis[u] + l[u] [v],那么更新dis[v]
  4. 重复上述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 协议 ,转载请注明出处!