图论算法:Dijkstra算法

它是一种贪心算法, 可以解决有向图G =(V, E)具有非负边权重, 即每个边(u, v)∈E w(u, v)≥0的有向图的单源最短路径问题。

Dijkstra的算法会维护一组顶点S, 这些顶点的最终最短路径权重已确定。这是针对所有顶点v∈S;我们有d [v] =δ(s, v)。该算法反复选择具有最小最短路径估计的顶点u∈V-S, 将u插入S并放宽所有留下u的边。

因为它总是选择V-S中“最轻”或“最接近”的顶点插入集合S中, 所以称为贪心策略。

Dijkstra's Algorithm (G, w, s)
 1. INITIALIZE - SINGLE - SOURCE (G, s)
 2. S←∅
 3. Q←V [G]
 4. while Q ≠ ∅
 5. do u ← EXTRACT - MIN (Q)
 6. S ← S ∪ {u}
 7. for each vertex v ∈ Adj [u]
 8. do RELAX (u, v, w)

分析:Dijkstra算法在具有边E和顶点V的图形上的运行时间可以表示为| E |的函数。和| V |使用Big-O表示法。 Dijkstra算法的最简单实现是将集合Q的顶点存储在普通链表或数组中, 而Extract-Min(Q)操作只是对Q中所有顶点的线性搜索。在这种情况下, 运行时间为O(| V2 | + | E | = O(V2)。

例:

Dijkstra算法

解:

步骤1:Q = [s, t, x, y, z]

我们一一扫描顶点, 然后找出相邻的顶点。计算每个相邻顶点之间的距离。

我们制作一个堆栈, 其中包含在计算出最短距离之后选择的那些顶点。

首先, 我们在堆栈M中取“”(这是来源)

M = [S]       Q = [t, x, y, z]

步骤2:现在找到t和y相邻的s。

Adj [s] → t, y      [Here s is u and t and y are v]
Dijkstra算法

情况-(i)s→td [v]> d [u] + w [u, v] d [t]> d [s] + w [s, t]∞> 0 + 10 [假条件]然后d [t]←10π[t]←5调整[s]←t, y

情况-(ii)s→yd [v]> d [u] + w [u, v] d [y]> d [s] + w [s, y]∞> 0 + 5 [假条件]∞> 5然后d [y]←5π[y]←5

通过比较情况(i)和情况(ii)Adj [s]→t = 10, y = 5 y最短y被分配为5 = [s, y]

Dijkstra算法

步骤3:现在找到y的相邻点, 即t, x, z。

Adj [y] → t, x, z   [Here y is u and t, x, z are v]

情况-(i)y→td [v]> d [u] + w [u, v] d [t]> d [y] + w [y, t] 10> 5 + 3 10> 8然后d [ t]←8π[t]←y

情况-(ii)y→xd [v]> d [u] + w [u, v] d [x]> d [y] + w [y, x]∞> 5 + 9∞> 14然后d [ x]←14π[x]←14

情况-(iii)y→zd [v]> d [u] + w [u, v] d [z]> d [y] + w [y, z]∞> 5 + 2∞> 7然后d [ z]←7π[z]←y

通过比较情况(i), 情况(ii)和情况(iii)Adj [y]→x = 14, t = 8, z = 7 z最短的z被分配为7 = [s, z]

Dijkstra算法

步骤-4现在, 我们将找到s, x的调整[z]

Adj [z] → [x, s]   	[Here z is u and s and x are v]

情况-(i)z→xd [v]> d [u] + w [u, v] d [x]> d [z] + w [z, x] 14> 7 + 6 14> 13然后d [ x]←13π[x]←z

情况-(ii)z→sd [v]> d [u] + w [u, v] d [s]> d [z] + w [z, s] 0> 7 + 7 0> 14∴不满意, 因此将其丢弃。现在我们有x = 13。

Dijkstra算法

步骤5:现在我们将找到Adj [t]

调整[t]→[x, y] [这里t是u, x和y是v]

情况-(i)t→xd [v]> d [u] + w [u, v] d [x]> d [t] + w [t, x] 13> 8 + 1 13> 9然后d [ x]←9π[x]←t

情况-(ii)t→yd [v]> d [u] + w [u, v] d [y]> d [t] + w [t, y] 5> 10∴此条件不满足, 因此将被丢弃。

Dijkstra算法

因此, 我们得到所有最短路径顶点为

从s到y的权重是5从s到z的权重是7从s到t的权重是8从s到x的权重

在给定的图中, 这是到光源的最短距离。

Dijkstra算法

Dijkstra算法的缺点

  1. 它会进行盲目搜索, 因此在处理时会浪费大量时间。
  2. 它不能处理负边缘。
  3. 它导致无环图, 并且通常无法获得正确的最短路径。
  4. 我们需要跟踪已访问的顶点。
微信公众号
手机浏览(小程序)
0
分享到:
没有账号? 忘记密码?