743. Network Delay Time

https://leetcode.com/problems/network-delay-time/

Python

DFS

from math import inf


class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        reach_times = [inf for i in range(n)]
        reach_times[k-1] = 0

        # Convert the graph from a list into dict, for better matching query later
        mapper = dict()
        for source, target, latency in times:
            if source not in mapper:
                mapper[source] = dict()
            mapper[source][target] = min(mapper[source].get(target, inf), latency)

        # DFS, or call it backtracking, go through all possible edges
        def dfs(source: int, accu: int):
            if source not in mapper:
                return

            for target in mapper[source]:
                new_accu = accu + mapper[source][target]

                # Only go deeper while the known cost of path is higher
                if reach_times[target-1] > new_accu:
                    reach_times[target-1] = new_accu
                    dfs(target, new_accu)

        dfs(k, 0)

        max_latency = max(reach_times)
        return max_latency if max_latency < inf else -1

Dijkstra Algorithm

(TODO)