Логотип AnimGAnimG

Dijkstra's Shortest Path

Аудитория: Software EngineerКатегория: Computer Science

Описание

Visualizes Dijkstra's algorithm on a weighted directed graph with 6 nodes. The animation shows the priority queue (min-heap), greedy node exploration, distance table updates at each step, and the final shortest path tree highlighted in gold.

Вдохновлены этой анимацией?

Dijkstra's Shortest Path

Description

Visualizes Dijkstra's algorithm on a weighted directed graph with 6 nodes. The animation shows the priority queue (min-heap), greedy node exploration, distance table updates at each step, and the final shortest path tree highlighted in gold.

Phases

# Phase Name Duration Description
1 Intro 3s Title and graph displayed with edge weights
2 Initialization 4s Source node highlighted, distance table initialized (0 for source, ∞ for rest)
3 Priority Queue 3s Priority queue shown with initial entry
4 Exploration Loop 24s Iteratively: dequeue minimum, relax edges, update distances and PQ
5 Final Path 6s Shortest path from source to all nodes highlighted in gold
6 Outro 4s Summary of distances shown

Layout

+--------------------------------------------------+
|  Title: Dijkstra's Shortest Path                 |
+--------------------------------------------------+
|                                                  |
|  Graph (center-left):                            |
|       A                                          |
|      / \                                         |
|     B   C                                        |
|    / \ / \                                       |
|   D   E   F                                      |
|                                                  |
|  Distance Table (right):                         |
|  Node | Dist | Prev                              |
|  A    |  0   |  -                                |
|  B    |  ∞   |  -                                |
|  ...                                             |
|                                                  |
|  Priority Queue (bottom-right):                  |
|  [(0,A), ...]                                    |
+--------------------------------------------------+

Area Descriptions

  • Center-left: Graph visualization with weighted directed edges
  • Right panel: Distance table updating at each step
  • Bottom panel: Priority queue contents

Assets & Dependencies

  • Fonts: LaTeX / sans-serif
  • Manim version: ManimCE 0.19.1

Notes

  • Visited nodes turn green
  • Current node being processed turns yellow
  • Relaxed edges turn cyan
  • Final shortest path edges turn gold with increased stroke width