network-delay-time.py

https://leetcode.com/problems/network-delay-time/
# Bellman-Ford shortest path algorithm
class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        dists = [float('inf') for _ in range(0, n + 1)]
        dists[k] = 0
        
        for i in range(n-1):
            # print(f"loop: {i}")
            for u, v, w in times:
                if dists[u] != float('inf'):
                    # if dists[u] + w < dists[v]:
                    #     print(f"updating with lower weight: {u}-{v} with {dists[u] + w}")
                    dists[v] = min(dists[v], dists[u] + w)
                # else:
                #     print(f"no existing edge to {u}, can't extend to {v}")
        
        min_cost = 0
        for weight in dists[1:]:
            if weight == float('inf'):
                return -1

            min_cost = max(min_cost, weight)
        
        return min_cost