In this article we’re going to discuss how to draw an animation of Dijkstra’s algorithm in Manim.

We want to draw an undirected, weighted graph that can be used to demonstrate Dijkstra’s algorithm.

To start, we would need to draw a few things:

  • The vertices

  • The edges

  • The weights

  • The distances from the starting vertex

The graph would look like this:

 

Before We Begin

Importing the relevant packages:

from manim import *
from manim.utils.color import Colors

Before we start, let’s create the class that will contain our actions. We’ll name it class Dijkstra.

class Dijkstra(Scene):
    def construct(self):
        # ...

 

Vertices

We’ll start with the vertices first. We will manually define a few properties for each vertex: its radius, color, opacity, and x-y coordinates. You can add or remove some of these properties if you wish, but I’m sticking to them for now.

Once we decide what properties we want to edit, we can create a 2D list like this:

# radius, color, opacity, X, Y
graph1_vlist = [[0.3, WHITE, 1, -3.0, -2.0],
                [0.3, WHITE, 1, 0.3, -2.8],
                [0.3, WHITE, 1, 0.0, 0.0],
                [0.3, WHITE, 1, 4.0, 0.3],
                [0.3, WHITE, 1, 1.3, 2.5],
                [0.3, WHITE, 1, -2.5, 1.5]]

And let’s create a class to store the graph:

class Graph:
    def __init__(self, scene, vertices_list):
        self.scene = scene

        # set up vertices
        self.vertices = VGroup()
        self.add_vertices(vertices_list)

        # Given a list, add vertices accordingly
        def add_vertices(self, list):
            for rad, color, opac, x, y in list:
                v = Circle(radius=rad).set_fill(color, opacity=opac).shift(RIGHT*x + UP*y)
                self.vertices.add(v)

Note: RIGHT and UP are vectors defined in the manim package.

Here, the graph receives two inputs upon initialization: the scene, which we will use later, and the list of vertices. The list is converted via the function add_vertices to create circles representing the vertices. Now the vertices are stored in the self.vertices group.

Next, we’ll need to draw the vertices. We can use the Create function:

c1 = Circle(radius=1).set_fill(WHITE, opacity=1)
self.play(Create(c1))

To simultaneously create all the vertices in the self.vertices group, we’ll need to define a bunch of animations, put them in an array, and play the array.

The graph class now looks like this:

class Graph:
    def __init__(self, scene, vertices_list):
        self.scene = scene

        # set up vertices
        self.vertices = VGroup()
        self.add_vertices(vertices_list)

        # Given a list, add vertices accordingly
        def add_vertices(self, list):
            for rad, color, opac, x, y in list:
                v = Circle(radius=rad).set_fill(color, opacity=opac).shift(RIGHT*x + UP*y)
                self.vertices.add(v)

    # Simultaneously create all vertices
    def create_vertices(self):
        animations = []
        for i in range(len(self.vertices)): 
            animations.append(Create(self.vertices[i]))
        self.scene.play(*animations)

Notice that in the function create_vertices we have to use self.scene to refer to the Scene object in the Dijkstra class to play the animations.

Updating our Dijkstra class:

class Dijkstra(Scene):
    def construct(self):

        # radius, color, opacity, X, Y
        graph1_vlist = [[0.3, WHITE, 1, -3.0, -2.0],
                        [0.3, WHITE, 1, 0.3, -2.8],
                        [0.3, WHITE, 1, 0.0, 0.0],
                        [0.3, WHITE, 1, 4.0, 0.3],
                        [0.3, WHITE, 1, 1.3, 2.5],
                        [0.3, WHITE, 1, -2.5, 1.5]]

        graph1 = Graph(self, graph1_vlist)
        graph1.create_vertices()

Our animation now looks like this:

 

Edges

Next, we’ll draw the edges of the graph. First, make an adjacency list for the graph:

# adjacency list
graph1_elist = [[0,1],
                [0,2],
                [0,5],
                [1,2],
                [1,3],
                [2,3],
                [2,5],
                [3,4],
                [5,4]]

In the Graph class, we can define a function that will convert the adjacency list to Line objects. Don’t forget to add this list to the initialization inputs in the Graph class.

def add_edges(self, list):
    for v1, v2 in list:
        l = Line(self.vertices[v1], self.vertices[v2])
        self.edges.add(l)

And to draw the edges:

def show_edges(self):
    self.scene.play(FadeIn(self.edges))

To recap, our Graph class looks like this now:

class Graph:
    def __init__(self, scene, vertices_list, edges_list):
        self.scene = scene

        # set up vertices
        self.vertices = VGroup()
        self.add_vertices(vertices_list) 

        # set up edges
        self.edges = VGroup()
        self.add_edges(edges_list)

    # Given a list, add vertices accordingly
    def add_vertices(self, list):
        for rad, color, opac, x, y in list:
            v = Circle(radius=rad).set_fill(color, opacity=opac).shift(RIGHT*x + UP*y)
            self.vertices.add(v)

    def add_edges(self, list):
        for v1, v2 in list:
            l = Line(self.vertices[v1], self.vertices[v2])
            self.edges.add(l)

    # Simultaneously create all vertices
    def create_vertices(self):
        animations = []
        for i in range(len(self.vertices)): 
            animations.append(Create(self.vertices[i]))
        self.scene.play(*animations)

    # Show edges
    def show_edges(self):
        self.scene.play(FadeIn(self.edges))

By calling the show_edges function we defined earlier, in the Dijkstra class:

graph1.show_edges()

We can draw the edges like this:

 

Weights and Distances

Next up are the weights and distances. Again we can make lists for these variables. For the distances we’ll initialize them to infinity at the start, except the starting vertex whose distance will be 0.

graph1_wlist = [
                # each entry corresponds to its line in line list
                [r"7", 35, WHITE, -1.5, -2.8],
                [r"9", 35, WHITE, -3.1, -0.3],
                [r"14", 35, WHITE, -1.7, -0.7], 
                [r"10", 35, WHITE, -0.1, -1.5],
                [r"15", 35, WHITE, 1.7, -1.2],
                [r"11", 35, WHITE, 1.9, 0.4],
                [r"2", 35, WHITE, -1.0, 0.9],
                [r"6", 35, WHITE, 2.7, 1.7],
                [r"9", 35, WHITE, -0.7, 2.3],

                # start and end vertices
                [r"a", 35, YELLOW, -3.0, -2.6],
                [r"b", 35, YELLOW, 1.8, 2.8]]
        
graph1_dlist = [[r"0", 27, BLUE, -3.5, -1.5],
                [r"inf", 27, BLUE, -0.2, -2.3],
                [r"inf", 27, BLUE, 0.0, 0.6],
                [r"inf", 27, BLUE, 4.0, 0.9],
                [r"inf", 27, BLUE, 0.8, 3.0],
                [r"inf", 27, BLUE, -3.0, 2.0]]

If you wish, you can also combine the edges list and the weights list, since they will be unchanged throughout the video and the weights correspond to the edges. But I’m going to leave them like this for now.

Once again we can convert them to objects in Manim, this time Tex objects. (You can also use other text objects in Manim.)

def add_weights(self, list):
    for string, size, col, x, y in list:
        text = Tex(string, font_size=size, color=col).shift(RIGHT*x + UP*y)
        self.weights.add(text)
    
def add_dists(self, list):
    for string, size, col, x, y in list:
        text = Tex(string, font_size=size, color=col).shift(RIGHT*x + UP*y)
        self.dists.add(text)

Define some functions in the Graph class so we can show them:

def ShowWeights(self):
    self.scene.play(FadeIn(self.weights))

def ShowDists(self):
    self.scene.play(FadeIn(self.dists))

Now in the Dijkstra class, call the functions:

graph1.ShowWeights()
graph1.ShowDists()

The video now looks like this:

We’ve drawn the graph, but we still have more animation to do. Continue to part 2 here.