¿El código del algoritmo de Dijkstra para almacenar los vértices contenidos en cada camino más corto no se está generando correctamente?

Implementé el algoritmo de Dijkstra para encontrar el camino más corto desde el vértice fuente a todos los demás vértices, y también quería almacenar qué vértices componen cada camino más corto. Para ello, lo hice llevando un registro del predecesor de cada vértice. Puede producir las distancias correctamente, pero como se ve en el siguiente resultado (ignorando las cosas de dulces), dos de los caminos se cambiaron (el camino desde el src hasta el vértice 3 y el camino desde el src hasta el vértice 4). ¿No estoy seguro de por qué no se está produciendo correctamente? Debo haber hecho algo mal mientras almacenaba los predecesores.

Así es como se ve el grafo.

¡El código en Python!

from queue import PriorityQueue

class Graph:
    def __init__(self, num_of_vertices):
        self.v = num_of_vertices
        self.edges = [[-1 for i in range(num_of_vertices)] for j in range(num_of_vertices)]
        self.visited = []

    def add_edge(self, u, v, weight):
        self.edges[u][v] = weight
        self.edges[v][u] = weight

    def dijkstra(self, start_vertex):
        D = {v:float('inf') for v in range(self.v)}
        V = {v:None for v in range(self.v)}
        D[start_vertex] = 0

        pq = PriorityQueue()
        pq.put((0, start_vertex))

        AllPathsList = []

        while not pq.empty():
            (dist, current_vertex) = pq.get()
            self.visited.append(current_vertex)

            for neighbor in range(self.v):
                if self.edges[current_vertex][neighbor] != -1:
                    distance = self.edges[current_vertex][neighbor]
                    if neighbor not in self.visited:
                        old_cost = D[neighbor]
                        new_cost = D[current_vertex] + distance
                        if new_cost < old_cost:
                            pq.put((new_cost, neighbor))
                            D[neighbor] = new_cost
                            V[neighbor] = current_vertex          

            S = []
            u = current_vertex
            while V[u] != None:
                S.insert(0, u)
                u = V[u]

            S.insert(0, start_vertex)
            AllPathsList.append(S)

        return D, AllPathsList

def main():
    g = Graph(6)
    g.add_edge(0, 1, 4)
    g.add_edge(0, 2, 7)
    g.add_edge(1, 2, 11)
    g.add_edge(1, 3, 20)
    g.add_edge(3, 4, 5)
    g.add_edge(3, 5, 6)
    g.add_edge(2, 3, 3)
    g.add_edge(2, 4 ,2)

    CandyPerVertexList = [0, 5, 4, 7, 8, 2]

    D, AllPathsList = g.dijkstra(0)

    for vertex in range(len(D)):
        print("La distancia de mi casa a la casa # ", vertex, " es: ", D[vertex], "min")
        print("El camino en particular es: ", AllPathsList[vertex])

        CandySum = 0
        for num in range(len(AllPathsList[vertex])):
            CandySum = CandySum + CandyPerVertexList[AllPathsList[vertex][num]]
        print("La cantidad de dulces para este camino es: ", CandySum)
        print()

main()

Y el resultado

La distancia de mi casa a la casa #  0 es:  0 min
El camino en particular es:  [0]
La cantidad de dulces para este camino es:  0

La distancia de mi casa a la casa #  1 es:  4 min
El camino en particular es:  [0, 1]
La cantidad de dulces para este camino es:  5

La distancia de mi casa a la casa #  2 es:  7 min
El camino en particular es:  [0, 2]
La cantidad de dulces para este camino es:  4

La distancia de mi casa a la casa #  3 es:  10 min
El camino en particular es:  [0, 2, 3]
La cantidad de dulces para este camino es:  11

La distancia de mi casa a la casa #  4 es:  9 min
El camino en particular es:  [0, 2, 4]
La cantidad de dulces para este camino es:  12

La distancia de mi casa a la casa #  5 es:  16 min
El camino en particular es:  [0, 2, 3, 5]
La cantidad de dulces para este camino es:  13