[グラフ] ダイクストラ法
最短経路問題 グラフ理論における最短経路問題（さいたんけいろもんだい、英:shortest path problem）とは、重み付きグラフの与えられた2つのノード間を結ぶ経路の中で、重みが最小の経路を求める最適化問題である。 出典: フリー百科事典『...
「ダイクストラ法」一覧
[Python] ABC016 C
問題 C - 友達の友達 回答 友達の友達を数える 集合を使い、友達の友達を探索して数えます。 import collections N, M = map(int, input().split()) adjacent_dict = col...
[Python] ABC012 D ダイクストラ法
問題 D - バスと避けられない運命 回答 ダイクストラ法を使います。 Python では TLE でしたが、PyPy では AC でした。 import collections import sys import heapq N, ...
[Python] ダイクストラ法
Python で、ダイクストラ法を使って、重み付きの有向グラフの単一始点最短経路問題を解きます。 以下の続きです。 ダイクストラ法 ダイクストラ法（だいくすとらほう、英: Dijkstra's algorithm）はグラフ理論における辺の重みが...