dijkstra

　

dijkstra

前言

• SPFA" role="presentation">SPFA$SPFA$算法由于它上限 O(NM)=O(VE)" role="presentation">O(NM)=O(VE)$O(NM)=O(VE)$的时间复杂度,被卡掉的几率很大.在算法竞赛中,我们需要一个更稳定的算法:dijkstra" role="presentation">dijkstra$dijkstra$.

什么是dijkstra" role="presentation">dijkstra$dijkstra$?

• dijkstra" role="presentation">dijkstra$dijkstra$是一种单源最短路径算法,时间复杂度上限为O(n2)" role="presentation">O(n2)$O(n^2)$(朴素),在实际应用中较为稳定;" role="presentation">;$;$加上堆优化之后更是具有O((n+m)log2⁡n)" role="presentation">O((n+m)log2n)$O((n+m){\log }_{2}n)$的时间复杂度,在稠密图中有不俗的表现.

dijkstra" role="presentation">dijkstra$dijkstra$的原理/流程?

• dijkstra" role="presentation">dijkstra$dijkstra$本质上的思想是贪心,它只适用于不含负权边的图.
• dijkstra" role="presentation">dijkstra$dijkstra$的流程如下:" role="presentation">:$:$
• 1." role="presentation">1.$1.$ 初始化dis[start]=0," role="presentation">dis[start]=0,$dis[start]=0,$其余节点的dis" role="presentation">dis$dis$值为无穷大.
• 2." role="presentation">2.$2.$ 找一个未被标记的,dis" role="presentation">dis$dis$值最小的节点x," role="presentation">x,$x,$标记节点x." role="presentation">x.$x.$
• 3." role="presentation">3.$3.$ 遍历x" role="presentation">x$x$的所有出边(x,y,z)," role="presentation">(x,y,z),$(x,y,z),$若dis[y]>dis[x]+z," role="presentation">dis[y]>dis[x]+z,$dis[y]>dis[x]+z,$则令dis[y]=dis[x]+z" role="presentation">dis[y]=dis[x]+z$dis[y]=dis[x]+z$
• 4." role="presentation">4.$4.$ 重复2,3" role="presentation">2,3$2,3$两步,直到所有点都被标记." role="presentation">.$.$
• 时间复杂度为O(n2)" role="presentation">O(n2)$O(n^2)$

图解

• 我们把点分成两类,一类是已经确定最短路径的点,称为”白点”,另一类是未确定最短路径的点,称为”蓝点”
• (令start=1" role="presentation">start=1$start=1$)
• 开始时我们把dis[start]" role="presentation">dis[start]$dis[start]$初始化为0" role="presentation">0$0$,其余点初始化为inf" role="presentation">inf$inf$

  

• 第一轮循环找到dis" role="presentation">dis$dis$值最小的点1" role="presentation">1$1$,将1" role="presentation">1$1$变成白点,对所有与1" role="presentation">1$1$相连的蓝点的dis" role="presentation">dis$dis$值进行修改,使得dis[2]=2,dis[3]=4,dis[4]=7" role="presentation">dis[2]=2,dis[3]=4,dis[4]=7$dis[2]=2,dis[3]=4,dis[4]=7$

  

• 第二轮循环找到dis" role="presentation">dis$dis$值最小的点2" role="presentation">2$2$,将2" role="presentation">2$2$变成白点,对所有与2" role="presentation">2$2$相连的蓝点的dis" role="presentation">dis$dis$值进行修改,使得dis[3]=3,dis[5]=4" role="presentation">dis[3]=3,dis[5]=4$dis[3]=3,dis[5]=4$

  

• 第三轮循环找到dis" role="presentation">dis$dis$值最小的点3" role="presentation">3$3$,将3" role="presentation">3$3$变成白点,对所有与2" role="presentation">2$2$相连的蓝点的dis" role="presentation">dis$dis$值进行修改,使得dis[4]=4" role="presentation">dis[4]=4$dis[4]=4$

  

• 接下来两轮循环分别将4,5" role="presentation">4,5$4,5$设为白点,算法结束,求出所有点的最短路径
• 时间复杂度O(n2)" role="presentation">O(n2)$O(n^2)$

为什么dijkstra" role="presentation">dijkstra$dijkstra$不能处理有负权边的情况?

• 我们来看下面这张图

  

• 2" role="presentation">2$2$到3" role="presentation">3$3$的边权为−4" role="presentation">−4$-4$,显然从1" role="presentation">1$1$到3" role="presentation">3$3$的最短路径为−2" role="presentation">−2$-2$(1−>2−>3)." role="presentation">(1−>2−>3).$(1->2->3).$但在循环开始时程序会找到当前dis" role="presentation">dis$dis$值最小的点3" role="presentation">3$3$,并标记它为白点.
• 这时的dis[3]=1," role="presentation">dis[3]=1,$dis[3]=1,$然而1" role="presentation">1$1$并不是起点到3" role="presentation">3$3$的最短路径.因为3" role="presentation">3$3$已经被标为白点,所以dis[3]" role="presentation">dis[3]$dis[3]$不会再被修改了.我们在边权存在负数的情况下得到了错误的答案.

dijkstra" role="presentation">dijkstra$dijkstra$的堆优化?

• 观察dijkstra" role="presentation">dijkstra$dijkstra$的流程,发现步骤2" role="presentation">2$2$可以优化
• 怎么优化呢?
• 我会zkw线段树!我会斐波那契堆!
• 我会堆!

• 我们可以用堆对dis" role="presentation">dis$dis$数组进行维护,用O(log2⁡n)" role="presentation">O(log2n)$O({\log }_{2}n)$的时间取出堆顶元素并删除,用O(log2⁡n)" role="presentation">O(log2n)$O({\log }_{2}n)$遍历每条边,总复杂度O((n+m)log2⁡n)" role="presentation">O((n+m)log2n)$O((n+m){\log }_{2}n)$

• 范例代码:

#include<bits/stdc++.h>

const int MaxN = 100010, MaxM = 500010;

struct edge
{
    int to, dis, next;
};

edge e[MaxM];
int head[MaxN], dis[MaxN], cnt;
bool vis[MaxN];
int n, m, s;

inline void add_edge( int u, int v, int d )
{
    cnt++;
    e[cnt].dis = d;
    e[cnt].to = v;
    e[cnt].next = head[u];
    head[u] = cnt;
}

struct node
{
    int dis;
    int pos;
    bool operator <( const node &x )const
    {
        return x.dis < dis;
    }
};

std::priority_queue<node> q;


inline void dijkstra()
{
    dis[s] = 0;
    q.push( ( node ){0, s} );
    while( !q.empty() )
    {
        node tmp = q.top();
        q.pop();
        int x = tmp.pos, d = tmp.dis;
        if( vis[x] )
            continue;
        vis[x] = 1;
        for( int i = head[x]; i; i = e[i].next )
        {
            int y = e[i].to;
            if( dis[y] > dis[x] + e[i].dis )
            {
                dis[y] = dis[x] + e[i].dis;
                if( !vis[y] )
                {
                    q.push( ( node ){dis[y], y} );
                }
            }
        }
    }
}


int main()
{
    scanf( "%d%d%d", &n, &m, &s );
    for(int i = 1; i <= n; ++i)dis[i] = 0x7fffffff;
    for( register int i = 0; i < m; ++i )
    {
        register int u, v, d;
        scanf( "%d%d%d", &u, &v, &d );
        add_edge( u, v, d );
    }
    dijkstra();
    for( int i = 1; i <= n; i++ )
        printf( "%d ", dis[i] );
    return 0;
}

例题

• 入门模板:P3371
• 进阶模板:P4779
• 其余例题请右转洛谷题库,搜索”最短路”

后记

• 本文部分内容摘自李煜东《算法竞赛进阶指南》和《信息学竞赛一本通》
• 友情提示:正权图请使用dijkstra" role="presentation">dijkstra$dijkstra$算法,负权图请使用SPFA" role="presentation">SPFA$SPFA$算法

相关阅读

Dijkstra算法

迪杰斯特拉算法可以用来求图的最短路径，本文通过对一个无向图最短路径的求取问题来讲解迪杰斯特拉算法。假如有无向图如下： 首先我