Visual Algorithms • UX/UI Case Study

Dijkstra’s Algorithm → Spanning Tree

Step-by-step shortest-path discovery, then a clean visualization of the resulting shortest-path tree.

This project teaches Dijkstra’s Algorithm as a sequence of small, visible decisions: selecting the next closest node, relaxing edges, and updating tentative distances. After the final distances stabilize, the visualization extracts the spanning tree of shortest paths (often called a shortest-path tree) from the chosen start node.

The UI supports beginners by separating “the process” (relaxation steps) from “the result” (the spanning tree), reducing confusion between shortest paths and minimum spanning trees.

Watch Demo

Quick Facts

Goal

Help learners understand relaxation and how the shortest-path tree is formed.

Audience

CS beginners learning graphs + algorithmic thinking.

My Role

UX/UI design, instructional flow, animation planning and implementation.

Tools

Manim (Python), captions, step state design, final tree extraction.

Concept Clarity

Dijkstra’s Algorithm

Finds the shortest distance from a chosen start node to every other node (non-negative edge weights).

Shortest-Path Spanning Tree

The set of “parent” edges that produced those shortest distances. It spans all reachable nodes from the start. (Not the same as a Minimum Spanning Tree.)

Step-by-Step Rules Shown in the Video

Initialize: distance(start)=0, all others = ∞. Parent pointers empty.
Select the unvisited node with the smallest tentative distance.
Relax edges: for each neighbor, try to improve its distance: if dist[u] + w(u,v) < dist[v], update dist[v] and set parent[v] = u.
Mark visited: lock the node (its shortest distance is final).
Repeat until all nodes are visited or unreachable nodes remain at ∞.

Key UX/UI Decisions

Two-phase structure

Phase 1: algorithm steps. Phase 2: extract and display the spanning tree result.

Consistent feedback

Every relaxation shows “old distance → new distance” so updates feel justified.

Visual hierarchy

Visited nodes vs frontier vs updated neighbor are visually distinct.

Avoid a common confusion

Explicitly labels the result as “Shortest-Path Tree” (not MST).

Demo / Media

Animation

Part 1 shows Dijkstra’s Algorithm step-by-step (select node → relax edges → update distances). Part 2 extracts the final shortest-path spanning tree using the parent pointers created during relaxations.

How the Spanning Tree is Created (After the Steps)

During relaxation, every time a node’s distance improves, the visualization records a parent: parent[v] = u. After the algorithm finishes, the spanning tree is simply the set of edges:

For each node v ≠ start that is reachable, draw the edge (parent[v], v).
Those parent edges form a tree (or forest if some nodes are unreachable).
This tree represents the shortest path from the start to every node (follow parents backward).

Outcome

Learners can (1) explain why a distance update happened, (2) predict the next selected node, and (3) understand that the final spanning tree is built from parent pointers—not from “choosing the smallest edges like Kruskal.”

Next Steps

Add a small on-screen “Distance Table” (node, dist, parent) synchronized with the animation.
Add checkpoints: “Which edge relaxation updated the distance?”
Add alternate start nodes to show how the shortest-path tree changes.