グラフ理論最短路問題ダイクストラ法蟻本読書会

Contents

1 ダイクストラ法と最短路問題
2 基本問題
3 応用問題

ダイクストラ法と最短路問題

ダイクストラ法（だいくすとらほう、英: Dijkstra’s algorithm）はグラフ理論における辺の重みが非負数の場合の単一始点最短経路問題を解くための最良優先探索によるアルゴリズムである。

グラフ理論における最短経路問題とは、重み付きグラフの与えられた2つのノード間を結ぶ経路の中で、重みが最小の経路を求める最適化問題です。最適化問題を解く方法のひとつにダイクストラ法があります。これは辺の重みが非負数になっている単一始点最短経路問題を解くためのアルゴリズムです。

出発する頂点を頂点 s とします。まず頂点 s に隣接している頂点のなかで、s からの距離が最も短い頂点を求めます。そのあと s からの距離が二番目に短い頂点を探します。これは最初に求めた頂点以外の s に隣接している頂点、または最初に求めた頂点に隣接している頂点のなかで、s からの距離が最も短い頂点となります。さらに最短距離が未確定の頂点のうち、始点からの距離が最短な頂点の最短距離を確定する処理を繰り返します。これで頂点 s からほかのすべての頂点へ向かう経路の最短距離を求めることができます。

基本問題

以下のようなグラフが与えられるとき、頂点 1 から各頂点までの最短経路長を求めてください。

頂点数は N 、辺数は M である
i 番目の辺は頂点 A_i と頂点 B_i を結び、長さは C_i である

入力されるデータ
N M
A_1 B_1 C_1
A_2 B_2 C_2
　…
A_M B_M C_M

（ただし、2 ≦ N ≦ 100,000
1 ≦ M ≦ min(100,000, N(N-1)/2)
1 ≦ C_i ≦ 10,000 ）

これで一応正しい出力は得られます。ただこの方法はダイクストラ法ではありません。

ダイクストラ法は、最初に出発する頂点に隣接している頂点のなかで、最も近い頂点を求めます。出発点との距離が未確定の頂点のなかから最も近い頂点を探す処理を繰り返します。

ところが以下のコードでは最初に求めているのは、「最も近い頂点」ではありません。ここで求めているのは隣接リストの最初にセットされている頂点でしかなく「最も近い頂点」ではありません。これだとある頂点と開始地点との暫定的な距離がわかってもその値は何度書き換わるかわかりません。できれば1回で確定したいものです。「辺の重みに負数がない」という条件下ではもっと効率的な方法があるのです。

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        int N, M;
        {
            int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            N = vs[0];
            M = vs[1];
        }

        List<int>[] list = new List<int>[N];
        List<int>[] weights = new List<int>[N];
        for (int i = 0; i < N; i++)
        {
            list[i] = new List<int> ();
            weights[i] = new List<int>();
        }

        for (int i = 0; i < M; i++)
        {
            int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            int a = vs[0] - 1;
            int b = vs[1] - 1;
            int c = vs[2];
            list[a].Add (b);
            list[b].Add(a);
            weights[a].Add(c);
            weights[b].Add(c);
        }
        Solve(N, list, weights);
    }

    // この方法はダイクストラ法ではありません
    static void Solve(int n, List<int>[] list, List<int>[] weights)
    {
        int[] costs = new int[n];
        for (int i = 0; i < n; i++)
            costs[i] = int.MaxValue;

        Queue<int> q = new Queue<int> ();
        q.Enqueue(0);
        costs[0] = 0;

        while (q.Count > 0)
        {
            int v = q.Dequeue();
            int curCost = costs[v];

            for (int i = 0; i< list[v].Count; i++)
            {
                int next = list[v][i];
                int newCost = curCost + weights[v][i];
                if (costs[next] <= newCost)
                    continue;

                q.Enqueue(next);
                costs[next] = newCost;
            }
        }
        foreach (int cost in costs)
        {
            if(cost < int.MaxValue)
                Console.WriteLine(cost);
            else
                Console.WriteLine(-1); // たどり着けない
        }
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

class Program

{

static void Main()

{

int N, M;

{

int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

N = vs[0];

M = vs[1];

}

List<int>[] list = new List<int>[N];

List<int>[] weights = new List<int>[N];

for (int i = 0; i < N; i++)

{

list[i] = new List<int> ();

weights[i] = new List<int>();

}

for (int i = 0; i < M; i++)

{

int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int a = vs[0] - 1;

int b = vs[1] - 1;

int c = vs[2];

list[a].Add (b);

list[b].Add(a);

weights[a].Add(c);

weights[b].Add(c);

}

Solve(N, list, weights);

}

// この方法はダイクストラ法ではありません

static void Solve(int n, List<int>[] list, List<int>[] weights)

{

int[] costs = new int[n];

for (int i = 0; i < n; i++)

costs[i] = int.MaxValue;

Queue<int> q = new Queue<int> ();

q.Enqueue(0);

costs[0] = 0;

while (q.Count > 0)

{

int v = q.Dequeue();

int curCost = costs[v];

for (int i = 0; i< list[v].Count; i++)

{

int next = list[v][i];

int newCost = curCost + weights[v][i];

if (costs[next] <= newCost)

continue;

q.Enqueue(next);

costs[next] = newCost;

}

foreach (int cost in costs)

{

if(cost < int.MaxValue)

Console.WriteLine(cost);

else

Console.WriteLine(-1); // たどり着けない

}

ダイクストラ法では普通のキューではなく優先度付きキューを使います。キューに新しく訪問する頂点を追加するときに優先度として開始地点からの距離を設定します。するとつぎのTryDequeueメソッドでは開始地点からの距離が最短の頂点を最初に取り出すことができます。この場合は配列 costs[頂点番号] に優先度（距離）をそのまま格納します。

TryDequeueメソッドで同じ頂点番号が取得されてしまった場合はどうなるのでしょうか？つまり costs[頂点番号] にはすでに int.MaxValue 以外の値がセットされている場合です。この場合はキューから無視すべき値（最短距離を求めているのにすでに確定したはずの値よりも大きな値）が取得された場合なので continue します。

上記のコードとの大きな違いとして costs に値をセットする場所とループを continue する場所があげられます。

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    // Mainメソッドは同じなので省略

    static void Solve(int n, List<int>[] list, List<int>[] weights)
    {
        int[] costs = new int[n];
        for (int i = 0; i < n; i++)
            costs[i] = int.MaxValue;

        PriorityQueue<int, int> pq = new PriorityQueue<int, int>();
        pq.Enqueue(0, 0);

        while (pq.Count > 0)
        {
            _ = pq.TryDequeue(out int v, out int curCost);
            if (costs[v] < int.MaxValue) // すでに確定しているのであればこのループはスキップ
                continue;

            costs[v] = curCost; // ここで確定させる

            for (int i = 0; i< list[v].Count; i++)
            {
                int next = list[v][i];
                int newCost = curCost + weights[v][i];
                pq.Enqueue(next, newCost);
            }
        }

        foreach (int cost in costs)
        {
            if(cost < int.MaxValue)
                Console.WriteLine(cost);
            else
                Console.WriteLine(-1); // たどり着けない
        }
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

class Program

{

// Mainメソッドは同じなので省略

static void Solve(int n, List<int>[] list, List<int>[] weights)

{

int[] costs = new int[n];

for (int i = 0; i < n; i++)

costs[i] = int.MaxValue;

PriorityQueue<int, int> pq = new PriorityQueue<int, int>();

pq.Enqueue(0, 0);

while (pq.Count > 0)

{

_ = pq.TryDequeue(out int v, out int curCost);

if (costs[v] < int.MaxValue) // すでに確定しているのであればこのループはスキップ

continue;

costs[v] = curCost; // ここで確定させる

for (int i = 0; i< list[v].Count; i++)

{

int next = list[v][i];

int newCost = curCost + weights[v][i];

pq.Enqueue(next, newCost);

}

foreach (int cost in costs)

{

if(cost < int.MaxValue)

Console.WriteLine(cost);

else

Console.WriteLine(-1); // たどり着けない

}

応用問題

F – 船旅

JOI 国には n 島の島があり，各島には 1 から n までの番号が付けられている．現在 JOI 国では各島の間を結ぶ航路網の整備が進んでいる。

あなたは船舶の切符を扱っているチケットセンターに勤務している。JOI 国には船舶を使って，できる限り安価に島と島の間を旅行したいと考えている人が沢山おり、彼らは出発地と目的地を注文票に記入してあなたのところに送ってくる。

あなたの仕事は、客から注文票を受け取ったらすぐにいくつかの船舶を乗り継いで、出発地と目的地を結ぶ航路の中でもっとも安価な運賃を計算し客に伝えることである。

ただし旅程によっては船舶を使って旅行することが出来ない場合もある。そのときは『船舶を使って旅行することが出来ない』と客に伝える必要がある。また JOI 国では，島と島の間を結ぶ新しい船舶が，次々と運航を開始しており、あなたにはその情報が随時伝えられる。客に返事をする際には最新の情報に留意しなければならない。

入力として客の注文票や新たに運航を開始した船舶の運航情報が与えられたときに，客への返事を求めるプログラムを作成せよ。

入力の 1 行目には 2 つの整数 n, k (1 ≦ n ≦ 100，1 ≦ k ≦ 5000) が書かれている。n は島の数、k はクエリの数である。

クエリの最初の数字が 0 のとき、この行は客の注文票を表す。そのあと空白区切りで 2 個の整数 a, b (1 ≦ a ≦ n，1 ≦b ≦ n) が続くが、この場合は島 a から島 b までの運賃の合計の最小値を返すこと。島 a から島 b までたどり着けない場合は -1 を返すこと。

クエリの最初の数字が 1 のときは新たに運航を開始した船舶の運航情報を表す。そのあと空白区切りで 3 個の整数 c, d, e (1 ≦ c ≦ n，1 ≦ d ≦ n，1 ≦ e ≦ 1000000) が書かれている。これは島 c と島 d を往復する船舶が新たに運航を開始し、その運賃は e であることを表している。

第７回日本情報オリンピック予選の問題です。なので難しい問題ではないか？クエリが飛んでくるたびに辺を追加したり最短経路を計算していては間に合わないのではないかと思って考え込んでしまったのですが、愚直にやればよいという問題でした。予選とはいえ F 問題。これってラスボスじゃないの？

島がつながっているかのクエリがバンバン飛んできたとしてもその計算量は O(m (k + n) log n) なので普通に間に合います。計算量を理解しているかどうかが問題となります。

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        int n, k;
        {
            int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            n = vs[0];
            k = vs[1];
        }

        List<long>[] list = new List<long>[n];
        List<long>[] weights = new List<long>[n];
        for (int i = 0; i < n; i++)
        {
            list[i] = new List<long> ();
            weights[i] = new List<long>();
        }

        List<long> rets = new List<long>();
        for (int i = 0; i < k; i++)
        {
            long[] vs = Console.ReadLine().Split().Select(_ => long.Parse(_)).ToArray();
            long q = vs[0];
            if (q == 0)
            {
                // ふたつの島はつながっているか？
                long a = vs[1] - 1;
                long b = vs[2] - 1;
                long[] costs = Dijkstra(n, a, list, weights);
                if(costs[b] < long.MaxValue)
                    rets.Add(costs[b]);
                else
                    rets.Add(-1);
            }
            if (q == 1)
            {
                // ふたつの島をつなげる
                long c = vs[1] - 1;
                long d = vs[2] - 1;
                long e = vs[3];
                list[d].Add(c);
                list[c].Add(d);
                weights[c].Add(e);
                weights[d].Add(e);
            }
        }
        foreach(long ret in rets)
            Console.WriteLine(ret);
    }

    // 頂点 s から他の頂点への最短経路を配列で返す（連結していないなら long.MaxValue）
    static long[] Dijkstra(long n, long s, List<long>[] list, List<long>[] weights)
    {
        long[] costs = new long[n];
        for (int i = 0; i < n; i++)
            costs[i] = long.MaxValue;

        PriorityQueue<long, long> pq = new PriorityQueue<long, long>();
        pq.Enqueue(s, 0);

        while (pq.Count > 0)
        {
            _ = pq.TryDequeue(out long v, out long curCost);
            if (costs[v] < long.MaxValue)
                continue;

            costs[v] = curCost;

            for (int i = 0; i< list[v].Count; i++)
            {
                long next = list[v][i];
                long newCost = curCost + weights[v][i];
                pq.Enqueue(next, newCost);
            }
        }
        return costs;
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

class Program

{

static void Main()

{

int n, k;

{

int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

n = vs[0];

k = vs[1];

}

List<long>[] list = new List<long>[n];

List<long>[] weights = new List<long>[n];

for (int i = 0; i < n; i++)

{

list[i] = new List<long> ();

weights[i] = new List<long>();

}

List<long> rets = new List<long>();

for (int i = 0; i < k; i++)

{

long[] vs = Console.ReadLine().Split().Select(_ => long.Parse(_)).ToArray();

long q = vs[0];

if (q == 0)

{

// ふたつの島はつながっているか？

long a = vs[1] - 1;

long b = vs[2] - 1;

long[] costs = Dijkstra(n, a, list, weights);

if(costs[b] < long.MaxValue)

rets.Add(costs[b]);

else

rets.Add(-1);

}

if (q == 1)

{

// ふたつの島をつなげる

long c = vs[1] - 1;

long d = vs[2] - 1;

long e = vs[3];

list[d].Add(c);

list[c].Add(d);

weights[c].Add(e);

weights[d].Add(e);

}

foreach(long ret in rets)

Console.WriteLine(ret);

}

// 頂点 s から他の頂点への最短経路を配列で返す（連結していないなら long.MaxValue）

static long[] Dijkstra(long n, long s, List<long>[] list, List<long>[] weights)

{

long[] costs = new long[n];

for (int i = 0; i < n; i++)

costs[i] = long.MaxValue;

PriorityQueue<long, long> pq = new PriorityQueue<long, long>();

pq.Enqueue(s, 0);

while (pq.Count > 0)

{

_ = pq.TryDequeue(out long v, out long curCost);

if (costs[v] < long.MaxValue)

continue;

costs[v] = curCost;

for (int i = 0; i< list[v].Count; i++)

{

long next = list[v][i];

long newCost = curCost + weights[v][i];

pq.Enqueue(next, newCost);

}

return costs;

}

D – Saving Snuuk

すぬけ国には n 個の都市があり、m 本の電車が走っています。都市には 1 から n の番号がつけられていて、 i 番目の電車は都市 u i と v i の間を両方向に走っています。どの都市からどの都市へも電車を乗り継ぐことで到達できます。

すぬけ国で使える通貨には、円とスヌークの 2 種類があります。どの電車の運賃も円とスヌークのどちらの通貨でも支払え、i 番目の電車の運賃は、円で支払う場合 a i 円、スヌークで払う場合 b i スヌークです。

両替所のある都市に行くと、1 円を 1 スヌークに両替することができます。ただし両替をするときには持っている円すべてをスヌークに両替しなければなりません。

現在、両替所は n 個の都市すべてに存在しますが i 番目の都市の両替所は今年から i 年後に閉鎖されてしまい、i 年後とそれ以降は使うことができません。

kenkoooo さんは 10^15 円を持って都市 s から旅に出て、都市 t へ向かおうと思っています。移動中、kenkoooo さんは両替所のある都市のいずれかで円をスヌークに両替しようと考えています。ただし、都市 s または都市 t の両替所で両替をしてもよいものとします。

kenkoooo さんは移動の経路と両替をする都市を適切に選ぶことで、できるだけ多くのスヌークを持っている状態で都市 t に辿り着きたいと考えています。

i = 0, …, n-1 のそれぞれについて、i 年後に都市 s から都市 t へ移動した際に kenkoooo さんが所持しているスヌークの最大額を求めてください。ただし、旅行中に年をまたぐことは無いとします。

入力されるデータ
n m s t
u_1 v_1 a_1 b_1
u_2 v_2 a_2 b_2
　…
u_m v_m a_m b_m

（ただし
2 ≦ n ≦ 10^5, 1 ≦ m ≦ 10^5
1 ≦ s, t ≦ n, 1 ≦ u_i, v_i ≦ n, 1 ≦ a_i, b_i ≦ 10^9
どの都市からどの都市へも電車を乗り継ぐことで到達できる）

「途中まで円で払い、途中でスヌークに換金する」、「両替をするときには持っている円すべてをスヌークに両替する」という制約のもとで、都市 s から都市 t へ移動した際に所持しているスヌークを最大化するには、

都市 s ～両替地点（円）
都市 t ～両替地点（スヌーク）

の合計が最小になる両替地点を探せばよいことになります。

コードの costs1[i] + costs2[i] が都市 i で両替したときの最低コストを表しています。各年で costs1[i] + costs2[i] が最小になる i を考える必要がありますが、最初に両替できる都市が 1 つの年（最後の年）から逆順に最低コストを考えると計算量を減らすことができます（年とか都市とか紛らわしい）。

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        int n, m, s, t;
        {
            int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            n = vs[0];
            m = vs[1];
            s = vs[2] - 1;
            t = vs[3] - 1;
        }

        List<long>[] list = new List<long>[n];
        List<long>[] weights1 = new List<long>[n];
        List<long>[] weights2 = new List<long>[n];
        for (int i = 0; i < n; i++)
        {
            list[i] = new List<long> ();
            weights1[i] = new List<long>();
            weights2[i] = new List<long>();
        }

        for (int i = 0; i < m; i++)
        {
            long[] vs = Console.ReadLine().Split().Select(_ => long.Parse(_)).ToArray();
            long u = vs[0] - 1;
            long v = vs[1] - 1;
            long a = vs[2];
            long b = vs[3];
            list[u].Add(v);
            list[v].Add(u);
            weights1[u].Add(a);
            weights1[v].Add(a);
            weights2[u].Add(b);
            weights2[v].Add(b);
        }

        long[] costs1 = Dijkstra(n, s, list, weights1);
        long[] costs2 = Dijkstra(n, t, list, weights2);

        // costs1[i] + costs2[i] が 都市 i で両替したときの最低コスト
        // 各年で costs1[i] + costs2[i] が最小になる i を考える
        // 逆順に最低コストを考える
        long min = long.MaxValue;
        List<long> costs = new List<long>();
        for (int i = n-1; i >= 0; i--)
        {
            min = Math.Min(min, costs1[i] + costs2[i]);
            costs.Add(min);
        }

        // 最低コストは最後の年から逆順で格納されているので元に戻す
        costs.Reverse();

        // 各年の残金の最大値（10^15 - 最低コスト）を出力する
        foreach (long cost in costs)
            Console.WriteLine(1000000000000000 - cost);
    }

    static long[] Dijkstra(int n, int s, List<long>[] list, List<long>[] weights)
    {
        long[] costs = new long[n];
        for (int i = 0; i < n; i++)
            costs[i] = long.MaxValue;

        PriorityQueue<long, long> pq = new PriorityQueue<long, long>();
        pq.Enqueue(s, 0);

        while (pq.Count > 0)
        {
            _ = pq.TryDequeue(out long v, out long curCost);
            if (costs[v] < long.MaxValue)
                continue;

            costs[v] = curCost;

            for (int i = 0; i< list[v].Count; i++)
            {
                long next = list[v][i];
                long newCost = curCost + weights[v][i];
                pq.Enqueue(next, newCost);
            }
        }
        // 都市の数と都市間の運賃の制約から途中で旅費がなくなることを考える必要はない
        return costs;
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

class Program

{

static void Main()

{

int n, m, s, t;

{

int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

n = vs[0];

m = vs[1];

s = vs[2] - 1;

t = vs[3] - 1;

}

List<long>[] list = new List<long>[n];

List<long>[] weights1 = new List<long>[n];

List<long>[] weights2 = new List<long>[n];

for (int i = 0; i < n; i++)

{

list[i] = new List<long> ();

weights1[i] = new List<long>();

weights2[i] = new List<long>();

}

for (int i = 0; i < m; i++)

{

long[] vs = Console.ReadLine().Split().Select(_ => long.Parse(_)).ToArray();

long u = vs[0] - 1;

long v = vs[1] - 1;

long a = vs[2];

long b = vs[3];

list[u].Add(v);

list[v].Add(u);

weights1[u].Add(a);

weights1[v].Add(a);

weights2[u].Add(b);

weights2[v].Add(b);

}

long[] costs1 = Dijkstra(n, s, list, weights1);

long[] costs2 = Dijkstra(n, t, list, weights2);

// costs1[i] + costs2[i] が都市 i で両替したときの最低コスト

// 各年で costs1[i] + costs2[i] が最小になる i を考える

// 逆順に最低コストを考える

long min = long.MaxValue;

List<long> costs = new List<long>();

for (int i = n-1; i >= 0; i--)

{

min = Math.Min(min, costs1[i] + costs2[i]);

costs.Add(min);

}

// 最低コストは最後の年から逆順で格納されているので元に戻す

costs.Reverse();

// 各年の残金の最大値（10^15 - 最低コスト）を出力する

foreach (long cost in costs)

Console.WriteLine(1000000000000000 - cost);

}

static long[] Dijkstra(int n, int s, List<long>[] list, List<long>[] weights)

{

long[] costs = new long[n];

for (int i = 0; i < n; i++)

costs[i] = long.MaxValue;

PriorityQueue<long, long> pq = new PriorityQueue<long, long>();

pq.Enqueue(s, 0);

while (pq.Count > 0)

{

_ = pq.TryDequeue(out long v, out long curCost);

if (costs[v] < long.MaxValue)

continue;

costs[v] = curCost;

for (int i = 0; i< list[v].Count; i++)

{

long next = list[v][i];

long newCost = curCost + weights[v][i];

pq.Enqueue(next, newCost);

}

// 都市の数と都市間の運賃の制約から途中で旅費がなくなることを考える必要はない

return costs;

}

グラフ理論最短路問題ダイクストラ法蟻本読書会

ダイクストラ法と最短路問題

基本問題

応用問題

鳩でも分かるC#管理人からのお願い

コメントについて

管理人のモチベーションアップのために

コメントをどうぞ