How to get the path from the Dijkstra algorithm in Python

Question

I took the code for the Dijkstra algorithm from this website and rewrote it for my needs (see below). Now I need to implement a feature that would store the shortest path for each node. I tried implementing it using this code from Geeks for Geeks as guideline but failed miserably. Below is the code for my graph class:

class Graph: 
    max_int = 999999
    def __init__(self, vertices, adj_matrix, start, target):
        # Get the vertices
        self.vertices = vertices

        self.start = start # an integer

        self.size = len(self.vertices)

        self.adj_matrix = adj_matrix # an adjacency matrix 

    def min_distance(self, distance, shortest_path_arr):
        min_distance = self.max_int

        for i in range(self.size):
            if distance[i] < min_distance and shortest_path_arr[i] == False:
                min_distance = distance[i]
                min_index = i
        
        return min_index
    
    def dijkstra(self):
        distance = [self.max_int] * self.size
        distance[self.start] = 0
        shortest_path_arr = [False] * self.size

        for vertex in range(self.size):
            x = self.min_distance(distance, shortest_path_arr)

            shortest_path_arr[x] = True

            for i in range(self.size):
                if self.adjMatrix[x][i] > 0 and shortest_path_arr[i] == False and distance[i] > distance[x] + self.adjMatrix[x][i]:
                    distance[i] = distance[x] + self.adjMatrix[x][i]

What should I do to get the path in the right order?

What happens when you run your code? What do you want it to do instead? Please edit your question to include a minimal reproducible example that we can run ourselves along with this extra explanation. — Code-Apprentice
– Code-Apprentice, Commented Mar 14, 2023 at 18:46
When you visit a new node, you need to record the node you reached the new node from ( predecessor node ). When you find a new, shorter path to a node you need to update the predecessor node. Finally you can find the, reversed, route to any node by backtracking from the end node to the start node. — ravenspoint
– ravenspoint, Commented Mar 14, 2023 at 18:54

Yep Yep · Accepted Answer · 2023-03-24 11:13:45Z

0

You can change the distance from a list of ints to a list of pairs, in python that would be a tuple.
Another way is just to have another list which contains the previous node in the path for every node.
Then you add to this line:

distance[i] = distance[x] + self.adjMatrix[x][i]

And set parent[start]=start, when 'start' is the node you start the search from.
something like previous[i]=x.
Then, you can create a function that gets a node and the parents, and returns the path to it like this:

def get_parents(parent, start, end):
    ans = [end]
    cur = end
    while (parent[cur] != cur):
        cur = parent[cur]
        ans.append(cur)
    return ans[::-1] #we reverse because we added the nodes from the end to the start

answered Mar 24, 2023 at 11:13

Yep Yep

5304 silver badges15 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

How to get the path from the Dijkstra algorithm in Python

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related