LeetCode #743. Network Delay Time | ダイクストラの問題

【LeetCode #743】Network Delay Time

はじめに

GW 明けだったので仕事を早めに切り上げましたが，daily 解くのに手こずりました…．
そして！結構難しく感じたので，今日は daily ではなく類題の典型問題を取り上げようと思います！

問題概要

1 から n の n 個のノードが与えられて，ノード k から全ノードへ信号を送るとき，最も時間がかかるノードまでの最短到達時間を求める問題（到達不能なノードがあれば -1）

例

入力: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
出力: 2
説明: ノード 4 までの最短経路が 2→3→4 で、合計時間は 2

カテゴリ

難易度： medium
タグ： Depth-First Search，Breadth-First Search，Graph，Heap (Priority Queue)，Shortest Path

解法：ダイクストラ

この問題はダイクストラで解く典型ですね！
ダイクストラについてはまた別で解説しようと思うので，とりあえずこの記事では解いていきます！
今回，有向グラフが与えられるので u->v に対して重み w とするとき，graph[u] = [(v, w)] といった形でグラフの情報を保持し，ダイクストラに臨みます．
各ノードに対する k からの距離を格納するための配列を用意しておき，ダイクストラでは，あるノードと隣接するノードへの距離が，既存の距離のよりも短いものが見つかれば更新していきます．
コードとしては下記になります．

from collections import defaultdict
import heapq
class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        graph = defaultdict(list)
        for u, v, w in times:
            graph[u].append((v, w))

        dist = [float('inf')] * (n+1)
        dist[k] = 0

        time_and_node = [(0, k)]

        while len(time_and_node):
            time, node = heapq.heappop(time_and_node)

            if time > dist[node]:
                continue
            
            for neighbor, weight in graph[node]:
                if dist[neighbor] > time + weight:
                    dist[neighbor] = time + weight
                    heapq.heappush(time_and_node, (dist[neighbor], neighbor))
        max_time = max(dist[1:])
        return max_time if max_time != float('inf') else -1

まとめ

本日はダイクストラを用いる問題について取り上げました！
ちょっとあっさりした内容ですが楽しんでいただけたら幸いです．
またダイクストラ自体については別で取り上げようと思います！
さらに，今日のデイリー問題についても，ダイクストラが理解できていたらその応用で解けるので，近いうちに解説記事を書こうと思います！
ではまた〜！

おまけ

TypeScript ではこうなります．

function networkDelayTime(times: number[][], n: number, k: number): number {
    const graph = new Map<number, number[][]>();
    function pushToMap(key: number, value: number[]) {
        if (!graph.has(key)) {
            graph.set(key, []);
        }
        graph.get(key)!.push(value);
    }
    for (const t of times){
        pushToMap(t[0], [t[1], t[2]]);
    }

    const dist: number[] = Array(n+1).fill(Infinity);
    dist[k] = 0;


    const pq = new MinPriorityQueue<{ a: number, b: number }>(({a}) => a);
    pq.enqueue({a: 0, b: k});
    while (!pq.isEmpty()){
        const {a, b} = pq.dequeue();

        if (a > dist[b]){
            continue;
        }
        if (!graph.has(b)){
            continue;
        }
        const g = graph.get(b);
        for (const [nei, wei] of g){
            if (dist[nei] > a + wei){
                dist[nei] = a + wei;
                pq.enqueue({a: dist[nei], b: nei})
            }
        }
    }
    const maxVal = Math.max(...dist.slice(1));
    if (maxVal === Infinity){
        return -1;
    }
    return maxVal;
};