ダイクストラ法

dijkstra.png
概要
dijkstra法は幅優先探索である。
dijkstraは貪欲法でもある。
キューは使わず、優先度付きキューを使う
もっとも低いコストを持つノードが優先度付きキューの一番上になるような探索関数を定義する。
↑ような性質を持つデータ構造として向いているのがヒープなのである。部分的にだけソートしてくれるのがいいらしい?
普通の方法 O(V2)
優先度つきキュー O(ElogV)

ネットワークの最短距離を求めるアルゴリズム。
ダイクストラ法は、ネットワークの各頂点までの最短距離を求めるアルゴリズムです。
始点に近い頂点から最短距離を確定していきます。
もちろん、ネットワークの最短距離を求める以外にも使ってもいい。

探索ルールまとめ

  • 1度調べた頂点は2度と調べない….後戻りはしないので、過去を記録する必要はないってことだね。
  • 次は最も良いノードに移動する…何が最も良いのかは、与えられた問題次第。

たとえば。。


Aが始点とする。始点なので、最初に0とメモを記しておく。(この数字は、このノードに来るまでにかかったコストって意味)

  1. 始点から直接到達できる接点までの距離を調べます
  2. このうち、最小の値で到達できる節点を選択します

Bまで到達するには3
Dまで到達するには6
Cまで到達するには7
かかる。だったらBが一番少ないので、次はBに移ることにする。
そして、Bの場所に3とメモる。

  1. 選択した節点を経由した最小距離に書き換えます
  2. 選択済みの節点から直接到達できる節点のうち、最小の値で到達できる節点を選択します。

ってやつをやったってわけだ。
次は、Dしか進めないのでDに進む。
ここでメモる値は2じゃなくて5.
今までかかったコストの合計を記録して、最終的にゴールに着いた時に、どのくらいのコストかわかりたいからだ。

3と4を繰り返し、すべての節点までの最短距離を確定します


最終的に最短距離は8だとわかったわけだ。
ダイクストラのアルゴリズムは、

  • すべての辺のコストが非負である場合

に必ず最適解を返すことがわかっている。
上の例も、すべての辺の値は非負だった。
ダイクストラのアルゴリズムは欲張り法で最適解が得られる代表的な例である。

辺に負の値がある場合は欲張り法が効かない…!?

逆に、負のコストの辺がある場合には最適解を得られない場合がある。
たとえば、下の図。


この例の場合、ダイクストラのアルゴリズムでは、
a,b,cの順に距離を確定していくので、
bまでの最短経路は、
S→b
で距離は4と計算される。
しかし、実際には
s→a→c→b
の経路が距離3で最短になる。

TopCoderで出された問題でdijkstra法を使用して解くもの

KiloManX(SRM 181)Div 1 1000
SRM 150 - Div 1 1000 - RoboCourier
SRM 194 - Div 1 1000 - IslandFerries
SRM 198 - Div 1 500 - DungeonEscape
TCCC '04 Round 4 - 500 - Bombman
実装の仕方
ヒープを使う
ヒープを使いたいのは、優先度付きキューを実装したいからである。
C++にはSTLで優先度付きキューの型がある!PRIORITY_QUEUE<>である 
#include <queue>
using namespace std;
void main(){
priority_queue<int> pq;
}
注意すべきなのは、C++のpriority_queue<>は 最も高い 要素を最初に返す、ということである。
そこで、自分にとって都合の良い順番にしたい場合、次のような構造体を定義する

Define your structure:
struct node {
int cost;
int at;};

そして、costでソートしたい。なので<演算子のオーバーロードをする
bool operator<(const node &leftNode, const node &rightNode) {
 if (leftNode.cost != rightNode.cost) return leftNode.cost < rightNode.cost;
 if (leftNode.at != rightNode.at) return leftNode.at < rightNode.at;
 return false;
}

参考にしたサイト

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=graphsDataStrucs3#dijkstra
http://vipprog.net/wiki/algo_and_data_const.html#l7e4f36c


greedy-method weighted-graphs

サポートサイト Wikidot.com greedy-methodweighted-graphs