サクサク読めて、アプリ限定の機能も多数!
トップへ戻る
Appleイベント
take44444.github.io
単一始点最短路(Dijkstra法) 重みが全て\(0\)以上である任意の重み付きグラフ\(G\)における単一始点最短路は,Dijkstra法によって\(O(|E| \log |V|)\)で求めることができる. 単一始点最短路とは,あるノード\(s \in G\)から,\(G\)に含まれる任意のノードまでの最短路である.以降始点を\(s\)と呼ぶ. 説明 Dijkstra法の説明と正当性の証明を同時にするような形で説明を書く. 以下の説明では,あるノード\(i\)について,\(s\)から\(i\)までの最短路長を\(d_{s→i}\)と表記する.また,あるノード\(i\)から出てあるノード\(j\)に入る(有向)辺の重みを\(e_{i→j}\)と表記する. Dijkstra法では,\(s\)からの最短路を,最短路長が小さいノードから順に求めていく.つまり,任意の時点で,最短路が求まっている
グラフ問題 %%{init: {"flowchart" : { "curve" : "basis" } } }%% graph LR 1((1)) --- 2((2)) 2((2)) --- 3((3)) 2((2)) --- 4((4)) 3((3)) --- 1((1)) 3((3)) --- 4((4)) 4((4)) --- 1((1)) グラフは,ノード(頂点)と,それらを繋ぐエッジ(辺)からなる.このドキュメントでは,特に断りのない限りグラフのノード集合を\(V\),辺集合を\(E\)とする.ノード数は\(|V|\),辺数は\(|E|\)で表される. グラフでよく出る単語 パス(道) あるノードから始めて,いくつかの辺をたどって,あるノードにたどり着くまでのノードの列をパス(道)という.有向グラフの場合,向きに従ってたどる必要がある. また,同じノードを2回通らないパスを単純パ
はじめに このドキュメントは,主に競技プログラミングで出題される問題を解く際に利用できるアルゴリズムやデータ構造をまとめたものです.特定の問題にはあまりフォーカスしないため,問題を解く際の考察の仕方等の内容はありません.詳しく,正確に,分かりやすく書いていこうと思っています. このドキュメントは執筆途中です. 想定する読者 C++を用いたプログラミングに慣れている方を読者として想定しており,C++言語の仕様や,文法にはあまり触れません.また,計算量という用語についても説明しません.ただし,償却計算量など,計算量の見積もりが複雑なものについては必要に応じて説明します. コードについて このドキュメントで登場するコードは,可読性向上のため,以下のようなコードがファイルの先頭に記述してあることを前提としています.また,適切な問題を用いてコードの検証がなされている場合は,コード周辺にのように,検証
このページを最初にブックマークしてみませんか?
『take44444.github.io』の新着エントリーを見る
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く