图论算法（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）。
例：

文章图片
解：
步骤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]

文章图片
情况-（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]

文章图片
步骤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]

文章图片
步骤-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。

文章图片
步骤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∴此条件不满足, 因此将被丢弃。