7    VisuAlgo    Single-Source Shortest Paths
Exploration Mode ▿

Draw Graph

Random Graph

Example Graphs

Bellman Ford's

Dijkstra's Algorithm

BFS Algorithm

DFS Algorithm

Dynamic Programming

CP3 4.3 U/U

CP3 4.4 D/U

CP3 4.17 D/W

CP3 4.18 -ve weight

CP3 4.19 -ve cycle

CP3 4.40 Tree

Bellman Ford's Killer

Dijkstra's Killer

DAG

Go

Original

Modified

Go

Go

Go

About Team Terms of use
slow
fast
go to beginning previous frame pause play next frame go to end

About

VisuAlgo was conceptualised in 2011 by Dr Steven Halim as a tool to help his students better understand data structures and algorithms, by allowing them to learn the basics on their own and at their own pace.

VisuAlgo contains many advanced algorithms that are discussed in Dr Steven Halim's book ('Competitive Programming', co-authored with his brother Dr Felix Halim) and beyond. Today, some of these advanced algorithms visualization/animation can only be found in VisuAlgo.

Though specifically designed for National University of Singapore (NUS) students taking various data structure and algorithm classes (e.g. CS1010, CS1020, CS2010, CS2020, CS3230, and CS3230), as advocators of online learning, we hope that curious minds around the world will find these visualisations useful too.

VisuAlgo is not designed to work well on small touch screens (e.g. smartphones) from the outset due to the need to cater for many complex algorithm visualizations that require lots of pixels and click-and-drag gestures for interaction. The minimum screen resolution for a respectable user experience is 1024x768 and only the landing page is relatively mobile-friendly.

VisuAlgo is an ongoing project and more complex visualisations are still being developed.

The most exciting development is the automated question generator and verifier (the online quiz system) that allows students to test their knowledge of basic data structures and algorithms. The questions are randomly generated via some rules and students' answers are instantly and automatically graded upon submission to our grading server. This online quiz system, when it is adopted by more CS instructors worldwide, should technically eliminate manual basic data structure and algorithm questions from typical Computer Science examinations in many Universities. By setting a small (but non-zero) weightage on passing the online quiz, a CS instructor can (significantly) increase his/her students mastery on these basic questions as the students have virtually infinite number of training questions that can be verified instantly before they take the online quiz. The training mode currently contains questions for 12 visualization modules. We will soon add the remaining 8 visualization modules so that every visualization module in VisuAlgo have online quiz component.

Another active branch of development is the internationalization sub-project of VisuAlgo. We want to prepare a database of CS terminologies for all English text that ever appear in VisuAlgo system. This is a big task and requires crowdsourcing. Once the system is ready, we will invite VisuAlgo visitors to contribute, especially if you are not a native English speaker. Currently, we have also written public notes about VisuAlgo in various languages: zh, id, kr, vn, th.

Team

Project Leader & Advisor (Jul 2011-present)
Dr Steven Halim, Senior Lecturer, School of Computing (SoC), National University of Singapore (NUS)
Dr Felix Halim, Software Engineer, Google (Mountain View)

Undergraduate Student Researchers 1 (Jul 2011-Apr 2012)
Koh Zi Chun, Victor Loh Bo Huai

Final Year Project/UROP students 1 (Jul 2012-Dec 2013)
Phan Thi Quynh Trang, Peter Phandi, Albert Millardo Tjindradinata, Nguyen Hoang Duy

Final Year Project/UROP students 2 (Jun 2013-Apr 2014)
Rose Marie Tan Zhao Yun, Ivan Reinaldo

Undergraduate Student Researchers 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

Final Year Project/UROP students 3 (Jun 2014-Apr 2015)
Erin Teo Yi Ling, Wang Zi

Final Year Project/UROP students 4 (Jun 2016-Apr 2017)
Truong Ngoc Khanh, John Kevin Tjahjadi, Gabriella Michelle

Acknowledgements
This project is made possible by the generous Teaching Enhancement Grant from NUS Centre for Development of Teaching and Learning (CDTL).

Terms of use

VisuAlgo is free of charge for Computer Science community on earth. If you like VisuAlgo, the only payment that we ask of you is for you to tell the existence of VisuAlgo to other Computer Science students/instructors that you know =) via Facebook, Twitter, course webpage, blog review, email, etc.

If you are a data structure and algorithm student/instructor, you are allowed to use this website directly for your classes. If you take screen shots (videos) from this website, you can use the screen shots (videos) elsewhere as long as you cite the URL of this website (http://visualgo.net) and/or list of publications below as reference. However, you are NOT allowed to download VisuAlgo (client-side) files and host it on your own website as it is plagiarism. As of now, we do NOT allow other people to fork this project and create variants of VisuAlgo. Using the offline copy of (client-side) VisuAlgo for your personal usage is fine.

Note that VisuAlgo's online quiz component is by nature has heavy server-side component and there is no easy way to save the server-side scripts and databases locally. Currently, the general public can only use the 'training mode' to access these online quiz system. Currently the 'test mode' is a more controlled environment for using these randomly generated questions and automatic verification for a real examination in NUS. Other interested CS instructor should contact Steven if you want to try such 'test mode'.

List of Publications

This work has been presented briefly at the CLI Workshop at the ACM ICPC World Finals 2012 (Poland, Warsaw) and at the IOI Conference at IOI 2012 (Sirmione-Montichiari, Italy). You can click this link to read our 2012 paper about this system (it was not yet called VisuAlgo back in 2012).

This work is done mostly by my past students. The most recent final reports are here: Erin, Wang Zi, Rose, Ivan.

Bug Reports or Request for New Features

VisuAlgo is not a finished project. Dr Steven Halim is still actively improving VisuAlgo. If you are using VisuAlgo and spot a bug in any of our visualization page/online quiz tool or if you want to request for new features, please contact Dr Steven Halim. His contact is the concatenation of his name and add gmail dot com.

In the Single-Source Shortest Paths (SSSP) problem, we aim to find the shortest paths from a particular single-source vertex to all other vertices in a directed weighted graph (if such paths exist).


Different algorithms (e.g. Bellman Ford, Dijkstra — 2 versions, BFS, DFS, and/or Dynamic Programming) can be used depending on the nature of the directed weighted graph, i.e. weighted/unweighted, with/without negative weight/cycle.

X Esc
Next

When the SSSP algorithm animation is running, the vertices and edges of the SSSP spanning tree will be shown as an orange highlight and the corresponding distance information from the source vertex to each vertex will be shown as a red text below each vertex.

X Esc
Prev
Next

There are three different sources for specifying an input graph:

  1. Draw Graph: You can draw any directed weighted graph as the input graph.
  2. Random Graph: You can tap into our graph database to see other random directed weighted graph that have been drawn by other users (currently disabled).
  3. Example Graphs: You can select from the list of our selected example graphs to get you started.
X Esc
Prev
Next

The general purpose O(VE) Bellman Ford's algorithm can solve all kinds of valid SSSP problem variants, albeit with a rather slow running time (try Example: Bellman Ford's Killer).


The only variant that Bellman Ford's cannot solve is when the input graph contains negative weight cycle reachable from the source vertex (the SSSP values from vertices reachable from such negative cycle(s) are thus not well defined as we can stay in that cycle forever to get -∞ value). However, Bellman Ford's can be used to detect if the input graph contains at least one negative weight cycle reachable from the source vertex.


Bellman Ford's algorithm will produce correct answer for all our Example Graphs except Example Graph: CP3 4.19 but Bellman Ford's algorithm will be able to detect that Example Graph: CP3 4.19 contains at least one negative weight cycle reachable from a default source vertex 0.

X Esc
Prev
Next

The O((V+E) log V) Original Dijkstra's algorithm is the most frequently used SSSP algorithm for typical input: Directed weighted graph that has no negative weight edge at all (which is commonly found in real life, try Example Graph: CP3 4.17, Bellman Ford's Killer, DAG).


When the input graph contains a negative weight edge, the original version of Dijkstra's algorithm can produce wrong answer (try Example: CP3 4.18, Dijkstra's Killer).


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 not negative weight cycle (try Example: CP3 4.18, but very slow on Dijkstra's Killer). It will also be trapped in infinite loop for directed weighted graphs that have at least one negative weight cycle reachable from the source vertex (try Example: CP3 4.19).

X Esc
Prev
Next

The O(V+E) Breadth-First Search (BFS) algorithm can solve special case of SSSP problem, i.e. when the input graph is unweighted (all edges have unit weight 1, try Example: CP3 4.3 or CP3 4.4) or constant weighted (all edges have the same constant weight).


BFS will very likely produce wrong answer when run on weighted graphs and we will display a warning message although we do not prevent you from trying this feature (try Example: CP3 4.3 or CP3 4.4, then try running BFS on all other weighted graphs).

X Esc
Prev
Next

The O(V+E) Depth-First Search (DFS) algorithm can solve special case of SSSP problem, i.e. when the input graph is a tree thus any path that connects the source vertex to another vertex is the shortest path.


DFS will very likely produce wrong answer when run on any other graphs that are not Tree and we will display a warning message although we do not prevent you from trying this feature (try Example: CP3 4.40, which is an undirected weighted tree and then try running DFS on all other non-tree graphs).

X Esc
Prev
Next

The O(V+E) Dynamic Programming algorithm can solve special case of SSSP problem, i.e. when the input graph is a Directed Acyclic Graph (DAG) thus we can find at least one topological order of the DAG and process the edge relaxation according to this topological order.


Dynamic Programming will not work for any non DAG as non DAG contains at least one cycle and thus no topological order within that cycle (try Example Graphs that are DAGs: CP3 4.17, CP3 4.18, Bellman Ford's Killer, Dijkstra's Killer, and DAG).

X Esc
Prev
Next

As the action is being carried out, each step will be described in the status panel.

X Esc
Prev
Next

You can also follow the pseudocode highlights to trace the algorithm.

X Esc
Prev
Next

Control the animation with the player controls! Keyboard shortcuts are:

Spacebar: play/pause/replay
Left/right arrows: step backward/step forward
-/+: decrease/increase speed
X Esc
Prev
Next

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.

X Esc
Prev