Javaでの実装

ウィキペディア小見出し辞書

Javaでの実装

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2018/04/10 17:32 UTC 版)

「エドモンズ・カープのアルゴリズム」の記事における「Javaでの実装」の解説

public class FlowGraph { public static final int WHITE = 0, GRAY = 1, BLACK = 2; private double[][] flow, capacity, resCapacity; private int[] parent, color, queue; private double[] minCapacity; private int size, source, sink, first, last; private double maxFlow; public FlowGraph(String fileName) { // 入力テキストファイルから // "size" 値 // "capacity[size][size]" 配列 // "source" および "sink" ノードのインデックス値（0始点） // を読み込む。 edmondsKarp(); // 出力ファイルに結果を書く（"flow" 配列と "maxFlow" 値） } private void edmondsKarp() { // 計算量 O(V³E) のエドモンズ・カープのアルゴリズム flow = new double[size][size]; resCapacity = new double[size][size]; parent = new int[size]; minCapacity = new double[size]; color = new int[size]; queue = new int[size]; for (int i = 0; i < size; i++) for (int j = 0; j < size; j++) resCapacity[i][j] = capacity[i][j]; while (BFS(source)) { maxFlow += minCapacity[sink]; int v = sink, u; while (v != source) { u = parent[v]; flow[u][v] += minCapacity[sink]; flow[v][u] -= minCapacity[sink]; resCapacity[u][v] -= minCapacity[sink]; resCapacity[v][u] += minCapacity[sink]; v = u; } } } private boolean BFS(int source) { // O(V²) の幅優先探索 for (int i = 0; i < size; i++) { color[i] = WHITE; minCapacity[i] = Double.MAX_VALUE; } first = last = 0; queue[last++] = source; color[source] = GRAY; while (first != last) { // "queue" が空でないうちはループする int v = queue[first++]; for (int u = 0; u < size; u++) if (color[u] == WHITE && resCapacity[v][u] > 0) { minCapacity[u] = Math.min(minCapacity[v], resCapacity[v][u]); parent[u] = v; color[u] = GRAY; if (u == sink) return true; queue[last++] = u; } } return false; }}