Shortest Path (Dijkstra)

Join me to stay up-to-date and get my new articles delivered to your inbox by subscribing here.

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