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

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

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

これはどのようなアルゴリズムなのでしょうか？

青い頂点から赤い頂点まで移動することを考えます。辺でつながっている頂点間のみ双方向に移動可能ですが、移動時には辺に書かれている値と同じだけのコストがかかります。コストを最小にするためにはどうすればよいでしょうか？

まずスタート地点に 0 を書き込みます。

スタート地点から移動可能な頂点に移動元までの移動コスト（ここでは 0）に辺の重みを足した値を書き込みます。これがその頂点までの移動コストの暫定値です。

暫定値のなかで最小の値を確定値とします。これでこの頂点への最小移動コストが確定しました。なぜ確定させてよいかというと、辺の重みが非負であるということは別の頂点から移動してきてこの値がさらに小さな値に更新されることは絶対にありえないからです。

最小コストが確定した頂点から移動可能な頂点に辺の重みを足した値を書き込むのですが、すでに書き込まれている暫定値のほうが小さい場合はなにもしません。この図では暫定値が更新されるのは黄色い頂点だけです。

そして前回と同様に暫定値のなかで最小のものを確定値にします。赤い頂点が新たに最小移動コストが確定した頂点です。

ここから移動可能な頂点に対して暫定コストを計算し、未定の場合、既存の暫定値のほうが大きい場合は値を更新します。

あとはこの繰り返しです。すべての頂点の最小コストが定まったら終了です。

基本問題

以下のようなグラフが与えられるとき、頂点 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 ）

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

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

コメントについて

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

コメントをどうぞ