Dijkstra with Heap

Problem

Compute single-source shortest paths in a directed weighted graph with positive edge weights using Dijkstra's algorithm and a min-heap.

edges is a list of [u, v, w] triples. Return a list of distances from src in node order, using -1 for unreachable nodes.

Hint

Skip stale heap entries whose distance is larger than the recorded best.

case 1

in: [5,[[0,1,4],[0,2,1],[2,1,2],[1,3,1],[2,3,5],[3,4,3]],0]

expected: [0,3,1,4,7]

case 2

in: [4,[[0,1,1],[2,3,1]],0]

expected: [0,1,-1,-1]

case 3

in: [1,[],0]

expected: [0]

case 4

in: [3,[[0,1,10],[0,2,1],[2,1,1]],0]

expected: [0,2,1]

Starter codePython

import heapq
def dijkstra(n, edges, src):
    # Your code here
    pass

4 test cases · run your code against them in the editor