[Aizu Online Judge] Graph Algorithms 1 (GRL_1) - ヤマカサのプログラミング勉強日記

最短経路問題

GRL_1では最短経路問題を扱います。ダイクストラ法やベルマン–フォード法やワーシャルフロイド法について学びます。

Single Source Shortest Path (GRL_1_A)

単一点間の最短経路を答える問題です。優先度付きキューを用いたダイクストラ法で解きました。

コード

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

public class ProblemA {
    static final int MAX = 100000;
    static final int INF = 1 << 30;
    static final int WHITE = 0;
    static final int GRAY = 1;
    static final int BLACK = 2;
    static int n, r;
    static  Map<Integer, List<int[]>> adj = new HashMap<Integer, List<int[]>>();
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        int q = scan.nextInt();
        r = scan.nextInt();
        for(int i = 0; i < n; i++) {
            List<int[]> list = new ArrayList<int[]>();
            adj.put(i, list);
        }
        for(int i = 0; i < q; i++) {
            int s = scan.nextInt();
            int t = scan.nextInt();
            int d = scan.nextInt();
            List<int[]> list = adj.get(s);
            int[]td = {t, d};
            list.add(td);
            adj.put(s, list);
        }
        scan.close();
        dijkstra();
    }
    static void dijkstra() {
        Queue<int[]> pq = new PriorityQueue<int[]>(new MyComparator ());
        int[]color = new int[MAX];
        int[]d = new int[MAX];
        for(int i = 0; i < n; i++) {
            d[i] = INF;
            color[i] = WHITE;
        }
        d[r] = 0;
        // n0[0]: 重み, n0[1]: ノード
        int[]n0 = {0, r};
        pq.add(n0);
        color[r] = 0;
        while(!pq.isEmpty()) {
            int[]f = pq.poll();
            int u = f[1];
            color[u] = BLACK;
            // 最小値を取り出し、それが最短でなければ無視
            if(d[u] < f[0]) continue;
            for(int j = 0; j < adj.get(u).size(); j++) {
                int[]t = adj.get(u).get(j);
                int v = t[0];
                if(color[v] == BLACK) continue;
                if(d[v] > d[u] + t[1]) {
                    d[v] = d[u] + t[1];
                    int[]p = {d[v], v};
                    pq.add(p);
                    color[v] = GRAY;
                }
            }
        }
        for(int i = 0; i < n; i++) {
            if(d[i] == INF) {
                System.out.println("INF");
            }else {
                System.out.println(d[i]);
            }
        }
    }
    static class MyComparator implements Comparator<int[]> {
        @Override
        public int compare (int[] arg0, int[] arg1) {
            int x = arg0[0];
            int y = arg1[0];
            if (x < y) {
                return -1;
            } else if (x > y) {
                return 1;
            } else{
                return 0;
            }
        }
    }
}

Single Source Shortest Path (Negative Edges) (GRL_1_B)

単一始点最短経路負の重み | グラフ | Aizu Online Judge

負の重みがある最短経路問題です。ダイクストラ法では扱うことができないので、ベルマン–フォード法を用います。

負閉路の検出について、下のサイトが参考になります。

sesenosannko.hatenablog.com

コード

import java.util.Scanner;

public class ProblemB {
    static final int MAX = 1000;
    static final int INF = 1 << 21;
    static final int WHITE = 0;
    static final int GRAY = 1;
    static final int BLACK = 2;
    static int n, r, q;
    static Edge[]e;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        q = scan.nextInt();
        e = new Edge[q];
        r = scan.nextInt(); // 始点
        for(int i = 0; i < q; i++) {
            int s = scan.nextInt();
            int t = scan.nextInt();
            int d = scan.nextInt();
            e[i] = new Edge(s, t, d);
        }
        scan.close();
        //bellmanFord();
        if(bellmanFord()) {
            System.out.println("NEGATIVE CYCLE");
        }else {
            for(int i = 0; i < n; i++) {
                if(d[i] == INF) {
                    System.out.println("INF");
                }else {
                    System.out.println(d[i]);
                }
            }
        }


    }
    static int[]d = new int[MAX];
    static boolean bellmanFord() {
        for(int i = 0; i < n; i++) {
            d[i] = INF;
        }
        d[r] = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < q; j++) {
                if(d[e[j].from] != INF && d[e[j].to] > d[e[j].from] + e[j].cost) {
                    d[e[j].to] = d[e[j].from] + e[j].cost;
                    if(i == n - 1) return true;
                }
            }
        }
        return false;
    }
    static class Edge{
        int from, to, cost;
        public Edge(int from, int to, int cost) {
            this.from = from;
            this.to= to;
            this.cost = cost;
        }
    }
}

All Pairs Shortest Path (GRL_1_C)

全点対間最短経路 | グラフ | Aizu Online Judge

全点対間最短経路の問題です。

螺旋本の15.1 で紹介されています。

負の重みがあるので、ワーシャルフロイド法を使います。

コード

import java.util.Scanner;

public class ProblemC {
    static final int MAX = 100;
    static final long INF = (1L << 32);
    static int n;
    static long[][]d = new long[MAX][MAX];
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        int q = scan.nextInt();
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(i != j) d[i][j] = INF;
            }
        }
        for(int i = 0; i < q; i++) {
            int u = scan.nextInt();
            int v = scan.nextInt();
            int c = scan.nextInt();
            d[u][v] = c;
        }
        scan.close();
        warshallFloyd();
        boolean negative = false;
        for(int i = 0; i < n; i++){
            if(d[i][i] < 0) negative = true;
        }
        if(negative) {
            System.out.println("NEGATIVE CYCLE");
        }else {
            for(int i = 0; i < n; i++) {
                for(int j = 0; j < n; j++) {
                    if(j == n - 1) {
                        if(d[i][j] == INF) System.out.println("INF");
                        else System.out.println(d[i][j]);
                    }
                    else {
                        if(d[i][j] == INF) System.out.print("INF ");
                        else System.out.print(d[i][j] + " ");
                    }
                }
            }
        }
    }
    static void warshallFloyd() {
        for(int k = 0; k < n; k++) {
            for(int i = 0; i < n; i++) {
                if(d[i][k] == INF) continue;
                for(int j = 0; j < n; j++) {
                    if(d[k][j] == INF) continue;
                    d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]);
                }
            }
        }
    }
}

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

作者: 渡部有隆
出版社/メーカー: マイナビ出版
発売日: 2015/01/30
メディア: Kindle版
この商品を含むブログを見る

感想

あまり理解できていませんが、ライブラリとしても使うので、使いこなせるようにしたいです。