SSSP is one of the most frequent graph problem encountered in real-life. Every time we want to move from one place (usually our current location) to another (our destination), we will try to pick a short — if not the shortest — path.
SSSP algorithm(s) is embedded inside various map software like Google Maps and in various Global Positioning System (GPS) tool.
Input 1: A directed weighted graph G(V, E), not necessarily connected, where V/vertices can be used to describe intersections, junctions, houses, landmarks, etc and E/edges can be used to describe streets, roads, avenues with proper direction and weight/cost.
Input 2: As the name implies, the SSSP problem has another input: A source vertex s ∈ V.
The objective of the SSSP problem is to find the shortest path weight from s to each vertex u ∈ V, denoted as δ(s, u) (δ is pronounced as 'delta') and also the actual shortest path from s to u.
The path weight of a path p is simply the summation of edge weights along that path.
The weight of the shortest path from s to s is trivial: 0.
The weight of the shortest path from s to any unreachable vertex is also trivial: +∞.
PS: The weight of the shortest path from s to v where (s, v) ∈ E does not necessarily the weight of w(s, v). See the next few slides to realise this.
在这个可视化中讨论的所有六种（6）SSSP算法的输出结果是这两个数组/向量：
Initially, D[u] = +∞ (practically, a large value like 109) ∀u ∈ V\{s}, but D[s] = D[0] = 0.
Initially, p[u] = -1 (to say 'no predecessor') ∀u ∈ V.
Now click — don't worry about the details as they will be explained later — and wait until it is over (approximately 10s on this small graph).
At the end of that SSSP algorithm, D[s] = D[0] = 0 (unchanged) and D[u] = δ(s, u) ∀u ∈ V
e.g., D[2] = 6, D[4] = 7 (these values are stored as red text under each vertex).
At the end of that SSSP algorithm, p[s] = p[0] = -1 (the source has no predecessor), but p[v] = the origin of the red edges for the rest, e.g., p[2] = 0, p[4] = 2.
Thus, if we are at s = 0 and want to go to vertex 4, we will use shortest path 0 → 2 → 4 with path weight 7. In the exploration mode, after any SSSP algorithm has been completed, you can hover on any vertex and notice the shortest path from source vertex s to that vertex is highlighted.
一些图包含负权重边（不一定是循环）和/或负权重循环。例如（虚构）：假设你可以通过时间隧道（特殊的虫洞边，具有负权重）向前（正常，具有正权重的边）或向后穿越时间，如上面的例子所示。
在那个图上，从源顶点s = 0到顶点{1, 2, 3}的最短路径都是未定义的。例如 1 → 2 → 1 是一个负权重循环，因为它的总路径（循环）权重为 15-42 = -27。因此，我们可以在负权重循环 0 → 1 → 2 → 1 → 2 → ... 上无限循环，以获得总的未定义的最短路径权重 -∞。
然而，请注意，从源顶点s = 0到顶点 4 的最短路径是可以的，δ(0, 4) = -99。所以，负权重边的存在并不是主要问题。主要问题是从源顶点s可达的负权重循环的存在。
此可视化中讨论的所有SSSP算法的主要操作是使用以下伪代码进行 relax(u, v, w(u, v))松弛操作:
relax(u, v, w_u_v)
if D[v] > D[u]+w_u_v // 如果可以缩短路径
D[v] = D[u]+w_u_v // 我们“松弛”这个边
p[v] = u // 记住/更新 前一个点
// 根据需要更新一些其它的数据结构
例如，请参见下图中的松弛(1,2,4) 操作：
There are four different sources for specifying an input graph:
贝尔曼福特的通用算法，虽然有一点慢，但可以解决各种有效的SSSP 问题 (除了一个 ， 我们再以后讨论这个例外)。它还有一个非常简单的伪代码：
for i = 1 to |V|-1 // 这里是 O(V), 所以 O(V×E×1) = O(V×E)
for each edge(u, v) ∈ E // 这里是 O(E), 例如，通过使用边缘列表
relax(u, v, w(u, v)) // 这里是 O(1)
不用多说了，让我们通过点击 看它在上面的示例图上是如何工作的。（≈30s, 而且现在, 请忽略伪代码底部的附加的循环）。
或者说，从源顶点 s 到”最远的”（按照最短路径中的边，详见上面的 Bellman-Ford Kill 示例）节点 v 的最短路径 p 最多有 |V|-1 条边。
定理 2: 如果 G = (V, E) 不包含负权重环 , 那么在贝尔曼福特算法终止后，我们将得到 D[v] = δ(s, u), ∀ u ∈ V.
为此, 我们将使用归纳证明法 ，以下是验证的起始点:
考虑从源点 s 到顶点 vi 的最短路径 p ，其中 vi 被定义为顶点，从源点 s 到达它的实际最短路径需要 i 次跳 (i 条边) 。回想一下定理 1 ，p 将是简单的路径，因为我们有相同的没有负权重环的假设。
尝试在上面的 'Bellman Ford's Killer' 示例中运行 。这里有V = 7 个顶点和 E = 6 条边，但是边列表 E 被设置成最差的次序。请注意，在 (V-1)×E = (7-1)*6 = 36 次操作（约40s，耐心等待）之后，贝尔曼福特算法将以正确的答案终止，我们将无法提前终止贝尔曼福特算法。
有的时候，我们面对的实际问题并不是原始问题的普通形式。因此在此电子讲座中，我们会着重于单源最短路径问题的 5 种特殊情况。当我们遇见它们时，我们可以用比 O(V×E) 的贝尔曼福特算法更快的算法解决。这些情况是：
The O(V+E) Breadth-First Search (BFS) algorithm can solve special case of SSSP problem when the input graph is unweighted (all edges have unit weight 1, try on example: 'CP4 4.2 U/U' above) or positive constant weighted (all edges have the same constant weight, e.g. you can change all edge weights of the example graph above with any positive constant weight of your choice).
当图是未加权 时— 这在现实生活中经常出现— 这种 SSSP 问题可以被视为找到从源点 s 到其它顶点的最小边数的问题。
由快速的 O(V+E) BFS 算法产生的来自源点 s 的BFS的生成树 — 注意符号 ‘+’ — 精确地符合要求。
与贝尔曼福特的 O(V×E) 相比— 注意符号 ‘×’ — 在这个特殊的SSSP中使用 BFS 是明智之举。
与图遍历模块中的标准 BFS 不同，我们需要做简单的修改，使得 BFS 能够解决无权重版本的 SSSP 问题：
但是, BFS 很可能在有权重图上运行时产生错误答案，因为 BFS 实际上并不是为解决有权重的SSSP问题而设计的。可能存在这样的情况：采用具有更多边的路径产生的总路径权重总量小于采用具有最小边数量的路径 - 这就是BFS算法的输出。
在此可视化中，以用于教学目的，我们将允许您在“错误”的输入图上运行BF，但我们将在算法结束时显示警告信息。例如，在上面的一般图上尝试 ，你将看到顶点 {3,4} 将会有错误的 D[3] 和 D[4] 值 (以及 p[3] 和 p[4] 值).我们很快会看到戴克斯特拉 (Dijkstra) 算法（2种实现变体）以比一般的贝尔曼福特算法更快的方式解决某些加权SSSP问题。
The O((V+E) log V) Dijkstra's algorithm is the most frequently used SSSP algorithm for typical input: Directed weighted graph that has no negative weight edge, formally: ∀edge(u, v) ∈ E, w(u, v) ≥ 0. Such weighted graph (especially the positive weighted ones) is very common in real life as travelling from one place to another always use positive time unit(s). Try on one of the Example Graphs: CP4 4.16* D/W shown above (compared to CP4 version, we add one more edge 2 → 1 to make the graph non-DAG).
Dijkstra's algorithm maintains a set R(esolved) — other literature use set S(olved) but set S and source vertex s are too close when pronounced — of vertices whose final shortest path weights have been determined. Initially R = {}, empty.
Then, it repeatedly selects vertex u in {V\\R} (can also be written as {V-R}) with the minimum shortest path estimate (the first vertex selected is u = s as initially only D[s] = 0 and the other vertices have D[u] = ∞), adds u to R, and relaxes all outgoing edges of u. Detailed proof of correctness of this Dijkstra's algorithm is usually written in typical Computer Science algorithm textbooks and we replicate it in the next few slides. For a simpler intuitive visual explanation on why this greedy strategy works, see this.
For efficient implementation, this entails the use of a Priority Queue as the shortest path estimates keep changing as more edges are processed. The choice of relaxing edges emanating from vertex with the minimum shortest path estimate first is greedy, i.e., use the "best so far", but we will see later that it can be proven (with loop invariants) that it will ends up with an optimal result — if the graph has no negative weight edge.
在Dijkstra的算法中，每个顶点只会从优先队列（PQ）中提取一次。由于有V个顶点，我们最多会做O(V)次这样的操作。
无论PQ是使用二叉最小堆实现的，还是使用平衡BST如AVL树实现的，ExtractMin()操作都在O(log V)中运行。
因此，这部分是O(V log V)。
每当一个顶点被处理，我们松弛其相邻顶点。总计 E 条边会被处理。
如果当松弛 edge(u, v) 时，我么需要减小 D[v]，我们可以在最小二叉堆中 (较难实现，因为 C++ STL priority_queue/Python heapq/Java PriorityQueue 都不支持此操作) 调用 O(log V) 的 DecreaseKey() 操作；或是简单地在平衡二叉树如AVL树中删除旧项并重新插入新项，这种方法的时间复杂度也为 O(log V)，但更容易实现，因为可以直接调用 C++ STL set/Java TreeSet - 不幸的是Python没有内置支持。
所以，这部分的时间复杂度为 O(E log V)。
因此总的来说，戴克斯特拉 (Dijkstra) 算法的时间复杂度为 O(V log V + E log V) = O((V+E) log V)，这比 O(VxE) 的贝尔曼福特 (Bellman-Ford) 算法要快得多。To show the correctness of Dijkstra's algorithm on non-negative weighted graph, we need to use loop invariant: a condition which is True at the start of every iteration of the loop.
We want to show:
- Initialization: The loop invariant is true before the first iteration.
- Maintenance: If the loop invariant is true for iteration x, it remains true for iteration x+1.
- Termination: When the algorithm ends, the loop invariant helps the proof of correctness.
Discussion: Formally prove the correctness of Dijkstra's algorithm in class!
When the input graph contains at least one negative weight edge — not necessarily negative weight cycle — Dijkstra's algorithm can produce wrong answer.
Try on one of the Example Graphs: CP4 4.20.
At the end of the execution of Dijkstra's algorithm, vertex 4 has wrong D[4] value as the algorithm started 'wrongly' thinking that subpath 0 → 1 → 3 is the better subpath of weight 1+2 = 3, thus making D[4] = 6 after calling relax(3,4,3). However, the presence of negative weight -10 at edge 2 → 3 makes the other subpath 0 → 2 → 3 eventually the better subpath of weight 10-10 = 0 although it started worse with path weight 10 after the first edge 0 → 2. This better D[3] = 0 is never propagated further due to the greedy nature of Dijkstra's algorithm, hence D[4] is wrong.
Dijkstra's algorithm can also be implemented differently. The O((V+E) log V) Modified Dijkstra's algorithm can be used for directed weighted graphs that may have negative weight edges but no negative weight cycle.
Such input graph appears in some practical cases, e.g., travelling using an electric car that has battery and our objective is to find a path from source vertex s to another vertex that minimizes overall battery usage. As usual, during acceleration (or driving on flat/uphill road), the electric car uses (positive) energy from the battery. However, during braking (or driving on downhill road), the electric car recharges (or use negative) energy to the battery. There is no negative weight cycle due to kinetic energy loss.
For example, try on one of the Example Graphs: CP4 4.20 that has troubled the original version of Dijkstra's algorithm (see previous slide).
On non-negative weighted graphs, the behavior of Modified Dijkstra's implementation is exactly the same as the Original Dijkstra's so we can use the same time complexity analysis of O((V+E) log V).
PS: We note that when we use the Modified Dijkstra's algorithm, there can be more items (up to E) in the Priority Queue than if we use the Original Dijkstra's algorithm (up to V). However, since O(log E) = O(log V^2) = O(2 log V) = O(log V), we still treat the Priority Queue operations as O(log V).
However, if the graph has at least one negative weight edge, the analysis is harder.
When the input graph contains at least one negative weight edge but no negative weight cycle — the modified Dijkstra's algorithm produces correct answer.
Try on one of the Example Graphs: CP4 4.20 that causes problem for .
At the end of the execution of ModifiedDijkstra's algorithm, vertex 4 has correct D[4] value as although the modified Dijkstra's algorithm also started 'wrongly' thinking that subpath 0 → 1 → 3 is the better subpath of weight 1+2 = 3, thus making D[4] = 6 after calling relax(3,4,3). Here, the modified Dijkstra's algorithm continues propagating D[3] = 0 after it founds out that the other subpath 0 → 2 → 3 is eventually the better subpath of weight 10-10 = 0. Hence D[4] is eventually correct again. However, this is at the expense of potentially running (much more) operations than O((V+E) log V).
Unfortunately, running on the graph with negative weight cycle as shown on one of the Example Graphs: CP4 4.22 above will cause an endless loop (the animation is very long but we limit the number of loop to be 100 edges processed so your web browser will not hang).
Try on the extreme corner case above that is very hard to derive without proper understanding of this algorithm and was part of Asia Pacific Informatics Olympiad (APIO) 2013 task set by A/P Halim himself long ago.
The Modified Dijkstra's algorithm will terminate with correct answer, but only after running exponential number of operations (each carefully constructed triangle raises the number of required operations by another power of two). Thus we cannot prematurely terminate Modified Dijkstra's in this worst case input situation.
However, such extreme corner case is rare and thus in practice, Modified Dijkstra's algorithm can be used on directed graphs that have some negative weighted edges as long as the graph has no negative weight cycle reachable from the source vertex s.
O(V) 深度优先搜索 (DFS) 算法可以解决S特殊的SSP 问题，就是当输入图是（加权）树时。
在树中，只有一条独特的无环路径连接两个不同的顶点。因此，将源点 s 链接到任何另一个顶点 u ∈ V 的唯一路径其实上也是最短的路径。例如，在上面的树图上尝试 。
请注意，对于（加权）树，我们也可以使用BFS。例如，在上面的同一个树图上尝试 。
讨论：如果输入是一个（加权）树，为什么DFS (以及 BFS) 运行 的是 O(V)而不是 O(V+E) ？
O(V+E) 动态规划 算法可以解决SSSP特殊的问题，就是当输入图是有向无环图（DAG）时 ，我们可以找到至少一个属于这个DAG的拓扑顺序，并根据这个拓扑秩序处理边松弛操作。
例如，在上面示例的DAG上尝试 。 首先，它使用 O(V+E) DFS 或 Graph Traversal 模块中概述的BFS/Kahn 算法.去计算一个（还有其它）可能的拓扑顺序。 比如，假设一个拓扑顺序是 {0,2,1,3,4,5}。然后它松弛该拓扑顺序中列出的外出边。在经过一次 O(V+E) pass 后，我们将得到正确的 D[u] 值， ∀u ∈ V。
在上面显示的修改版的戴克斯特拉杀手示例中， 运行得很快，因为尽管具有负权重边，图实际上是一个DAG。并且因此不必担心负权重循环。
但是，DP不适用于任何非DAG，因为非DAG至少包含一个圈，因此在该圈内不能找到拓扑顺序。
用来在 DAG 上求解单源最短路径 (SSSP) 的动态规划算法也被称为 one-pass 贝尔曼福特算法，因为它只用一个拓扑顺序短息（我们知道这是这个DAG的（其中一个）正确顺序）代替最外层的 V-1 圈循环 (我们不知道正确的顺序，所以我们只能重复到达到最大的可能性）。
在上面的实例 DAG 上对比 (根据其顶点的拓扑顺序仅松弛 E 边一次）与 (以随机顺序松弛 E 边，V-1 次) 。
关于 SSSP 问题，我们还有基于 SSSP 算法的基础解释的许多其他东西。
同时，你可以使用/修改我们关于 Bellman-Ford/Bellman-Ford-Moore/Dijkstra 算法的实现：bellman_ford.cpp/bellman_ford_moore.cpp/dijkstra.cpp
bellman_ford.java/bellman_ford_moore.java/dijkstra.java
bellman_ford.py/bellman_ford_moore.py/dijkstra.py
bellman_ford.ml/bellman_ford_moore.ml/dijkstra.ml
有关此SSSP问题及其各种算法的一些有趣问题，请在 SSSP 培训模块中练习（无需登陆）。
但是，对于注册用户，您应该登陆然后转到 Main Training Page 以正式清除此模块（清除其它先决模块），此类成就将记录在你的账户中。
我们还有一些编程问题，这些问题在某种程度上需要使用正确的SSSP算法：Kattis - hidingplaces 和 Kattis - shortestpath1。
尝试解决它们，然后尝试这个有趣的SSSP问题的更多有趣的变体。
广告：购买竞赛编程教科书以了解更多关于这个有趣问题的信息。