Dijkstra Relaxation Count

Problem

Count how many times Dijkstra strictly improves a tentative distance.

edges is a directed [u, v, w] list with positive weights and the heap always pops the smallest (distance, node) pair. Every time a popped edge d + w beats the current dist[v], count one improvement and push the new pair. Return the total count, which is 0 when no edge leaves the source.

Hint

A node can be improved several times, so count every strict decrease, not just the final values.

Test cases

case 1

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

expected: 5

case 2

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

expected: 2

case 3

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

expected: 1

case 4

in: [1,[],0]

expected: 0

case 5

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

expected: 3

Starter codePython

import heapq

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

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