山傘のプログラミング勉強日記

プログラミングに関する日記とどうでもよい雑記からなるブログです。

[Aizu Online Judge] Graph Algorithms 1 (GRL_1)

最短経路問題

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

Single Source Shortest Path (GRL_1_A)

単一始点最短経路 | グラフ | Aizu Online Judge

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

コード

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]);
                }
            }
        }
    }
}

感想

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