【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

まとめ

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