Part 1 here.

Now that we have the graph, we can start the animation of Dijkstra’s algorithm. Most of this will be done through changing properties in objects of the Graph class and showing these changes.

This is our goal:

Updating Vertices

When we visit each vertex, we can highlight that vertex to make it clear which vertex is the current one. We can use the Flash function in Manim:

rad = 0.5
c1 = Circle(rad)
self.add(c1)
self.play(Flash(c1, flash_radius=rad))

The bottom left vertex, labeled a, is our starting vertex. We can flash it first. In the Graph class, this vertex is stored in the vertices object as the first element. We can call it as graph1.vertices[v1]. At the same time, turn the vertex yellow to indicate that it is our current vertex.

v1 = 0
graph1.vertices[v1].set_fill(YELLOW, opacity=1.0)
self.play(Flash(graph1.vertices[v1], flash_radius=graph1_vlist[v1][0]+0.1))

The flash animation would look like this in our graph:

Arrows

Now we traverse through the current vertex’s neighbors. Throughout the entire algorithm we will traverse through each edge once. We can reorder the previous graph1_llist to the order of edges the algorithm traverses through:

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

(My list from part 1 is already ordered properly).

For each edge in the list, we want to show an arrow pointing from the first vertex to the second. We can do this by creating an Arrow object:

# v1 and v2 are objects
arrow = Arrow(v1, v2, color=RED)

We can define a function that blinks this Arrow object in the Dijkstra class:

# given an object, blink it five times.
def blink(self, obj):
    for i in range(5):
        self.add(obj)
        self.wait(0.25)
        self.remove(obj)
        self.wait(0.25)

Putting these together:

v1 = 0
v2 = 1
arrow = Arrow(graph1.vertices[v1], graph1.vertices[v2], color=RED)
self.blink(arrow)

And here is the result:

We can now create a loop that traverses through each edge of the graph, in the order we previously defined. We first determine if the current vertex has been updated. If it has, we flash the new current vertex. Then, we create an Arrow object corresponding to the current edge, and use the blink function to show it:

prevv = -1
for v1, v2 in graph1_elist:
    if prevv != v1:
        if prevv != -1:
            graph1.vertices[prevv].set_fill(RED, opacity=1.0)
        graph1.vertices[v1].set_fill(YELLOW, opacity=1.0)
        self.play(Flash(graph1.vertices[v1], flash_radius=graph1_vlist[v1][0]+0.1))
        self.wait(0.5)
        prevv = v1

    arrow = Arrow(graph1.vertices[v1], graph1.vertices[v2], color=RED)
    self.blink(arrow)

The video currently looks like this:

Updating Distances

Next up is updating the distances.

The distances are stored as the dists object in the Graph class. To update a distance, we would need to change its text content and color, and possibly its location. To update the first distance, for example, we can do this:

v2 = 1
str1 = "5"
x = 3.0
y = 2.0
graph1.dists[v2] = Tex(str1, font_size=25, color=TEAL_A).shift(RIGHT*x + UP*y)

Because some of the updated text does not fit into its original location, we would need to update the location for some of the distances. To organize these locations, we can create a new list to keep track of what needs to be updated. You can also append them to existing lists.

# each entry corresponds to its edge in graph1_elist.
# each time we replace the text twice.
# format of the entries:
# text to replace 1st time, text to replace 2nd time, x, y.
graph1_clist = [[r"0 + 7 \textless\ inf", r"7", -0.2, -2.3],
                [r"0 + 14 \textless\ inf", r"14", 0.3, 0.6],
                [r"0 + 9 \textless\ inf", r"9", -2.7, 2.0],
                [r"7 + 10 \textgreater\ 14", r"14", 0.3, 0.6],
                [r"7 + 15 \textless\ inf", r"22", 4.5, 0.9],
                [r"14 + 11 \textgreater\ 22", r"22", 4.5, 0.9],
                [r"14 + 2 \textgreater\ 9", r"9", -2.7, 2.0],
                [r"22 + 6 \textless\ inf", r"28", 0.8, 3.0],
                [r"9 + 9 \textless\ 28", r"18", 0.8, 3.0]]

Now, in our loop, add the updating distances. Each update will occur after the arrow has been shown.

# This should be inside the for loop we created earlier
graph1.dists[v2] = Tex(str1, font_size=25, color=TEAL_A).shift(RIGHT*x + UP*y)
self.wait(1.5)
graph1.dists[v2] = Tex(str2, font_size=27, color=BLUE).shift(RIGHT*x + UP*y)
self.wait(1.5)

The loop looks like this now:

prevv = -1
for (v1, v2), (str1, str2, x, y) in zip(graph1_elist, graph1_clist):
    if prevv != v1:
        if prevv != -1:
            graph1.vertices[prevv].set_fill(RED, opacity=1.0)
        graph1.vertices[v1].set_fill(YELLOW, opacity=1.0)
        self.play(Flash(graph1.vertices[v1], flash_radius=graph1_vlist[v1][0]+0.1))
        self.wait(0.5)
        prevv = v1

    arrow = Arrow(graph1.vertices[v1], graph1.vertices[v2], color=RED)
    self.flash_obj(arrow)

    graph1.dists[v2] = Tex(str1, font_size=25, color=TEAL_A).shift(RIGHT*x + UP*y)
    self.wait(1.5)
    graph1.dists[v2] = Tex(str2, font_size=27, color=BLUE).shift(RIGHT*x + UP*y)
    self.wait(1.5)

The final product looks like this: