Dijkstra Directed Distances

Problem

Compute single-source shortest distances in a directed graph with positive weights.

edges is a list of [u, v, w] triples where w > 0, and source is a node index. Return the distance list in node order, using -1 for nodes that cannot be reached from the source. The method must be Dijkstra with a heap, not Bellman-Ford.

Hint

Use -1 to mean infinite, and skip heap entries that are stale.

Test cases

case 1

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

expected: [0,3,1,4]

case 2

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

expected: [0,1,-1]

case 3

in: [2,[[0,1,7],[1,0,2]],1]

expected: [2,0]

case 4

in: [1,[],0]

expected: [0]

case 5

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

expected: [0,3,2]

Starter codePython

import heapq

def dijkstra_distances(n, edges, source):
    # Your code here
    pass

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