This is a classic algorithm, and from the archive! It is just Dijkstra’s algorithm, and in fact this sort of formulation is exactly how my undergrad algorithms professor tried to have us develop the intuition of how it worked. I appreciate that this formulation at least suggests something of an approachable motivation, measuring network latency and similar.

class Solution(object):
    def networkDelayTime(self, times, n, k):
        # Cache neighbors and their weights
        neighbors = {u : [] for u, _, _ in times}
        for u, v, w in times:
            neighbors[u].append((v, w))
            
        # Djikstra's
        worklist = [k]
        cost = {k: 0} # cost to reach k
        while worklist:
            u = worklist.pop()
            c = cost[u]
            if u not in neighbors:
                continue # its a sink
            for v, w in neighbors[u]:
                if v not in cost or cost[v] > w + c:
                    cost[v] = w + c
                    worklist.append(v)
        
        # Return requested result
        if len(cost) != n:
            return -1
        return max(cost.values())

Discussion

This was originally “easy” on Leetcode, according to my notes. I think with some thought this can be an approachable, or independently derivable algorithm. (A different professor I had pointed to Dijkstra as an advantage of being early on in a new field: if you are, you can name all the “obvious” results after yourself!) I wouldn’t say this is an obvious algorithm, but the idea that you “update your neighbors” when you receive new information is something that is worth getting a measurement on, interview-ish speaking.

Glad to finally get another graph algorithm on the books. The others are here.