您的位置: 首页  >  文章  >  详解Dijkstra算法（含数学证明和优化）

详解Dijkstra算法（含数学证明和优化）

分类: 文章 • 2025-05-26 13:48:28

Dijkstra算法简介：

Dijkstra算法是由荷兰计算机科学家Edsger Wybe Dijkstra于1959年提出的一种解决有向加权图中单源最短路问题的算法，其中要求加权图中不可有负权边。

Dijkstra算法步骤演示：

  • 以如下的一张有向正权图G为例，规定：
    • 起点为A
    • 向量xy→表示从顶点x到顶点y的有向边
    • 向量的模∣∣xy→∣∣表示有向边xy→的权值

详解Dijkstra算法（含数学证明和优化）

  • 初始状态：
    　　设起点到各点当前最短距离为Lk(k=A,B,C,D,E)，则有：
    LA=0

    并设此时
    LB至LE=+∞

    则可列表：
  LA LB LC LD LE
初始状态 0 +∞ +∞ +∞ +∞



  • 第一次迭代：
    　　从起点A点出发，更新起点到A的邻居（B、C、D）的当前最短距离（Lk）。此时：
    对B：
    LB=∣∣∣AB→∣∣∣=10
    对C：
    LC=∣∣∣AC→∣∣∣=3
    对D：
    LD=∣∣∣AD→∣∣∣=20

    则可列表：
  LA LB LC LD LE
第一次迭代后 0 10 3 20 +∞



  • 第二次迭代：
    　　找出第一次迭代后除已处理过的起点A外，Lk最小的点：C
    　　从C出发，更新C邻居（B、E）的Lk值，此时：
    对B：
    　　经过C到达B的路径长度：
    L=LC+∣∣∣CB→∣∣∣=5
    ∵LB=10>L
    ∴更新LB=L=LC+∣∣∣CB→∣∣∣=5

    对E：
    　　经过C到达E的路径长度：
    L=LC+∣∣∣CE→∣∣∣=18
    ∵LE=+∞>L
    ∴更新LE=L=LC+∣∣∣CE→∣∣∣=18

    则可列表：
  LA LB LC LD LE
第二次迭代后 0 5 3 20 18



  • 第三次迭代：：
    　　找出第二次迭代后，除已处理过的A、C两点外，Lk最小的点：B
    　　从B出发，更新B邻居（D）的Lk值，此时：
    对D：
    　　经过B到达D的路径长度：
    L=LB+∣∣∣BD→∣∣∣=10
    ∵LD=20>L
    ∴更新LD=L=LB+∣∣∣BD→∣∣∣=10

    则可列表：
  LA LB LC LD LE
第三次迭代后 0 5 3 10 18



  • 第四次迭代：
    　　找出第三次迭代后，除已处理过的A、B、C三点外，Lk最小的点：D
    　　从D出发，更新D邻居（E）的Lk值，此时：
    对E：
    　　经过D到E的路径长度：
    L=LD+∣∣∣DE→∣∣∣=21
    ∵LE=18<L
    ∴不必更新，LE=18

    则可列表：
  LA LB LC LD LE
第四次迭代后 0 5 3 10 18



  • 第五次迭代：
    　　找出第四次迭代后，除已处理过的A、B、C、D四点外，Lk最小的点：E
    　　此时，E没有邻居，因此对E的处理直接结束
    　　
    则可列表：
  LA LB LC LD LE
第五次迭代后 0 5 3 10 18



  • 五次迭代后，有向图G中所有的点都被处理过，算法终止，则整个迭代过程列表如下：
  LA LB LC LD LE
初始状态 0 +∞ +∞ +∞ +∞
第一次迭代后 0 10 3 20 +∞
第二次迭代后 0 5 3 20 18
第三次迭代后 0 5 3 10 18
第四次迭代后 0 5 3 10 18
第五次迭代后 0 5 3 10 18

　　不难观察到，Dijkstra算法的特点主要是从起点开始，“由近及远，层层扩展”，越靠前处理的点离起点越近，最后一个处理的点一定离起点最远。
　　所以，依据算法每找到一个顶点后，该顶点对应的Lk值就是起点到该点的最短路径长度，且Lk在这之后不会被更改。
　　而最后一次迭代得到的所有Lk的值，就是由起点（亦称源点）A到各点的最短路径长度。
　　故Dijkstra算法解决的是有向图中的单源最短路问题。

算法概括：

  1. 步骤概括：

    • 第一个核心步骤：找到当前未处理过的顶点中Lk最小的点V，（由于起点到起点的消耗为0，所以算法开始时V必定代表起点）；
    • 第二个核心步骤：若V有邻居，则计算经过V的情况下起点到达各邻居的消耗L，并选择是否更新V邻居的Lk值。若没有邻居则对该点的处理结束
    • 重复以上两个核心步骤，直到满足算法终止的条件：有向图中所有的点都被处理过。

  2. 流程图：

Created with Raphaël 2.1.0开始找到符合条件的V更新V的所有邻居图中所有顶点都被找到过？结束yesno

数学描述及证明

  • Dijkstra算法的数学描述：
    设全集U：有向图中所有的点的集合。
    设点集S ：已经找到最短路径的点的集合，初始状态下设仅有 起点∈S。
    设点集Q：还未找到最短路径的点的集合，显然Q=U−S。
    设Lk为当前情况下，起点经过S中若干点到点k的最短距离（k∈U），初始L起点=0，其他均为+∞。
    算法开始：
    • 从起点开始，沿某条弧（设权值为arcs）找到起点的一个邻居n
    • 令Ln=min{Ln,L起点+arcs}
    • 按此方式更新起点所有邻居
    • 在集合Q中找到Lk最小的点v，则Lv即起点到v的最短路径长度
    • 将点v从Q中取出加入S，对点v重复上述所有操作
    • 如此重复，直到S=U，即Q=∅时，算法结束，Lk即为从起点到各点的最短路径长度

提醒：这里读者一定要反复仔细体会Lk的含义，它不断更新的过程正是Dijkstra算法“由近及远，层层扩展”特点的体现。同时思考一下之前提过的“找到一个点后，该点Lk值肯定不会被更改”的原因（理解Lk的含义后，原因其实是显而易见的）。

  • Dijkstra算法的数学证明：
    由算法的数学描述，可知：
    只有命题：“每次从Q集中找到Lk最小的点v，Lv即为从起点到v的最短路径长度”正确时，算法正确。
    可用广义数学归纳法证明，设起点为o：

    • 证明：算法找到的第一个点为v1，Lv1即为从起点到v1的最短路径长度。
      用反证法：
      ∵算法找到的第一个点一定是起点o最近的邻居
      假设Lv1不是从起点到v1的最短路径长度
      则∃点v，使得∣∣ov→∣∣<∣∣ov1→∣∣，与已知矛盾
      故假设不成立，子命题得证
    • 证明：已用算法从Q中依次找到了v1,v2,⋯,vk共k个点，且Lv1,Lv2,⋯,Lk是起点到各点的最短路径长度，则此时从Q中依照算法再找一个点vk+1，Lk+1即为起点到vk+1的最短路径长度。
      用反证法：
      假设Lk+1不是起点到vk+1最短路径的长度
      所以设起点到vk+1的最短路径经过的点的集合为V，路径长度为L，则有L<Lk+1
      ∵由Lk的含义⇒V∩Q≠∅
      又∵o∈V且o∈S⇒V∩S≠∅
      则设到vk+1的最短路径中，最靠近vk+1且不属于S的点为vx，vx的后继为vy
      ∵有向图中边均为正权边
      ∴必有Lvx<Lvy⩽L，vy为vk+1时等号成立
      又∵vx∉S⇒Lvx>Lk+1，产生矛盾
      故假设不成立，子命题得证

    综上所述，该命题得证，故算法正确。

关于负权边

Dijkstra算法要求有向图中不得有负权边，如果图中有负权边，则在之前的证明过程中：

∵Lvx<Lvy不一定成立（Lvy⩽L依然成立）

∴Lvx>Lk+1不一定成立

故此时算法正确性不得证。

这里举一个简单的例子供读者自行对照理解：
详解Dijkstra算法（含数学证明和优化）

时间复杂度

设有向图中，共有V个顶点，E条边。
传统Dijkstra算法中主要操作有：

  1. 每次从Q集中找到Lk最小的点，最坏情况下需：
    (V−1),(V−2),⋯,1

    次操作。
    所以整个算法过程共需：
    (V−1)+(V−2)+⋯+1=(v−1)v2=V22−12

    次操作。
  2. 计算并更新各点邻居的Lk值，实质上是将所有的边遍历一遍，故需E次操作。
    则用大O表示法:
    O(V22−12+E)⇔O(n2)

    故传统Dijkstra算法的时间复杂度为O(n2)

Dijkstra算法的优化

在上述对于传统Dijkstra算法的时间复杂度分析中，我们可知，（尤其是稀疏图中）从Q集中找到Lk最小的点的过程极大影响了算法的性能，这个过程在顶点无序状态下需要O(n2)的复杂度。
因此对于顶点的有效排序可以大大地提高算法的性能，常用的方法有：小顶堆或优先队列：

  • 小顶堆优化中，我们初始将所有顶点设置为一个小顶堆，此时堆顶一定为起点，而在每一次迭代中，我们将堆顶元素取出（复杂度O(1)），而后调整小顶堆（复杂度O(logn)），这样调整V次，直到堆中所有顶点全部加入S。则整个算法的时间复杂度将从O(n2)优化为O(nlogn)。
  • 优先队列优化中，建立一个最小优先的优先级队列，队列中保存顶点和当前Lk值的二元组，初始将起点二元组入队，每当某个顶点的Lk值被更新，则将这个新的顶点二元组入队，每次迭代时，将队首元素取出并出队，直到队列为空。由于优先队列一般采用堆实现，故维护优先队列的复杂度同为O(logn)，则整个算法的时间复杂度同被优化为O(nlogn)。

注意：优先队列优化中，新的顶点二元组入队时，旧的二元组依然在优先队列中，因此每次出队的元素可能会有杂音，如何识别并去除这些杂音是这种优化方式需要考虑的。

关于无向图

事实上，Dijkstra算法同样可以处理无向图中的单源最短路问题（无向图其实可看做一种特殊的有向图），但在这种情况下，要对算法做一些修改：标记已经访问过的边，在寻找邻居时不沿已标记过的边寻找。

关于空间复杂度

Dijkstra算法的空间复杂度视具体实现方法而定，采用邻接矩阵的存图方式的空间复杂度为O(n2)，然而在稀疏图中，这种存储方式将有大量的空间浪费，因此推荐使用邻接表和有关标志数组存图。

算法具体代码实现多种多样，留作读者自行思考，在此不再赘述。

绝对原创，转载请注明出处。
才疏学浅，如有错误，望不吝赐教

相关推荐