Dijkstra算法详解

2021-12-07 00:01:28

今天给大家讲解\(dijkstra\)图论最短路算法

在讲解\(dijkstra\)算法之前,先来给大家讲解一下图论中的松弛操作。

松弛,即\(relaxtion\),是一种编程学术语。

举例说明，例如我们可以从某个机场坐飞机达到若干个机场，然后从这些机场出发，我们又需做火车前往若干个城镇。现在假设我们手里有飞行时间表（\(list\) 或者 \(dict\)），而 \(A_u\) 表示的是从当前位置出发，我们到达 \(u\) 机场所需的时间。类似地，我们用 \(b_{uv}\) 来表示坐火车从 u 机场到达 v 城镇所需的时间（B 自然为 \(list\) \(of\) \(lists\) 或 \(dict\)）。下面我们从到达各镇的路径中随机选择一条，它所需的时间为 \(C_v\)：

C[v] = float('inf')
for u in A:
    C[v] = min(C[v], A[u]+B[u][v]) //

松弛法（relaxation）是一数学术语，描述的是一些求解方法，这些方法会通过逐步接近的方式获得相关问题的最佳解法。每运用一次松弛法就好像我们“移动”了一次，而我们要做的就是在尽可能少的移动次数内找到最佳解决方案。

理论上来说，我们可以在整个空间上运用相关的松弛法，但关键在于找到一个正确的执行次序。

讲完了松弛法,接下来就给大家讲解\(dijkstra\)算法

(1).\(dijkstra\)算法解决问题范围

\(dijkstra\)算法主要解决的是单源点的最短路和最短路径问题,
且路径的权值不为负权。

(2).\(dijkstra\)算法思想及原理

\(dijkstra\)算法思想是基于贪心算法思想的。所谓贪心算法即始终保持当前迭代解为当前最优解。意思就是在已知的条件下或是当前拥有的全部条件下保证最优解，若在此后的迭代中由于加入了新的条件使得产生了更优解则替代此前的最优解。通过不断的迭代不断保证每次迭代的结果都是当前最优解，那么当迭代到最后一轮时得到的就会是全局最优解。由于下一轮迭代会参考上一轮的最优解，因此每一轮的迭代的工作量基本一致，降低了整体工作的复杂性。

(3).\(dijkstra\)算法描述

我们假设现在要求出\(k\)点到其他点的距离。

首先将\(k\)点加入一个集合,让他在集合标记为已知,意思就是已经确定\(k\)点到达该点的最短路径,没有标记为已知的点就默认为在未知集合。

然后运用\(k\)进行松弛他的后继节点。

接着找出在未知集合中里找出距离\(k\)最近的点,将它设为新的起点\(k\)。

最后就重复以上流程\(n\)次(\(n\)为顶点数)。

(4).\(dijkstra\)算法具体流程

(5).\(dijkstra\)算法的优化

我们发现,普通的\(dijkstra\)算法中,“寻找距离\(k\)最近的一个点”这一步我们可以进行优化。我们可以把已知的点和到起点的距离放进一个优先队列里,然后每次取出队头的那个点来当作起点进行下面的操作(队头的点应是到起点距离最小的点,要变动一下排序规则)

(6).\(dijkstra\)算法核心代码

优化前:

void Dijkstra(int k1)
{
    //vis为已知集合,dis表示k1到其他点的最小距离
    memset(dis,0x3f,sizeof(vis));
    vis[k1]=1;
    dis[k1]=0;
    for(int i=1;i<m;++i)
    {
        for(int j=fst[k1];j;j=arr[j].nxt)//链式前向星
        {
           //松弛
            int tmp=arr[j].u;
            if(dis[k1]+arr[j].v<dis[tmp])
            {
                dis[tmp]=dis[k1]+arr[j].v;
                last[tmp]=k1;
            }
        }
        int mid=0x3f3f3f3f;
        //寻找距离起点最小的点
        for(int j=1;j<=m;++j)
        {
            if(vis[j]==0&&dis[j]<mid)
            mid=dis[j],k1=j;
        }
        vis[k1]=1;
    }
}

优化后:

dis[s]=0;
q.push(make_pair(0,s));
while(!q.empty())//排序规则请运用结构体重载自己设定,这里不做阐述
{
    int x=q.top().second;//取出点
    q.pop();
    if(vis[x]==1)//如果这个点已经被压入队列过,不执行这一次循环。
        continue;
    vis[x]=1;
    //松弛
    for(int i=head[x];i;i=e[i].next)
    {
        int y=e[i].to,z=e[i].w;
        if(dis[x]+z<dis[y])
        {
            dis[y]=dis[x]+z;
            q.push(make_pair(-dis[y],y));//将所有距离和点压入队列
        }
    }
}

(7).\(dijkstra\)算法时间复杂度

普通\(dijkstra\):\(O(n^2)\)

优化后的\(dijkstra\):\(O(nlogn)\)

(8).\(dijkstra\)输出路径

dis[s]=0;
q.push(make_pair(0,s));
while(!q.empty())
{
   int x=q.top().second;
   q.pop();
   if(vis[x]==1)
       continue;
   vis[x]=1;
   for(int i=head[x];i;i=e[i].next)
   {
       int y=e[i].to,z=e[i].w;
       if(dis[x]+z<dis[y])
       {
           dis[y]=dis[x]+z;
           last[y]=x;
           q.push(make_pair(-dis[y],y));
       }
   }
}
void print(int t)
{
    if(last[t])
    print(last[t]);
    cout<<t<<" ";
}

以上就是\(dijkstra\)算法的全部内容了,希望大家有所收获

参考资料:

unique_pursuit的dijkstra算法详解（迪杰斯特拉算法）简单易懂

Nicola-Zhang的relaxation（松弛法）定义理解

码农公寓