読者です 読者をやめる 読者になる 読者になる

ダイクストラ法の練習

java

久しぶりにダイクストラ法を、更に久しぶりにJavaで書いてみたら、引っかかりまくりで呆然としました。やはり週一で1アルゴリズムくらいのペースで書いておかないと、腕がなまってしまうなぁ、と痛感。

class Node {
  private char label;
  private int totalCost;
  private Node from;

  public Node(char label, Node from) {
    this.label = label;
    this.from = from;
  }
  public Node(char label) { this(label, null); }

  public char getLabel() { return label; }
  public Node getFrom() { return from; }
  public int getTotalCost() { return totalCost; }
  public void setFrom(Node from) { this.from = from; }
  public void setTotalCost(int totalCost) { this.totalCost = totalCost; }
}

class Route {
  private Node srcNode, dstNode;
  private int cost;

  public Route(Node srcNode, Node dstNode, int cost) {
    this.srcNode = srcNode;
    this.dstNode = dstNode;
    this.cost = cost;
  }

  public Node getSrcNode() { return srcNode; }
  public Node getDstNode() { return dstNode; }
  public int getCost() { return cost; }
}

public class Dijkstra {
  public static void main(String argv[]) {
    Node dummy = new Node('X');
    Node s = new Node('S', dummy);
    Node a = new Node('A');
    Node b = new Node('B');
    Node c = new Node('C');
    Node d = new Node('D');
    Node g = new Node('G');

    Route[] routes = {
      new Route(s, a, 5),
      new Route(s, b, 4),
      new Route(s, c, 2),
      new Route(a, b, 2),
      new Route(a, g, 6),
      new Route(b, c, 3),
      new Route(b, d, 2),
      new Route(d, g, 4),
    };

    while (true) {
      boolean cont = false;
      for (Route route : routes) {
        Node src = route.getSrcNode();
        Node dst = route.getDstNode();
        if (src.getFrom() == null) continue;

        if (dst.getFrom() == null ||
            src.getTotalCost() + route.getCost() < dst.getTotalCost()) {
          dst.setFrom(src);
          dst.setTotalCost(src.getTotalCost() + route.getCost());
          cont = true;
        }
      }
      if (!cont) break;
    }

    System.out.println("distance: " + g.getTotalCost());
    Node node = g;
    while (node != dummy) {
      System.out.println(node.getLabel());
      node = node.getFrom();
    }
  }
}

グラフは http://www.deqnotes.net/acmicpc/dijkstra/ のを使わせてもらっています。

komamitsu@onion:~/bitbucket/misc$ java Dijkstra 
distance: 10
G
D
B
S