ダイクストラ法 - Bug's Groove
前回のアルゴリズムイントロダクション輪講の話題、単一始点最短路問題から。詳しくは アルゴリズムイントロダクション第24章 単一始点最短路問題 - naoyaのはてなダイアリー へ。その中で丁度前回 書いたプリム法と同じく、ダイクストラ法が最小優先度付きキューを使うので、ちょっといじったらかけるのでは？と思って書いてみました。(相変わらずの乱プログラムご容赦...)。対象のグラフは教科書通り。 実装的には、minheap クラスは前回のプリム法と全く一緒。MinPriorityQueue は前回と使い方が違うので一部実装し直し。(といっても relax の周り)。実行するとこんな感じになるはずです。 s -> y -> t (8) s -> y -> t -> x (9) s -> y (5) s -> y -> z (7) 教科書のヒープソート (6章) にもあったように、優先度付きキュー
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://www.logopt.com/python_learning/wp-content/uploads/2014/05/mipproblem2.pdf
「ナイト・ツアー」の解をPython 60行でコーディング | スラド
