はじめに
今回はダイクストラ法を実装してみようという記事になります！
ダイクストラ法を用いることで迷路の最短距離を求めたりすることができます。
カーナビの経路探索や鉄道の経路案内なんかにも使われている例があるそうです。
では早速みていきましょう。
ダイクストラ法
ダイクストラ法はWidipediaでは以下のように説明されていました。
ダイクストラ法（だいくすとらほう、英: Dijkstra's algorithm）はグラフ理論における辺の重みが非負数の場合の単一始点最短経路問題を解くための最良優先探索によるアルゴリズムである。
図をみてもらった方が早いと思いますが、２つの頂点を結んだ辺には移動のコストが表記されておりスタート位置からそれぞれの頂点までの最短経路を求めることができます。
実装するときは以下の手順をすることで実現できます。
- 初期化：スタート頂点の値（最小コスト候補）を0，他の頂点の値を未定義（または∞）に設定。
- 確定した頂点に変化がなければ終了する
- 確定されていない頂点のうち，最小の値を持つ頂点を見つけ，確定した頂点とする
- 確定した頂点からの伸びている辺をそれぞれチェックし，「確定した頂点までのコスト＋辺のコスト」を計算し，そのノードの現在値よりも小さければ更新する （経路情報も必要であれば，「どこから来たのか」を表す変数が確定ノードを指すようにする）
コード
優先度付きキューは以前実装したものを使用します。
www.hanachiru-blog.com
public class Dikstra { public int N { get; } // 頂点の数 private List<Edge>[] _graph; // グラフの辺のデータ /// <summary> /// 初期化 /// </summary> /// <param name="n">頂点数</param> public Dikstra(int n) { N = n; _graph = new List<Edge>[n]; for (int i = 0; i < n; i++) _graph[i] = new List<Edge>(); } /// <summary> /// 辺を追加 /// </summary> /// <param name="a">接続元の頂点</param> /// <param name="b">接続先の頂点</param> /// <param name="cost">コスト</param> public void Add(int a, int b, long cost = 1) => _graph[a].Add(new Edge(b, cost)); /// <summary> /// 最短経路のコストを取得 /// </summary> /// <param name="start">開始頂点</param> public long[] GetMinCost(int start) { // コストをスタート頂点以外を無限大に var cost = new long[N]; for (int i = 0; i < N; i++) cost[i] = 1000000000000000000; cost[start] = 0; // 未確定の頂点を格納する優先度付きキュー(コストが小さいほど優先度が高い) var q = new PriorityQueue<Vertex>(N * 10, Comparer<Vertex>.Create((a, b) => b.CompareTo(a))); q.Push(new Vertex(start, 0)); while (q.Count > 0) { var v = q.Pop(); // 記録されているコストと異なる(コストがより大きい)場合は無視 if (v.cost != cost[v.index]) continue; // 今回確定した頂点からつながる頂点に対して更新を行う foreach (var e in _graph[v.index]) { if (cost[e.to] > v.cost + e.cost) { // 既に記録されているコストより小さければコストを更新 cost[e.to] = v.cost + e.cost; q.Push(new Vertex(e.to, cost[e.to])); } } } // 確定したコストを返す return cost; } public struct Edge { public int to; // 接続先の頂点 public long cost; // 辺のコスト public Edge(int to, long cost) { this.to = to; this.cost = cost; } } public struct Vertex : IComparable<Vertex> { public int index; // 頂点の番号 public long cost; // 記録したコスト public Vertex(int index, long cost) { this.index = index; this.cost = cost; } public int CompareTo(Vertex other) => cost.CompareTo(other.cost); } }
有向グラフに対応しているので、無向グラフのときは両方の向きの辺を追加してください。
使い方
このグラフについてコードにしてみましょう。
static void Main(string[] args) { // ダイクストラのインスタンスを作成 var graph = new Dikstra(6); // 辺の情報を追加する(無向グラフなので両方の向きに) graph.Add(0, 1, 7); graph.Add(0, 2, 14); graph.Add(0, 3, 9); graph.Add(1, 0, 7); graph.Add(1, 3, 10); graph.Add(1, 4, 15); graph.Add(2, 0, 14); graph.Add(2, 3, 2); graph.Add(2, 5, 9); graph.Add(3, 0, 9); graph.Add(3, 2, 2); graph.Add(3, 4, 11); graph.Add(4, 1, 15); graph.Add(4, 3, 11); graph.Add(4, 5, 6); graph.Add(5, 2, 9); graph.Add(5, 4, 6); // 最短距離を調べる var minDistaces = graph.GetMinCost(0); for (int i = 0; i < minDistaces.Count; i++) Console.WriteLine($"Vertex[{i}] = {minDistaces[i]}"); }
Vertex[0] = 0 Vertex[1] = 7 Vertex[2] = 11 Vertex[3] = 9 Vertex[4] = 20 Vertex[5] = 20
辺の情報を手動で入れるのはかなり辛かったですが、正しくそれぞれの点の最短距離を求められているようです。
さいごに
とりあえずダイクストラ法を実装することができました。
ただコストだけでなく最短距離のルートも知れた方が良い気がするので、また気が向いたらそちらの機能も実装してみようと思います。
ではまた。
