ダイクストラ法について - bpeldi2oerkd8の開発日誌

今回はAtCoderの記事です。

ちなみに、昨日AGCがあったのですが、ちょっとだけ問題を覗いて解けそうになかったので早めに退散しました。

次回からはratedの対象が2000～になるみたいですね。

あれだけ難しい問題がそろっているので、対象を絞るのも仕方のないことなのかなと思います。
（昨日は1問も解けなくてもレートが上がった方がそこそこいたようですし）

次回のNOMURA プログラミングコンテスト 2020 (ARCクラス) には参加する予定です。

さて、今回はダイクストラ法について勉強しました。

ダイクストラ法とは

最短経路を求めるアルゴリズムです。

BFSとの違いは、BFSはグラフの辺の重みが等しい時にしか使えませんが、ダイクストラ法は辺の重みが正であればそれぞれ重みが違っても使うことができます。

BFSは計算量がO(V+E)で解けますが、ダイクストラ法はO(ElogV)です。

基本的にBFSで解ける場合はBFSで解くという感じですね。

このアルゴリズムの考え方は以下のサイトがわかりやすかったです。
https://nw.tsuda.ac.jp/lec/dijkstra/

どのように解くのか（Javaの場合）

ライブラリを作ってGithubに上げました。
github.com

このライブラリの使い方について簡単に説明します。

まずグラフを作ってそれを引数としてDijkstraクラスのインスタンスを作ります。
次に、問題文で求められているものに必要なメソッドを呼び出します。

例えば、下のような感じです。

//無向グラフの作成
UDGraph g = new UDGraph(n);

//インスタンスを生成
Dijkstra dk = new Dijkstra(g);

//メソッドを呼び出す（この場合、最短経路を返す）
Deque<Integer> path = dk.getMinPath(a, b);

作ったライブラリを使って、1つ問題を解いてみました。

解いた問題は、JOI 2008 予選 6 - 船旅です。
atcoder.jp

自作のライブラリの部分はスペースの都合上、省きました。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	//java11

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		int k = sc.nextInt();

		UDGraph g = new UDGraph(n);
		Dijkstra dk = new Dijkstra(g);

		while(sc.hasNext()) {
			int num = sc.nextInt();

			if(num == 0) {
				int a = sc.nextInt();
				int b = sc.nextInt();

				long cost = dk.getMinWeight(a, b);

				if(cost == Long.MAX_VALUE)
					System.out.println(-1);
				else
					System.out.println(cost);

			}else if(num == 1) {
				int c = sc.nextInt();
				int d = sc.nextInt();
				long e = sc.nextLong();

				g.addEdge(c, d, e);
			}
		}
	}

        //ここから下は自作のライブラリ

}