Floyd-Warshall Update Count

Problem

Count how many strict distance improvements the Floyd-Warshall triple loop makes.

edges is a directed [u, v, w] list with arbitrary weights and the diagonal starts at 0. For every (k, i, j) triple, count an update when dist[i][k] + dist[k][j] < dist[i][j] before the write. Skip triples touching infinity. Return the total number of updates.

Hint

A shorter route through k must beat the current entry strictly; count after the comparison succeeds.

Test cases

case 1

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

expected: 1

case 2

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

expected: 0

case 3

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

expected: 3

case 4

in: [1,[]]

expected: 0

case 5

in: [2,[]]

expected: 0

Starter codePython

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

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