Dijkstra Shortest Paths

Problem

Given n nodes, directed edges as [u, v, w] triples with non-negative weights, and a source node, return the shortest distance from the source to every node, using -1 for unreachable nodes.

Use a min-heap of (distance, node) pairs and settle a node the first time it is popped. Parallel edges are allowed.

Hint

A node is final when it is popped; later heap entries for it can be ignored.

Test cases

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: [1,[],0]

expected: [0]

case 3

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

expected: [0,1,2]

case 4

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

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

case 5

in: [3,[],1]

expected: [-1,0,-1]

Starter codePython

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

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