For Dijkstra’s algorithm, what would be a way to keep track of and store the vertices that each shortest path contains?

I have it coded it out to update all the costs of the edges and such to complete Dijkstra’s main goal of finding the shortest path from the source vertex to all other vertices.

But I what I need help on is figuring out a way to store the vertices that each shortest path contains into an array that contains each path’s vertices that it passed through.

So for example let’s say the shortest path from the source vertex (A) to vertex (Z) is A -> B -> V – > Z. The shortest path goes through vertices B and V in order to get Z. I want to be able to store each of the vertices in that sequence into an array. Then place that array into a bigger list of arrays that will contain all of the sequences. The problem is that I’m not sure where to place that since the while loop below is for updating the costs of the edges.

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)
    
    D, AllPathsList = g.dijkstra(0)

    for vertex in range(len(D)):
        print("Distance from vertex 0 to vertex", vertex, "is:", D[vertex])
        print("Particular path is:", AllPathsList[vertex])
main()

Answer

The usual procedure is to keep track of the predecessor of each vertex. Every time you update the cost for a vertex, you store the vertex that you got there from as its predecessor.

When you’re done, you can follow the chain of predecessors from any vertex back to the source to find the shortest path to it.

Advertisement

Answer