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

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

[Aize Online Judge] ALDS1_12

重み付きグラフ

螺旋本の13章 重み付きグラフを読んでいきます。

この章では、グラフの変に重みがついたものを扱います。最小全域木や最短経路を学びます。

ALDS1_12_A: Minimum Spanning Tree

Minimum Spanning Tree | Aizu Online Judge

与えられたグラフの最小全域木の辺の重みの総和を計算する問題です。

最小全域木を求めるためにプリムのアルゴリズムを使います。

プリム法(最小全域木問題)

コード

import java.util.Scanner;

public class ProblemA {
    static final int MAX = 100;
    static final int INF = 1 << 21;
    static final int WHITE = 0;
    static final int GRAY = 1;
    static final int BLACK = 2;
    static int n;
    static int[][]M = new int[MAX][MAX];
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                int e = scan.nextInt();
                if(e == -1) M[i][j] = INF;
                else M[i][j] = e;
            }
        }
        scan.close();
        System.out.println(prim());
    }
    static int prim() {
        int u, minV;
        int[]d = new int[MAX];
        int[]p = new int[MAX];
        int[]color = new int[MAX];
        for(int i = 0; i < n; i++) {
            d[i] = INF;
            p[i] = -1;
            color[i] = WHITE;
        }
        d[0] = 0;
        while(true) {
            minV = INF;
            u = -1;
            for(int i = 0; i < n; i++) {
                if(minV > d[i] && color[i] != BLACK) {
                    u = i;
                    minV = d[i];
                }
            }
            if(u == -1) {
                break;
            }
            color[u] = BLACK;
            for(int v = 0; v < n; v++) {
                if(color[v] != BLACK && M[u][v] != INF) {
                    if(d[v] > M[u][v]) {
                        d[v] = M[u][v];
                        p[v] = u;
                        color[v] = GRAY;
                    }
                }
            }
        }
        int sum = 0;
        for(int i = 0; i < n; i++) {
            if(p[i] != -1) {
                sum += M[i][p[i]];
            }
        }
        return sum;
    }
}

ALDS1_12_B: Single Source Shortest Path I

Single Source Shortest Path I | Aizu Online Judge

ダイクストラ法に関する問題です。一度学んだことがある内容でしたが、実装はしたことはありませんでした。

ダイクストラ法(最短経路問題)

コード

import java.util.Scanner;

public class ProblemB {
    static final int MAX = 100;
    static final int INF = 1 << 21;
    static final int WHITE = 0;
    static final int GRAY = 1;
    static final int BLACK = 2;
    static int n;
    static int[][]M = new int[MAX][MAX];
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                M[i][j] = INF;
            }
        }
        for(int i = 0; i < n; i++) {
            int u = scan.nextInt();
            int k = scan.nextInt();
            for(int j = 0; j < k; j++) {
                int v = scan.nextInt();
                int c = scan.nextInt();
                M[u][v] = c;
            }
        }
        scan.close();
        dijkstra();
    }
    static void dijkstra() {
        int minV;
        int[]d = new int [MAX];
        int[]color = new int [MAX];
        for(int i = 0; i < n; i++) {
            d[i] = INF;
            color[i] = WHITE;
        }
        d[0] = 0;
        color[0] = GRAY;
        while(true) {
            minV = INF;
            int u = -1;
            for(int i = 0; i < n; i++) {
                if(minV > d[i] && color[i] != BLACK) {
                    u = i;
                    minV = d[i];
                }
            }
            if(u == -1) break;
            color[u] = BLACK;
            for(int v = 0; v < n; v++) {
                if(d[v] > d[u] + M[u][v]) {
                    d[v] = d[u] + M[u][v];
                    color[v] = GRAY;
                }
            }
        }
        for(int i = 0; i < n; i++) {
            if(d[i] == INF) {
                System.out.println(i + " " + -1);
            }else {
                System.out.println(i + " " + d[i]);
            }
        }
    }
}

ALDS1_12_C: Single Source Shortest Path Ⅱ

最短経路 | アルゴリズムとデータ構造 | Aizu Online Judge

ノード数が先程の問題より大きい条件の最短経路の問題です。優先度付きキューによるダイクストラ法を実装します。

優先度付きキューにはサイズが2の配列を格納するので、独自定義による優先度を追加する必要があります。

コード

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 ProblemC {
    static final int MAX = 10000;
    static final int INF = 1 << 21;
    static final int WHITE = 0;
    static final int GRAY = 1;
    static final int BLACK = 2;
    static int n;
    // 重み付き隣接リスト
    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();
        for(int i = 0; i < n; i++) {
            int u = scan.nextInt();
            int k = scan.nextInt();
            List<int[]> list = new ArrayList<int[]>();
            for(int j = 0; j < k; j++) {
                int v = scan.nextInt();
                int c = scan.nextInt();
                int []pair = {v, c};
                list.add(pair);
            }
            adj.put(u, 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[0] = 0;
        int[]n0 = {0, 0};
        pq.add(n0);
        color[0] = 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(i + " " + -1);
            }else {
                System.out.println(i + " " + 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;
            }
        }
    }
}

感想

c++のコードをJavaで書き直したまではいいんですが、アルゴリズムの理解はまだできていません。似たような問題を解いて理解していきたいです。