1x

SSSP问题是（另）一个非常著名的计算机科学（CS）问题，全世界的每一个CS学生都必须掌握并了解。
SSSP问题有几种不同的有效（多项的）算法（例如贝尔曼福特，BFS，DFS，戴克斯特拉-2个版本，和/或动态规划），可以根据输入的有向加权图的性质使用，即加权/未加权，有/无（复权重）循环，或结构特殊（一个树/一个DAG）。

Remarks: By default, we show e-Lecture Mode for first time (or non logged-in) visitor.
If you are an NUS student and a repeat visitor, please login.

🕑

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.

Pro-tip 1: Since you are not logged-in, you may be a first time visitor (or not an NUS student) who are not aware of the following keyboard shortcuts to navigate this e-Lecture mode: [PageDown]/[PageUp] to go to the next/previous slide, respectively, (and if the drop-down box is highlighted, you can also use [→ or ↓/← or ↑] to do the same),and [Esc] to toggle between this e-Lecture mode and exploration mode.

🕑

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.

Pro-tip 2: We designed this visualization and this e-Lecture mode to look good on 1366x768 resolution or larger (typical modern laptop resolution in 2021). We recommend using Google Chrome to access VisuAlgo. Go to full screen mode (F11) to enjoy this setup. However, you can use zoom-in (Ctrl +) or zoom-out (Ctrl -) to calibrate this.

🕑

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.

Pro-tip 3: Other than using the typical media UI at the bottom of the page, you can also control the animation playback using keyboard shortcuts (in Exploration Mode): Spacebar to play/pause/replay the animation, / to step the animation backwards/forwards, respectively, and -/+ to decrease/increase the animation speed, respectively.

🕑

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生成树
🕑

🕑

🕑

`relax(u, v, w_u_v)  if D[v] > D[u]+w_u_v // 如果可以缩短路径    D[v] = D[u]+w_u_v // 我们“松弛”这个边    p[v] = u // 记住/更新 前一个点    // 根据需要更新一些其它的数据结构`

🕑

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

🕑

`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) `

🕑
Bellman-Ford 算法可以在普通的输入图中跑的更快一点，从最坏情况的 O(VxE) 到只要 O(kxE)，其中 k 是 Bellman-Ford 算法最外层的循环数。

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.

If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.

FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

🕑
1. 如果最短路径 p 不是简单路径
2. 那么 p 至少包含一个环 (根据非简单路径的定义)
3. 假设 p 中有一个正权重环 c (如左图的 绿绿)
4. 如果我们从 p 中移除 c，那么我们会得到一个比最短路径 p 更短的路径
5. 显然矛盾，所以 p 一定是一个简单路径
🕑
1. 就算 c 是一个零权重的环 — 根据我们的定理 1 这是可能的：没有负权重环 (详见右图中的 绿绿)，我们仍然可以从 p 中移除 c 而不增加 p 的权重
2. 总而言之，p 是一个简单路径 (第5点) 或可以被转换成简单路径 (第6点)

🕑

🕑
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 例子
🕑

🕑

🕑

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) 算法
🕑

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

🕑

🕑

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 一步
🕑

🕑

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.

🕑

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.

🕑

🕑

🕑

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!

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.

If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.

FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

🕑
Dijkstra 算法有多种实现方法。O((V+E) log V) 的改良版 Dijkstra 算法可以用在可能有负权重边但无负权重环的有向有权重图上。

🕑

🕑

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.

🕑

🕑

🕑

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.

🕑

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

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.

If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.

FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

🕑

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

🕑

🕑

🕑

🕑

🕑

You have reached the last slide. Return to 'Exploration Mode' to start exploring!

Note that if you notice any bug in this visualization or if you want to request for a new visualization feature, do not hesitate to drop an email to the project leader: Dr Steven Halim via his email address: stevenhalim at gmail dot com.

🕑

Visualisation Scale

Toggle V. Number for 0.5x

BFS 算法(s)

DFS 算法(s)

DP(s)

>

1.0x (Default)

0.5x (Minimal Details)

Negative Weight

Corner Case

Special Case

s =

Bellman-Ford

Bellman-Ford-Moore

s =

s =

s =

s =

#### 关于

VisuAlgo最初由副教授Steven Halim于2011年构思，旨在通过提供自学、互动式学习平台，帮助学生更深入地理解数据结构和算法。

VisuAlgo涵盖了Steven Halim博士与Felix Halim博士、Suhendry Effendy博士合著的书《竞技编程》中讨论的许多高级算法。即使过去十年，VisuAlgo仍然是可视化和动画化这些复杂算法的独家平台。

VisuAlgo仍然在不断发展中，正在开发更复杂的可视化。目前，该平台拥有24个可视化模块。

VisuAlgo配备了内置的问题生成器和答案验证器，其“在线测验系统”使学生能够测试他们对基本数据结构和算法的理解。问题根据特定规则随机生成，并且学生提交答案后会自动得到评分。随着越来越多的计算机科学教师在全球范围内采用这种在线测验系统，它可以有效地消除许多大学标准计算机科学考试中手工基本数据结构和算法问题。通过给通过在线测验的学生分配一个小但非零的权重，计算机科学教师可以显著提高学生对这些基本概念的掌握程度，因为他们可以在参加在线测验之前立即验证几乎无限数量的练习题。每个VisuAlgo可视化模块现在都包含自己的在线测验组件。

VisuAlgo已经被翻译成三种主要语言：英语、中文和印尼语。此外，我们还用各种语言撰写了关于VisuAlgo的公开笔记，包括印尼语、韩语、越南语和泰语：

id, kr, vn, th.

#### 团队

Associate Professor Steven Halim, School of Computing (SoC), National University of Singapore (NUS)
Dr Felix Halim, Senior Software Engineer, Google (Mountain View)

CDTL TEG 1: Jul 2011-Apr 2012: Koh Zi Chun, Victor Loh Bo Huai

Jul 2012-Dec 2013: Phan Thi Quynh Trang, Peter Phandi, Albert Millardo Tjindradinata, Nguyen Hoang Duy
Jun 2013-Apr 2014 Rose Marie Tan Zhao Yun, Ivan Reinaldo

CDTL TEG 2: May 2014-Jul 2014: Jonathan Irvin Gunawan, Nathan Azaria, Ian Leow Tze Wei, Nguyen Viet Dung, Nguyen Khac Tung, Steven Kester Yuwono, Cao Shengze, Mohan Jishnu

Jun 2014-Apr 2015: Erin Teo Yi Ling, Wang Zi
Jun 2016-Dec 2017: Truong Ngoc Khanh, John Kevin Tjahjadi, Gabriella Michelle, Muhammad Rais Fathin Mudzakir
Aug 2021-Apr 2023: Liu Guangyuan, Manas Vegi, Sha Long, Vuong Hoang Long, Ting Xiao, Lim Dewen Aloysius

Optiver: Aug 2023-Oct 2023: Bui Hong Duc, Oleh Naver, Tay Ngan Lin

Aug 2023-Apr 2024: Xiong Jingya, Radian Krisno, Ng Wee Han

List of translators who have contributed ≥ 100 translations can be found at statistics page.

NUS教学与学习发展中心（CDTL）授予拨款以启动这个项目。在2023/24学年，Optiver的慷慨捐赠将被用来进一步开发 VisuAlgo。

#### 使用条款

VisuAlgo并不是一个完成的项目。Steven Halim副教授仍在积极改进VisuAlgo。如果您在使用VisuAlgo时发现任何可视化页面/在线测验工具中的错误，或者您想要请求新功能，请联系Steven Halim副教授。他的联系方式是将他的名字连接起来，然后加上gmail dot com。