单源最短路径(SSSP)

1. Introduction

单源最短路径(SSSP)问题中,我们的目标是在有向加权图中找到从特定单源顶点到所有其它顶点的最短路径权重(和实际路径)(如果这样的路径存在)。
SSSP问题是(另)一个非常著名的计算机科学(CS)问题,全世界的每一个CS学生都必须掌握并了解。
SSSP问题有几种不同的有效(多项的)算法(例如贝尔曼福特,BFS,DFS,戴克斯特拉-2个版本,和/或动态规划),可以根据输入的有向加权图的性质使用,即加权/未加权,有/无(复权重)循环,或结构特殊(一个树/一个DAG)。

1-1. 动机

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.

1-2. SSSP 问题 - 两个输入值

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 sV.

1-3. SSSP 问题 - 输出

The objective of the SSSP problem is to find the shortest path weight from s to each vertex uV, 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.

1-4. SSSP问题 - 输出变量

在这个可视化中讨论的所有六种(6)SSSP算法的输出结果是这两个数组/向量:

  1. 一个大小为V的数组/向量DD代表 'distance')
    最初,如果u = s,那么D[u] = 0;否则D[u] = +∞(一个大数,例如 109
    当我们找到更好(更短)的路径时,D[u]会减小
    在SSSP算法的执行过程中,D[u]δ(s, u)
    在SSSP算法结束时,D[u] = δ(s, u)
  2. 一个大小为V的数组/向量p(p代表 'parent'/'predecessor'/'previous')
    p[u] = 来源su的最佳路径上的前驱
    p[u] = NULL(未定义,我们可以使用像-1这样的值)
    这个数组/向量p描述了结果SSSP生成树

1-5. s = 0 的例子

最初,D[u] = +∞ (实际上,一个大的值,如 109) ∀uV\\{s},但 D[s] = D[0] = 0。
最初,p[u] = -1 (表示 '没有前驱') ∀uV


现在点击 Dijkstra(0) —— 不用担心细节,稍后会解释 —— 等待结束 (在这个小图上大约需要10秒)。


在那个SSSP算法结束时,D[s] = D[0] = 0 (未改变) 和 D[u] = δ(s, u)uV
例如 D[2] = 6,D[4] = 7 (这些值存储为每个顶点下的红色文本)。
在那个SSSP算法结束时,p[s] = p[0] = -1 (源没有前驱),但 p[v] = 其他的红色边的起源,例如 p[2] = 0,p[4] = 2


因此,如果我们在 s = 0 并想去顶点4,我们将使用最短路径 0 → 2 → 4,路径权重为7。

1-6. 定义不明确的案例

一些图包含负权重边(不一定是循环)和/或负权重循环。例如(虚构):假设你可以通过时间隧道(特殊的虫洞边,具有负权重)向前(正常,具有正权重的边)或向后穿越时间,如上面的例子所示。


在那个图上,从源顶点s = 0到顶点{1, 2, 3}的最短路径都是未定义的。例如 1 → 2 → 1 是一个负权重循环,因为它的总路径(循环)权重为 15-42 = -27。因此,我们可以在负权重循环 0 → 1 → 2 → 1 → 2 → ... 上无限循环,以获得总的未定义的最短路径权重 -∞。


然而,请注意,从源顶点s = 0到顶点 4 的最短路径是可以的,δ(0, 4) = -99。所以,负权重的存在并不是主要问题。主要问题是从源顶点s可达的负权重循环的存在。

1-7. 主要操作: 松弛 (u, v, w(u, v))

此可视化中讨论的所有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) 操作:relax operation example

2. 输入图表

There are two different sources for specifying an input graph:

  1. Edit Graph: You can draw, edit, or import any directed weighted graph as the input graph.
  2. Example Graphs: You can select from the list of our selected example graphs to get you started. These example graphs have different characteristics.

3. SSSP算法

在此可视化中,我们会讨论 6 中 SSSP 算法。
我们会先讨论 O(VxE) 的贝尔曼福特 (Bellman-Ford) 算法,因为这是最通用的(也是最慢的)SSSP 算法。我们然后会讨论 5 种其他的,能更快解决 SSP 问题的特殊情况的算法(包括两种 Dijkstra 算法的变种)。

4. O(V×E) 贝尔曼福特算法

贝尔曼福特的通用算法,虽然有一点慢,但可以解决各种有效的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)

不用多说了,让我们通过点击 BellmanFord(0) 看它在上面的示例图上是如何工作的。(≈30s, 而且现在, 请忽略伪代码底部的附加的循环)。

4-1. 优化形式: O(k×E)

Bellman-Ford 算法可以在普通的输入图中跑的更快一点,从最坏情况的 O(VxE) 到只要 O(kxE),其中 k 是 Bellman-Ford 算法最外层的循环数。
讨论:如何提升?加速的效果显著吗?

4-2. 答案

[This is a hidden slide]

4-3. T.1: 最短路径是简单路径*

为了说服全世界的读者 Bellman-Ford 算法确实有作用,让我们在这几页里暂时从可视化模式转到证明模式。
定理一:如果 G = (V, E) 有非负权重环,那从源顶点 s 到顶点 v 的最短路径一定是一个简单路径。
回顾:一个简单路径是一个路径 p = {v0, v1, v2, ..., vk}, (vivi+1) ∈ E, ∀ 0 ≤ i ≤ (k-1) 其中没有重复的顶点。

4-4. 反证法 - 第1部分

  1. 如果最短路径 p 不是简单路径
  2. 那么 p 至少包含一个环 (根据非简单路径的定义)
  3. 假设 p 中有一个正权重环 c (如左图的 绿绿) cycle
  4. 如果我们从 p 中移除 c,那么我们会得到一个比最短路径 p 更短的路径
  5. 显然矛盾,所以 p 一定是一个简单路径

4-5. 反证法 - 第2部分

  1. 就算 c 是一个零权重的环 — 根据我们的定理 1 这是可能的:没有负权重环 (详见右图中的 绿绿),我们仍然可以从 p 中移除 c 而不增加 p 的权重cycle
  2. 总而言之,p 是一个简单路径 (第5点) 或可以被转换成简单路径 (第6点)

或者说,从源顶点 s 到”最远的”(按照最短路径中的边,详见上面的 Bellman-Ford Kill 示例)节点 v 的最短路径 p 最多有 |V|-1 条边。

4-6. T.2: 贝尔曼福特的算法是正确的

定理 2: 如果 G = (V, E) 不包含负权重环 , 那么在贝尔曼福特算法终止后,我们将得到 D[v] = δ(s, u), ∀ uV.

为此, 我们将使用归纳证明法 ,以下是验证的起始点:

考虑从源点 s 到顶点 vi 的最短路径 p ,其中 vi 被定义为顶点,从源点 s 到达它的实际最短路径需要 i 次跳 (i 条边) 。回想一下定理 1 ,p 将是简单的路径,因为我们有相同的没有负权重环的假设。

4-7. 归纳证明法

  1. 最开始 D[v0] = δ(s, v0) = 0, 因为 v0 就是源顶点 s
  2. 在遍历 E 一遍后,我们有 D[v1] = δ(s, v1)
  3. 在遍历 E 两遍后,我们有 D[v2] = δ(s, v2)
  4. ...
  5. 在遍历 E k 遍后,我们有 D[vk] = δ(s, vk)
  6. 如果没有负权重环,最短路径 p 是一个简单路径 (详见定理 1),所以最后一次遍历是第 |V|-1 次
  7. 在 |V|-1 次遍历 E 后,我们有 D[v|V|-1] = δ(s, v|V|-1), 不论 E 中边的排序 — 详见上面的 Bellman-Ford Killer 例子

4-8. 最坏情况的表现

尝试在上面的 'Bellman Ford's Killer' 示例中运行 BellmanFord(0) 。这里有V = 7 个顶点和 E = 6 条边,但是边列表 E 被设置成最差的次序。请注意,在 (V-1)×E = (7-1)*6 = 36 次操作(约40s,耐心等待)之后,贝尔曼福特算法将以正确的答案终止,我们将无法提前终止贝尔曼福特算法。

4-9. 在有负权重循环的图上

贝尔曼福特 (Bellman-Ford) 算法唯一不适用的情况是图中存在能从源顶点 s 到达的负权重环的情况。
然而,Bellman-Ford可被用来测试输入图是否含有至少一个可从源顶点 s 到达的负权重环,其根据为定理 2 的必然结果:如果在 |V|-1 次循环后仍然存在至少一个未被覆盖的值 D[u],那么至少存在一个可从源顶点 s 到达的负权重环。

5. 五种简化假设

有的时候,我们面对的实际问题并不是原始问题的普通形式。因此在此电子讲座中,我们会着重于单源最短路径问题的 5 种特殊情况。当我们遇见它们时,我们可以用比 O(V×E) 的贝尔曼福特算法更快的算法解决。这些情况是:

  1. 在无权重图中:O(V+E) 的 BFS,
  2. 在无负权重图中:O((V+E) log V) 的 戴克斯特拉 (Dijkstra) 算法,
  3. 在无负权重的环的图中:O((V+E) log V) 改良版戴克斯特拉 (Dijkstra) 算法,
  4. 在树中:O(V+E) 的 DFS/BFS,
  5. 在有向无环图中 (DAG): O(V+E) 动态规划 (DP) 算法

6. 广度优先搜索

O(V+E) 广度优先搜索 (BFS) 算法可以解决有特殊情况的SSSP问题,当输入图是未加权时(所有边都具有单位权重1,在上面的例子 'CP3 4.3' 上尝试 BFS(5)),或者正常数加权(所有有边都具有相同的恒定权重,例如,你可以在上面的例图中用你所选择的任何正恒定权重去更改所有的边的权重)。

6-1. 解释说明

当图是未加权 时— 这在现实生活中经常出现— 这种 SSSP 问题可以被视为找到从源点 s 到其它顶点的最小边数的问题。

由快速的 O(V+E) BFS 算法产生的来自源点 s 的BFS的生成树 — 注意符号 ‘+’ — 精确地符合要求。

与贝尔曼福特的 O(V×E) 相比— 注意符号 ‘×’ — 在这个特殊的SSSP中使用 BFS 是明智之举。

6-2. 次要实施调整

图遍历模块中的标准 BFS 不同,我们需要做简单的修改,使得 BFS 能够解决无权重版本的 SSSP 问题:

  1. 首先,我们将布尔数组 visited 改成一个整数数组 D
  2. 在 BFS 开始时,我们不令 visited[u] = false,而是令 D[u] = 1e9 (一个大数字来代表 +∞ 或者 -1 来代表“未访问”状态,但我们不能令 D[0] = 0) ∀uV\\{s};然后我们令 D[s] = 0
  3. 我们将
    if (visited[v] = 0) { visited[v] = 1 ... } // v 未被访问
    替换成
    if (D[v] = 1e9) { D[v] = D[u]+1 ... } // v 离 u 一步

6-3. 在一般图表上是错误答案

但是, BFS 很可能在有权重图上运行时产生错误答案,因为 BFS 实际上并不是为解决有权重的SSSP问题而设计的。可能存在这样的情况:采用具有更多边的路径产生的总路径权重总量小于采用具有最小边数量的路径 - 这就是BFS算法的输出。

在此可视化中,以用于教学目的,我们将允许您在“错误”的输入图上运行BF,但我们将在算法结束时显示警告信息。例如,在上面的一般图上尝试 BFS(0) ,你将看到顶点 {3,4} 将会有错误的 D[3] 和 D[4] 值 (以及 p[3] 和 p[4] 值).

我们很快会看到戴克斯特拉 (Dijkstra) 算法(2种实现变体)以比一般的贝尔曼福特算法更快的方式解决某些加权SSSP问题。

7. 戴克斯特拉算法(原始的实现)

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 Dijkstra(0) on one of the Example Graphs: CP4 4.16 shown above.

7-1. 关键想法

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.

7-2. O((V+E) log V) 时间复杂度 - 第 1部分

在Dijkstra的算法中,每个顶点只会从优先队列(PQ)中提取一次。由于有V个顶点,我们最多会做O(V)次这样的操作。


无论PQ是使用二叉最小堆实现的,还是使用平衡BST如AVL树实现的,ExtractMin()操作都在O(log V)中运行。


因此,这部分是O(V log V)。

7-3. O((V+E) log V) 时间复杂度 - 第 2部分

每当一个顶点被处理,我们松弛其相邻顶点。总计 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) 算法要快得多。

7-4. Proof of Correctness (1)

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!

7-5. Proof of Correctness (2)

[This is a hidden slide]

7-6. 在有负权重的表上是错误答案

当输入图包含至少一个负权重边 —— 不一定是负权重循环 —— 时,Dijkstra的算法可能会产生错误的答案。


尝试在其中一个示例图:CP3 4.18 上点击 Dijkstra(0)


在执行Dijkstra的算法结束时,顶点4的D[4]值错误,因为算法开始“错误地”认为子路径 0 → 1 → 3 是更好的子路径,权重为 1+2 = 3,因此在调用 relax(3,4,3) 后,D[4] = 6。然而,边 2 → 3 上的负权重 -10 使得另一个子路径 0 → 2 → 3 最终成为更好的子路径,尽管它开始时的路径权重为 10,但在第一条边 0 → 2 后,权重为 10-10 = 0。由于Dijkstra算法的贪婪性质,这个更好的D[3] = 0 永远不会进一步传播,因此D[4]是错误的。

8. 戴克斯特拉算法(修改版)

Dijkstra 算法有多种实现方法。O((V+E) log V) 的改良版 Dijkstra 算法可以用在可能有负权重边但无负权重环的有向有权重图上。
这种输入图也有实际应用:乘坐电动车出行而我们的目标是找到从源顶点 s 到另一个顶点的一条最省电的路。照常,在加速阶段(或在平地/上坡路)时,电车从电池中使用(正)能量;而在刹车(或下坡)时,电车重新充电(或使用负能量)。因为动能的损失,在路上没有负权重环。
例如,在示例图中试试 ModifiedDijkstra(0) : CP3 4.18 不适用 Dijkstra 算法的原始版本 (详见 前一页)。

8-1. 关键想法

关键点在于对于 C++ STL priority_queue/Python heapq/Java PriorityQueue 关于 ”usage modification“ 的部分,这允许其在 O(log V) 时间内高效地执行 ”DecreaseKey“ 操作。
这个技巧叫做 ”惰性更新“,我们在最小优先队列中保留过时的/更弱的/更大值的信息,而不是直接将其删除。因为优先队列中的项是从小到大排列的,我们保证我们会在遇到更弱的/过时的项(在这时已经可以忽略)之前遇到更小的/更新的项。

8-2. O((V+E) log V) 时间复杂度?

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.

8-3. 在没有负权重循环的图上更正

当输入图包含至少一个负权重边但没有负权重周期时 - 修改后的Dijkstra算法产生正确的答案。

尝试使用其中一个示例图表ModifiedDijkstra(0):CP3 4.18导致Dijkstra(0)出现问题。

在ModifiedDijkstra算法执行结束时,顶点4具有正确的D [4]值,因为虽然修改后的Dijkstra算法也开始“错误地”认为子路径0→1→3是权重1 + 2 = 3的更好的子路径,因此在调用relax(3,4,3)后使D [4] = 6。这里,修改后的Dijkstra算法在发现其他子路径0→2→3最终是权重10-10 = 0的更好子路径之后继续传播D [3] = 0.因此D [4]最终再次正确。然而,这是以比O((V + E)log V)可能运行(更多)操作为代价的。

8-4. 具有负权重循环的图的问题

不幸的是, 在一个负权重循环图上运行 ModifiedDijkstra(0) ,如上面的CP3 4.17示例图所示: 将导致无限循环(动画演示很长,但我们将循环数限制为只处理100个边,所以你的网页浏览器不会当机)。

8-5. 最差的案例输入

Try ModifiedDijkstra(0) 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.

9. 深度优先搜索

O(V) 深度优先搜索 (DFS) 算法可以解决S特殊的SSP 问题,就是当输入图是(加权)时。


在树中,只有一条独特的无环路径连接两个不同的顶点。因此,将源点 s 链接到任何另一个顶点 uV 的唯一路径其实上也是最短的路径。例如,在上面的树图上尝试 DFS(0)


请注意,对于(加权)树,我们也可以使用BFS。例如,在上面的同一个树图上尝试 BFS(0)


讨论:如果输入是一个(加权)树,为什么DFS (以及 BFS) 运行 的是 O(V)而不是 O(V+E) ?

9-1. 答案

[This is a hidden slide]

9-2. 错误答案(对于非树图)


在不是Tree的任何其他图形上运行时,DFS很可能会产生错误的答案。我们将为此类案例显示警告消息,但我们不会阻止您出于教学目的而尝试此功能。

例如,在上面的一般图表上尝试DFS(0),您将看到顶点{4}将具有错误的D [4]值(以及错误的p [4]值),因为DFS(0)深入0→1→首先是3→4,一直回溯到顶点0并且最终访问0→2但是由于DFS之前已经访问过顶点4,所以不能处理边缘2→4。

10. 动态规划(DP)

O(V+E) 动态规划 算法可以解决SSSP特殊的问题,就是当输入图是有向无环图(DAG)时 ,我们可以找到至少一个属于这个DAG的拓扑顺序,并根据这个拓扑秩序处理边松弛操作。


例如,在上面示例的DAG上尝试 DP(0) 。 首先,它使用 O(V+E) DFS 或 Graph Traversal 模块中概述的BFS/Kahn 算法.去计算一个(还有其它)可能的拓扑顺序。 比如,假设一个拓扑顺序是 {0,2,1,3,4,5}。然后它松弛该拓扑顺序中列出的外出边。在经过一次 O(V+E) pass 后,我们将得到正确的 D[u] 值, ∀uV

10-1. 长处与缺点

在上面显示的修改版的戴克斯特拉杀手示例中, DP(0) 运行得很快,因为尽管具有负权重边,图实际上是一个DAG。并且因此不必担心负权重循环。


但是,DP不适用于任何非DAG,因为非DAG至少包含一个圈,因此在该圈内不能找到拓扑顺序。

10-2. 与贝尔曼福特算法的相似之处

用来在 DAG 上求解单源最短路径 (SSSP) 的动态规划算法也被称为 one-pass 贝尔曼福特算法,因为它只用一个拓扑顺序短息(我们知道这是这个DAG的(其中一个)正确顺序)代替最外层的 V-1 圈循环 (我们不知道正确的顺序,所以我们只能重复到达到最大的可能性)。

在上面的实例 DAG 上对比 DP(0) (根据其顶点的拓扑顺序仅松弛 E 边一次)与BellmanFord(0) (以随机顺序松弛 E 边,V-1 次) 。

11. 额外的

关于 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

11-1. 在线测试

有关此SSSP问题及其各种算法的一些有趣问题,请在 SSSP 培训模块中练习(无需登陆)。


但是,对于注册用户,您应该登陆然后转到 Main Training Page 以正式清除此模块(清除其它先决模块),此类成就将记录在你的账户中。

11-2. 在线评判练习

我们还有一些编程问题,这些问题在某种程度上需要使用正确的SSSP算法:Kattis - hidingplacesKattis - shortestpath1


尝试解决它们,然后尝试这个有趣的SSSP问题的更多有趣的变体。


广告:购买竞赛编程教科书以了解更多关于这个有趣问题的信息。