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?
>Solution :
check this code:
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.target = target # 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
parent = [-1] * self.size # initialize parent array
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.adj_matrix[x][i] > 0 and shortest_path_arr[i] == False and distance[i] > distance[x] + self.adj_matrix[x][i]:
distance[i] = distance[x] + self.adj_matrix[x][i]
parent[i] = x # update parent array
# store shortest path for each node
shortest_path = {}
for node in range(self.size):
path = []
curr = node
while curr != -1:
path.insert(0, curr)
curr = parent[curr]
shortest_path[node] = path
return distance[self.target], shortest_path