ALG2012-C.ppt

2012717 (sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/lecture/alg/2012/index.html 1

1. 2. 2

.. 3

public class WeightedNode<E> { private E value; // private Map<WeightedNode<E>, Integer> edges; // private boolean visited; private int distance; public WeightedNode(E value, Map<WeightedNode<E>, Integer> edges) { this.value = value; this.edges = edges; reset(); public void reset(){ this.visited = false; this.distance = Integer.MAX_VALUE; this.edges.clear(); public E getvalue() { // return value; public Map<WeightedNode<E>, Integer> getedges(){ return this.edges; // public void connectto(weightednode<e> to, int weight){ this.edges.put(to, weight); // 4

public class Dijkstra { public static <E> void search(collection<weightednode<e>> graph, WeightedNode<E> start){ Set<WeightedNode<E>> visited = new HashSet<WeightedNode<E>>(); Set<WeightedNode<E>> unreached = new HashSet<WeightedNode<E>>(graph); start.setdistance(0); while(!unreached.isempty() ){ int min_distance = Integer.MAX_VALUE; WeightedNode<E> min_node = null; for(weightednode<e> node: unreached){ if(node.getdistance() < min_distance){ min_distance = node.getdistance(); min_node = node; unreached.remove(min_node); visited.add(min_node); for(map.entry<weightednode<e>,integer> edge: min_node.getedges().entryset()){ if(unreached.contains(edge.getkey())){ edge.getkey().setdistance( Math.min(edge.getKey().getDistance(), min_node.getdistance() + edge.getvalue())); 5

private static WeightedNode<Character> nodea = new WeightedNode<Character>('A', new HashMap<WeightedNode<Character>, Integer>()); private static WeightedNode<Character> nodeb = new WeightedNode<Character>('B', new HashMap<WeightedNode<Character>, Integer>()); private static WeightedNode<Character> nodec = new WeightedNode<Character>('C', new HashMap<WeightedNode<Character>, Integer>()); private static WeightedNode<Character> noded = new WeightedNode<Character>('D', new HashMap<WeightedNode<Character>, Integer>()); private static WeightedNode<Character> nodee = new WeightedNode<Character>('E', new HashMap<WeightedNode<Character>, Integer>()); private static WeightedNode<Character> nodef = new WeightedNode<Character>('F', new HashMap<WeightedNode<Character>, Integer>()); private static Collection<WeightedNode<Character>> test_data = new LinkedList<WeightedNode<Character>>(); static { test_data.add(nodea); test_data.add(nodeb); test_data.add(nodec); test_data.add(noded); test_data.add(nodee); test_data.add(nodef); public static void main(string[] args) { System.out.println("4.5.1"); for(weightednode<character> node: test_data){ node.reset(); nodea.connectto(nodeb, 6); nodea.connectto(nodec, 4); nodeb.connectto(noded, 3); nodec.connectto(nodee, 3); nodec.connectto(nodef, 6); nodee.connectto(nodeb, 2); nodee.connectto(noded, 1); search(test_data, nodea); System.out.println("" + nodea.getvalue() + ""); for(weightednode<character> node: test_data){ System.out.println("" + node.getvalue() + ": " + node.getdistance()); 6

ü ü ü ü ü ü 7

public class DijkstraArray { public static <E> void search(weightednode<e>[] nodes, int start, int[][] weights){ nodes[start].setdistance(0); for(int step = 0; step < nodes.length; step++){ int min = Integer.MAX_VALUE; int p = 0; for(int x = 0; x < nodes.length; x++){ if(!nodes[x].isvisited() && (nodes[x].getdistance() < min)){ p = x; min = nodes[x].getdistance(); if(min == Integer.MAX_VALUE){ throw new IllegalArgumentException(""); nodes[p].setvisited(true); for(int x = 0; x < nodes.length; x++){ if(weights[p][x] == Integer.MAX_VALUE){ continue; nodes[x].setdistance( Math.min(nodes[x].getDistance(), nodes[p].getdistance() + weights[p][x])); 8

private static WeightedNode<Character> nodea = new WeightedNode<Character>('A'); private static WeightedNode<Character> nodeb = new WeightedNode<Character>('B'); private static WeightedNode<Character> nodec = new WeightedNode<Character>('C'); private static WeightedNode<Character> noded = new WeightedNode<Character>('D'); private static WeightedNode<Character> nodee = new WeightedNode<Character>('E'); private static WeightedNode<Character> nodef = new WeightedNode<Character>('F'); @SuppressWarnings("unchecked") private static WeightedNode<Character>[] test_data = new WeightedNode[] { nodea, nodeb, nodec, noded, nodee, nodef ; public static void main(string[] args) { System.out.println("4.5.1"); for(weightednode<character> node: test_data){ node.reset(); int[][] weights = new int[test_data.length][test_data.length]; for(int[] from: weights){ for(int i = 0; i < from.length; i++){ from[i] = Integer.MAX_VALUE; weights[0][1] = 6; weights[0][2] = 4; weights[1][3] = 3; weights[2][4] = 3; weights[2][5] = 6; weights[4][1] = 2; weights[4][3] = 1; search(test_data, 0, weights); System.out.println("" + nodea.getvalue() + ""); for(weightednode<character> node: test_data){ System.out.println("" + node.getvalue() + ": " + node.getdistance()); 9

10

public class Floyd { public static <E> void search(int[][] weights, int[][] distances){ for(int i = 0; i < weights.length; i++){ distances[i] = weights[i].clone(); for(int k = 0; k < weights.length; k++){ for(int i = 0; i < weights.length; i++){ if(distances[i][k] == Integer.MAX_VALUE){ continue; // or for(int j = 0; j < weights[i].length; j++){ if(distances[k][j] == Integer.MAX_VALUE){ continue; // or int w = distances[i][k] + distances[k][j]; if(w < distances[i][j]){ distances[i][j] = w; 11

public static void main(string[] args) { System.out.println("4.5.1"); int[][] weights = new int[6][6]; for(int i = 0; i < weights.length; i++){ for(int j = 0; j < weights[i].length; j++){ weights[i][j] = Integer.MAX_VALUE; weights[i][i] = 0; weights[0][1] = 6; weights[0][2] = 4; weights[1][3] = 3; weights[2][4] = 3; weights[2][5] = 6; weights[4][1] = 2; weights[4][3] = 1; int[][] distances = new int[weights.length][]; search(weights, distances); System.out.println(""); for(int i = 0; i < distances.length; i++){ for(int j = 0; j < distances[i].length; j++){ if(distances[i][j] == Integer.MAX_VALUE){ System.out.print("- "); else { System.out.print(distances[i][j] + " "); System.out.println(); 12

a [ i, j] true = false 13

public class Warshall { public static <E> void search(boolean[][] adjacency, boolean[][] reachable){ for(int i = 0; i < adjacency.length; i++){ reachable[i] = adjacency[i].clone(); for(int k = 0; k < adjacency.length; k++){ for(int i = 0; i < adjacency.length; i++){ if(!reachable[i][k] ){ continue; for(int j = 0; j < adjacency[i].length; j++){ reachable[i][j] = reachable[i][j] reachable[k][j]; 14

public static void main(string[] args) { System.out.println("4.5.1"); boolean[][] adjacency = new boolean[6][6]; for(int i = 0; i < adjacency.length; i++){ for(int j = 0; j < adjacency[i].length; j++){ adjacency[i][j] = false; adjacency[i][i] = true; adjacency[0][1] = true; adjacency[0][2] = true; adjacency[1][3] = true; adjacency[2][4] = true; adjacency[2][5] = true; adjacency[4][1] = true; adjacency[4][3] = true; boolean[][] reachable = new boolean[adjacency.length][]; search(adjacency, reachable); System.out.println(""); for(int i = 0; i < reachable.length; i++){ for(int j = 0; j < reachable[i].length; j++){ if(reachable[i][j]){ System.out.print("+ "); else { System.out.print("- "); System.out.println(); 15

: : : : () PHS 16