ダイクストラとポテンシャルのはなし - niuez’s diary

はじめまして, niuezといいます. 競プロを少ししています. 最近勉強したことのメモ書きをしておきます. ダイクストラ法 ダイクストラ法(Dijkstra)は負の長さの無いグラフで始点からの最短距離を求めるアルゴリズムです. 具体的には 距離が未確定の頂点の中で一番小さいものを選び, 距離を確定させる. 選んだ頂点から距離が未確定の頂点に伸びる辺で, 未確定な距離をより短いものに更新する. を繰り返します. これを実装すると $O(N)$ですが, よく知られるダイクストラの計算量は $O((E+ V) \log E)$ です(heapとかを使う). #include <set> #include <queue> #include <vector> struct edge { int u,v; int dist; }; std::vector<int> dijkstra(const st