class Queue:
  def __init__(self):
    self.list = []

  def enqueue(self, item, distance):
    self.list.append((item, distance))
    self.list.sort(key = lambda x: x[1])

  def dequeue(self):
    return self.list.pop(0)[0]

  def isEmpty(self):
    return len(self.list) == 0
  
def dijkstra(graph, src):
  dist = {}
  visited = {}
  parent = {}
  queue = Queue()

  for node in graph:
    dist[node] = float('inf')
    visited[node] = False
    parent[node] = None

  dist[src] = 0

  queue.enqueue(src, 0)

  while (not queue.isEmpty()):
    v = queue.dequeue()
    visited[v] = True
    
    for neighbor in graph[v]:
      alt = dist[v] + graph[v][neighbor]
      if not visited[neighbor] and alt < dist[neighbor]:
        dist[neighbor] = alt
        parent[neighbor] = v
        queue.enqueue(neighbor, alt)

  return (dist, parent)

def reconstructPath(parent, dest):
  path = []
  at = dest

  while (parent[at]):
    path.insert(0, at)
    at = parent[at]

  path.insert(0, at)
  
  return path

graph = {
  "A": { "B": 4, "C": 2 },
  "B": { "A": 4, "C": 1, "D": 5 },
  "C": { "A": 2, "B": 1, "D": 1 },
  "D": { "B": 5, "C": 1 }
}
source = 'A'
destination = 'D'

(dist, parent) = dijkstra(graph, source)

print(reconstructPath(parent, destination))

// Javascript implementation

class Queue {
  constructor() {
    this.list = [];
  }

  enqueue(item, distance) {
    this.list.push({item, distance});
    this.list.sort((a, b) => a.distance - b.distance);
  }

  dequeue() {
    return this.list.shift().item;
  }

  isEmpty() {
    return this.list.length === 0;
  }
}

function dijkstra(graph, src) {
  const dist = {};
  const visited = {};
  const parent = {};
  const queue = new Queue();

  for (const node in graph) {
    dist[node] = Infinity;
    visited[node] = false;
    parent[node] = null;
  }

  dist[src] = 0;

  queue.enqueue(src, 0);

  while (!queue.isEmpty()) {
    const v = queue.dequeue();
    visited[v] = true;

    for (const neighbor in graph[v]) {
      const alt = dist[v] + graph[v][neighbor];
      if (!visited[neighbor] && alt < dist[neighbor]) {
        dist[neighbor] = alt;
        parent[neighbor] = v;
        queue.enqueue(neighbor, alt);
      }
    }
  }

  return { dist, parent };
}

function reconstructPath(parent, dest) {
  const path = [];
  let at = dest;

  while (parent[at]) {
    path.unshift(at);
    at = parent[at];
  }

  path.unshift(at);
  
  return path;
}

const graph = {
  A: { B: 4, C: 2 },
  B: { A: 4, C: 1, D: 5 },
  C: { A: 2, B: 1, D: 1 },
  D: { B: 5, C: 1 }
};
const source = 'A';
const destination = 'D';

const { dist, parent } = dijkstra(graph, source);

console.log(reconstructPath(parent, destination));