Go to Qiita Advent Calendar 2024 Top
LoginSignup
3
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

@airRnot1106

ダイクストラ法の理解に苦戦したので個人的メモ

Posted at

0.前書き

ダイクストラ法について、仕組みは理解できるけど、いざそれをコードで実装しようとすると手が止まってしまう……
コードで理解するのが大変だったのでメモを残します。なお、今回のダイクストラ法は最速距離を求めるだけで経路は求めないものとします。

1.環境

$ gcc -dumpversion
13.0.0

2.実装

以下のグラフを例として実装していきます。

graph.png

まず、行き先とコストを表す edge という構造体を用意します。

#include <bits/stdc++.h>
using namespace std;

struct edge
{
    int to; // 行き先
    int cost; //　コスト
};

そしてこの edge を持つ二次元 vector でグラフを表すこととします。

#include <bits/stdc++.h>
using namespace std;

struct edge
{
    int to; // 行き先
    int cost; //　コスト
};

int main()
{
    vector<vector<edge>> graph = {{{1, 3}, {2, 7}, {3, 2}}, {{0, 3}, {2, 1}}, {{0, 7}, {1, 1}, {4, 1}}, {{0, 2}, {4, 4}}, {{2, 1}, {3, 4}}};
}

graph.png

graph の index は実際のグラフの節点の index と一致しています。例えば 0 番目の節点は 1 番目にコスト 3 で、2 番目にコスト 7 で、3 番目にコスト 2 で行くことができます。

vector<vector<edge>> graph = {{{1, 3}, {2, 7}, {3, 2}}, {{0, 3}, {2, 1}}, {{0, 7}, {1, 1}, {4, 1}}, {{0, 2}, {4, 4}}, {{2, 1}, {3, 4}}};

それを{{1, 3}, {2, 7}, {3, 2}}という部分が表しています。これをすべての節点において行なっています。なお、今回はすべての辺において双方向に移動できることとします。


では、最初にスタート地点とゴール地点を決めましょう。今回は標準入力から受け取ることとします。

#include <bits/stdc++.h>
using namespace std;

struct edge
{
    int to;
    int cost;
};

int main()
{
    int s, g; // s:　スタート地点 g:　ゴール地点
    cin >> s >> g;
    vector<vector<edge>> graph = {{{1, 3}, {2, 7}, {3, 2}}, {{0, 3}, {2, 1}}, {{0, 7}, {1, 1}, {4, 1}}, {{0, 2}, {4, 4}}, {{2, 1}, {3, 4}}};
}

次に、スタート地点からそれぞれの節点までの最速距離を表す配列 dist を用意します。初期値はめちゃくちゃ大きい値にしておきます。

#include <bits/stdc++.h>
using namespace std;

struct edge
{
    int to;
    int cost;
};

int main()
{
    int s, g; // s:　スタート地点 g:　ゴール地点
    cin >> s >> g;
    vector<vector<edge>> graph = {{{1, 3}, {2, 7}, {3, 2}}, {{0, 3}, {2, 1}}, {{0, 7}, {1, 1}, {4, 1}}, {{0, 2}, {4, 4}}, {{2, 1}, {3, 4}}};
    int dist[graph.size()]; // vectorでもOK
    fill(dist, dist + graph.size(), INT_MAX); // めちゃくちゃ大きい値で埋める処理
}

もちろん、スタート地点からスタート地点までの最速距離は 0 なので、s 番目に 0 を代入します。

#include <bits/stdc++.h>
using namespace std;

struct edge
{
    int to;
    int cost;
};

int main()
{
    int s, g; // s:　スタート地点 g:　ゴール地点
    cin >> s >> g;
    vector<vector<edge>> graph = {{{1, 3}, {2, 7}, {3, 2}}, {{0, 3}, {2, 1}}, {{0, 7}, {1, 1}, {4, 1}}, {{0, 2}, {4, 4}}, {{2, 1}, {3, 4}}};
    int dist[graph.size()]; // vectorでもOK
    fill(dist, dist + graph.size(), INT_MAX); // めちゃくちゃ大きい値で埋める処理
    dist[s] = 0; // スタート地点からスタート地点までの最速距離は0で固定
}

次に、探索中の現在地を表す pair の型エイリアスを宣言しておきましょう。pair<int(スタート地点からの距離), int(現在地のindex)>となります。

#include <bits/stdc++.h>
using namespace std;

using cr_pair = pair<int, int>; //現在地を表す。<スタート地点から距離, 現在地のindex>
struct edge
{
    int to;
    int cost;
};

int main()
{
    int s, g; // s:　スタート地点 g:　ゴール地点
    cin >> s >> g;
    vector<vector<edge>> graph = {{{1, 3}, {2, 7}, {3, 2}}, {{0, 3}, {2, 1}}, {{0, 7}, {1, 1}, {4, 1}}, {{0, 2}, {4, 4}}, {{2, 1}, {3, 4}}};
    int dist[graph.size()]; // vectorでもOK
    fill(dist, dist + graph.size(), INT_MAX); // めちゃくちゃ大きい値で埋める処理
    dist[s] = 0; // スタート地点からスタート地点までの最速距離は0で固定
}

そして、その pair を入れる優先度付きキューを用意します。普通のキューは先に入れたものから先に出てきますが、優先度付きキューでは値が小さい、または大きいものから先に出てきます。ダイクストラ法ではコストが小さい順に処理していくので小さい順に出てくるキューを用意します。なお、キューに入っているのが pair の場合 first の値で順番が決定されます。

#include <bits/stdc++.h>
using namespace std;

using cr_pair = pair<int, int>; //現在地を表す。<スタート地点から距離, 現在地のindex>
struct edge
{
    int to;
    int cost;
};

int main()
{
    int s, g; // s:　スタート地点 g:　ゴール地点
    cin >> s >> g;
    vector<vector<edge>> graph = {{{1, 3}, {2, 7}, {3, 2}}, {{0, 3}, {2, 1}}, {{0, 7}, {1, 1}, {4, 1}}, {{0, 2}, {4, 4}}, {{2, 1}, {3, 4}}};
    int dist[graph.size()]; // vectorでもOK
    fill(dist, dist + graph.size(), INT_MAX); // めちゃくちゃ大きい値で埋める処理
    dist[s] = 0; // スタート地点からスタート地点までの最速距離は0で固定
    priority_queue<cr_pair, vector<cr_pair>, greater<cr_pair>> que; // この書き方をすると昇順のキューになる
}

最初の現在地はスタート地点なので、que にはスタート地点の情報を push しておきます。

#include <bits/stdc++.h>
using namespace std;

using cr_pair = pair<int, int>; //現在地を表す。<スタート地点から距離, 現在地のindex>
struct edge
{
    int to;
    int cost;
};

int main()
{
    int s, g; // s:　スタート地点 g:　ゴール地点
    cin >> s >> g;
    vector<vector<edge>> graph = {{{1, 3}, {2, 7}, {3, 2}}, {{0, 3}, {2, 1}}, {{0, 7}, {1, 1}, {4, 1}}, {{0, 2}, {4, 4}}, {{2, 1}, {3, 4}}};
    int dist[graph.size()]; // vectorでもOK
    fill(dist, dist + graph.size(), INT_MAX); // めちゃくちゃ大きい値で埋める処理
    dist[s] = 0; // スタート地点からスタート地点までの最速距離は0で固定
    priority_queue<cr_pair, vector<cr_pair>, greater<cr_pair>> que; // この書き方をすると昇順のキューになる
    que.push({0, s}); // 最初の現在地はスタート地点。{0: スタート地点から現在地までの距離, s: 現在地のindex}
}

ここからの作業は、

  1. キューから現在地を取り出す(優先度付きキューなのでスタート地点からの距離が小さい順に出てくる)。
  2. スタート地点から現在地までの距離が現時点での最速距離より小さいか判定する。小さければ continue。
  3. 現在地から行ける節点をひとつ取得し、スタート地点から現在地までの総コスト + その節点に行くのにかかるコストが現時点でのスタート地点からその節点までの最速距離より小さければ、そのコストを新たなその節点までの最速距離として更新する。そして、キューに{新たなその節点までの最速距離, その節点のindex}を push する。
  4. 3 を現在地から行ける節点すべてにおいて行う。
  5. 上記をキューがからになるまで行う。

となります。
これをコードで実装していきます。

キューから現在地を取り出す

/* ---省略--- */
cr_pair c = que.top();
int d = c.first; // スタート地点から現在地までの距離
int idx = c.second; // 現在地のindex
que.pop();

スタート地点から現在地までの距離が現時点での最速距離より小さいか判定する。

/* ---省略--- */
cr_pair c = que.top();
int d = c.first; // スタート地点から現在地までの距離
int idx = c.second; // 現在地のindex
que.pop();
if (d > dist[idx]) // dist[idx]: 現時点でのidxまでの最速距離
    continue; // 最速距離を更新できないなら意味がないので打ち切り

現在地から行ける節点をひとつ取得し、スタート地点から現在地までの総コスト + その節点に行くのにかかるコストが現時点でのスタート地点からその節点までの最速距離より小さければ、そのコストを新たなその節点までの最速距離として更新する。そして、キューに{新たなその節点までの最速距離, その節点のindex}を push する。

/* ---省略--- */
cr_pair c = que.top();
int d = c.first; // スタート地点から現在地までの距離
int idx = c.second; // 現在地のindex
que.pop();
if (d > dist[idx]) // dist[idx]: 現時点でのidxまでの最速距離
    continue; // 最速距離を更新できないなら意味がないので打ち切り
int to = graph[idx][0].to; //　とりあえず仮に0番目とする
int cost = graph[idx][0].cost;
if (d + cost < dist[to]) // スタート地点から現在地までの総コスト + その節点に行くのにかかるコスト < 現時点でのスタート地点からその節点までの最速距離
{
    dist[to] = d + cost; // 新たな最速距離で更新
    que.push({dist[to], to}); //　　次の探索地点をキューに追加
}

3 を現在地から行ける節点すべてにおいて行う。

/* ---省略--- */
cr_pair c = que.top();
int d = c.first; // スタート地点から現在地までの距離
int idx = c.second; // 現在地のindex
que.pop();
if (d > dist[idx]) // dist[idx]: 現時点でのidxまでの最速距離
    continue; // 最速距離を更新できないなら意味がないので打ち切り
for (int i = 0; i < graph[idx].size(); i++)
{
    int to = graph[idx][i].to; // graphの現在地から行けるi番目の節点のindex
    int cost = graph[idx][i].cost; // graphの現在地から行けるi番目の節点のcost
    if (d + cost < dist[to]) // スタート地点から現在地までの総コスト + i番目の節点に行くのにかかるコスト < 現時点でのスタート地点からi番目の節点までの最速距離
    {
        dist[to] = d + cost; // 新たな最速距離で更新
        que.push({dist[to], to}); //　　次の探索地点をキューに追加
    }
}

上記をキューがからになるまで行う。

/* ---省略--- */
while(!que.empty())
{
    cr_pair c = que.top();
    int d = c.first; // スタート地点から現在地までの距離
    int idx = c.second; // 現在地のindex
    que.pop();
    if (d > dist[idx]) // dist[idx]: 現時点でのidxまでの最速距離
        continue; // 最速距離を更新できないなら意味がないので打ち切り
    for (int i = 0; i < graph[idx].size(); i++)
    {
        int to = graph[idx][i].to; // graphの現在地から行けるi番目の節点のindex
        int cost = graph[idx][i].cost; // graphの現在地から行けるi番目の節点のcost
        if (d + cost < dist[to]) // スタート地点から現在地までの総コスト + i番目の節点に行くのにかかるコスト < 現時点でのスタート地点からi番目の節点までの最速距離
        {
            dist[to] = d + cost; // 新たな最速距離で更新
            que.push({dist[to], to}); //　　次の探索地点をキューに追加
        }
    }
}

よって、全体のコードは以下のようになります。

#include <bits/stdc++.h>
using namespace std;

using cr_pair = pair<int, int>; //現在地を表す。<スタート地点から距離, 現在地のindex>
struct edge
{
    int to;
    int cost;
};

int main()
{
    int s, g; // s:　スタート地点 g:　ゴール地点
    cin >> s >> g;
    vector<vector<edge>> graph = {{{1, 3}, {2, 7}, {3, 2}}, {{0, 3}, {2, 1}}, {{0, 7}, {1, 1}, {4, 1}}, {{0, 2}, {4, 4}}, {{2, 1}, {3, 4}}};
    int dist[graph.size()]; // vectorでもOK
    fill(dist, dist + graph.size(), INT_MAX); // めちゃくちゃ大きい値で埋める処理
    dist[s] = 0; // スタート地点からスタート地点までの最速距離は0で固定
    priority_queue<cr_pair, vector<cr_pair>, greater<cr_pair>> que; // この書き方をすると昇順のキューになる
    que.push({0, s}); // 最初の現在地はスタート地点。{0: スタート地点から現在地までの距離, s: 現在地のindex}
    while(!que.empty())
    {
        cr_pair c = que.top();
        int d = c.first; // スタート地点から現在地までの距離
        int idx = c.second; // 現在地のindex
        que.pop();
        if (d > dist[idx]) // dist[idx]: 現時点でのidxまでの最速距離
            continue; // 最速距離を更新できないなら意味がないので打ち切り
        for (int i = 0; i < graph[idx].size(); i++)
        {
            int to = graph[idx][i].to; // graphの現在地から行けるi番目の節点のindex
            int cost = graph[idx][i].cost; // graphの現在地から行けるi番目の節点のcost
            if (d + cost < dist[to]) // スタート地点から現在地までの総コスト + i番目の節点に行くのにかかるコスト < 現時点でのスタート地点からi番目の節点までの最速距離
            {
                dist[to] = d + cost; // 新たな最速距離で更新
                que.push({dist[to], to}); //　　次の探索地点をキューに追加
            }
        }
    }

    cout << dist[g] << endl; // ある地点への最速距離はdistを見ればわかる
}

では、実際の流れを例のグラフで追っていきます。

que: {{0, 0}}

graph (1).png

que: {{3, 1}, {7, 2}, {2, 3}}

graph (2).png

次にキューから取り出されるのは{2, 3}です。

que: {{3, 1}, {7, 2}, {6, 4}}

graph (3).png

節点 3 からは節点 0 にも行くことができますが、節点 0 までの最速距離 0 を更新することができないので打ち切りです。
次にキューから取り出されるのは{3, 1}です。

que: {{7, 2}, {6, 4}, {4, 2}}

graph (4).png

前段階で節点 2 には最速 7 コストで行けることがわかっていましたが、今回は 4 コストでたどり着くことができましたので最速距離を更新します。
次にキューから取り出されるのは{4, 2}です。

que: {{7, 2}, {6, 4}, {5, 4}}

graph (5).png

前段階で節点 4 には最速 6 コストで行けることがわかっていましたが、今回は 5 コストでたどり着くことができましたので最速距離を更新します。
次にキューから取り出されるのは{5, 4}です。
しかし、どの節点の最速距離も更新できないので打ち切りです。
次にキューから取り出されるのは{6, 4}です。
しかし、どの節点の最速距離も更新できないので打ち切りです。
次にキューから取り出されるのは{7, 2}です。
もちろん、どの節点の最速距離も更新できないので打ち切りです。
ここでキューが空になったので終了です。
最終的な結果は以下のようになりました。

graph (5).png

3. 後書き

長くなりましたが以上です。今回やったもの以外にもダイクストラ法には経路復元ができるものや A*アルゴリズムといった改善されたものなど色々種類があるので、それらも気が向いたら習得してみたいと思います。

3
2
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
3
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?