October 28, 2022
Coding & Algorithm Interview Data Structures & Algorithms
Python Implementation
This implementation uses an indexed minimum priority queue data structure.
class SHORTEST_PATH_DIJKSTRA:
INF = 1e7
def __init__(self, g, s):
self.dist_to = [self.INF] * len(g)
self.edge_to = [-1] * len(g)
self.dist_to[s] = 0
self.pq = INDEXED_MINIMUM_PRIORITY_QUEUE()
self.pq.push(s, self.dist_to[s])
while(not self.pq.is_empty()):
vertex_from, _ = self.pq.pop()
for edge in g[vertex_from]:
self.__relax(vertex_from, edge)
def __relax(self, vertex_from, edge):
vertex_to = edge[0]
edge_weight = edge[1]
if self.dist_to[vertex_to] > self.dist_to[vertex_from] + edge_weight:
self.dist_to[vertex_to] = self.dist_to[vertex_from] + edge_weight
self.edge_to[vertex_to] = vertex_from
self.pq.push(vertex_to, self.dist_to[vertex_to])
def has_path_to(self, v):
return self.dist_to[v] < self.INF
def dist_to(self, v):
return self.dist_to[v]
def path_to(self, v):
if not self.has_path_to(v): return None
path = []
edge = self.edge_to[v]
while (edge != -1):
path.append(edge)
edge = self.edge_to[edge]
return path
