All-Pairs Shortest via Repeated Dijkstra

Problem

Compute all-pairs shortest paths in a directed weighted graph with non-negative weights by running Dijkstra from every node.

edges is a list of [u, v, w] triples. Return an n by n matrix of distances with 0 on the diagonal and -1 for unreachable pairs.

Hint

Keep the minimum parallel edge for each ordered pair before relaxing.

case 1

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

expected: [[0,1,3,4],[6,0,2,3],[4,5,0,1],[3,4,6,0]]

case 2

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

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

case 3

in: [3,[]]

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

case 4

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

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

Starter codePython

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

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