[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で書き直したまではいいんですが、アルゴリズムの理解はまだできていません。似たような問題を解いて理解していきたいです。