プログラミング雑記

プログラミングが趣味のだらだら学生。自作したプログラムの紹介やいまハマってることなんかを適当に書いていったりいかなったり

ダイクストラ法を実装してみる

ダイクストラ法とは

ダイクストラ法(Dijkstra's Algorithm)は最短経路問題を解くグラフ理論アルゴリズムです。
出発点から目標点までの最短距離とそこまでの経路を求めることができます。 このダイクストラ法はチューリング賞を受賞し、構造化プログラミングを提唱したことでも有名なエドガー・ダイクストラによって考案されました。コンピュータサイエンスについて勉強していれば絶対に抑えておかなければならないアルゴリズムらいっす。

今回やること

Processingでダイクストラ法を見えるようにする。 f:id:kirari0831:20160111144303g:plain

アルゴリズムの説明

Wikipedia先生に丸投げする⇒ダイクストラ法
時間があれば自分の解説を載せたい。

プログラムの実装

アルゴリズムに従ってProcessingで実装していくよ~

import javax.swing.*;

final int nodeCount = 10;    //点の総数
int startNode = 0;  //出発点
int endNode = nodeCount - 1;    //目標点
Node[] nodes = new Node[nodeCount];
void setup() {
    size(800, 600);
    initNodes();
}
//点の初期化
void initNodes(){
    for (int i = 0; i < nodeCount; i++) {
        nodes[i] = new Node(i, (int)random(width), (int)random(height));
        for (int j = 0; j < i; j++) {
            if (i != j) {
                if (random(10) > 7) {   //適当に点と点の間をつなぐ
                    nodes[i].neighbors.add(nodes[j]);
                    nodes[j].neighbors.add(nodes[i]);
                }
            }
        }
    }
}
void draw() {
    background(0);
    new DijkstraAlgorithm().dijkstra(); //最短経路探索を行う
    for (Node node : nodes) {   //全てのノードの描画
        node.drawNode();
        node.drawLine();
    }
    drawPath(startNode, endNode);   //調べた経路を表示
}
void drawPath(int startNode, int v) {
    if (v == startNode) {
    } else if (pi[v] == -1) {
        fill(255);
        textSize(20);
        text("There is no shortest path.",20, 20);
    } else {
        drawPath(startNode, pi[v]); //再帰的にゴールから出発点に向けて順に調べていく
        stroke(0, 255, 0);
        line(nodes[v].x, nodes[v].y, nodes[pi[v]].x, nodes[pi[v]].y);
    }
}

Node moveNode = null;   //マウスで操作するノード
void mousePressed() {
    for (Node node : nodes) {
        if (isOver(node)) {
            moveNode = node;
        }
    }
}
void mouseDragged() {
    if (moveNode != null) { //選択されているノードがあれば動かす
        moveNode.x = mouseX;
        moveNode.y = mouseY;
    }
}
void mouseReleased() {
    moveNode = null;    //選択ノードの解除
}
//ノードの上にカーソルがあるかどうか
boolean isOver(Node node) {
    if (dist(mouseX, mouseY, node.x, node.y) < r) {
        return true;
    }
    return false;
}

int r = 20; //ノードの直径
class Node {
    int id;
    int x, y;
    ArrayList<Node> neighbors;  //隣接しているノード
    Node(int id, int x, int y) {
        this.id = id;
        this.x = x;
        this.y = y;
        neighbors = new ArrayList<Node>();
    }
    //ノードの描画
    void drawNode() {
        noStroke();
        fill(0, 0, 255, 200);
        ellipse(x, y, r, r);
        fill(255);
        textSize(12);
        text(id, x, y);
    }
    //隣接しているノードに向けて線を引く
    void drawLine() {
        stroke(255, 0, 0);
        textSize(10);
        for (Node neighbor : neighbors) {
            int dist = (int)(dist(neighbor.x, neighbor.y, x, y));
            text(dist, (x+neighbor.x)/2, (y+neighbor.y)/2);
            line(x, y, neighbor.x, neighbor.y);
        }
    }
}

void keyPressed() {
    //"d"のキーを押すことで出発点と目標点の変更が可能
    if (key == 'd') {
        String input = JOptionPane.showInputDialog("出発点と目的点をカンマ区切りで入力してください(例 : 0,9)");
        String[] inputs = input.split(",");
        try {
            startNode = Integer.parseInt(inputs[0]);
            endNode = Integer.parseInt(inputs[1]);
        }
        catch(Exception e) {
            JOptionPane.showMessageDialog(null, "カンマ区切りで2つ入力してください\n"+ input);
        }
    }
}

final int MAX = Integer.MAX_VALUE;
double[] d = new double[nodeCount];
int[] pi = new int[nodeCount];
int[] q = new int[nodeCount];
class DijkstraAlgorithm {
    void dijkstra() {
        init(startNode);
        while (!isEmpty()) {
            int u = 0;
            try{
                u = extractMin();
            }catch(ArrayIndexOutOfBoundsException e){
                break;
            }
            for (int i = 0; i < nodeCount; i++) {
                if (nodes[u].neighbors != null) {
                    if (nodes[u].neighbors.indexOf(nodes[i]) != -1) {
                        relax(u, i);
                    }
                }
            }
        }
        print_path(startNode, endNode);
    }
    //点の初期化
    void init(int startNode) {
        for (int i = 0; i < nodeCount; i++) {
            d[i] = MAX;
            pi[i] = -1;
            q[i] = 1;
        }
        d[startNode] = 0;
    }
    //最小になった頂点を取り除く
    int extractMin() throws ArrayIndexOutOfBoundsException{
        double min = MAX;
        int min_num = -1;
        for (int i = 0; i < nodeCount; i++) {
            if (d[i] < min && q[i] == 1) {
                min = d[i];
                min_num = i;
            }
        }
        q[min_num] = 0;
        return min_num;
    }
    //更新
    void relax(int u, int v) {
        double dist = getDist(nodes[u], nodes[v]);
        if (d[v] > d[u] + dist) {
            d[v] = d[u] + dist;
            pi[v] = u;
        }
    }

    void print_path(int startNode, int v) {
        if (v == startNode) {
            //      System.out.print(startNode);
        } else if (pi[v] == -1) {
            //      System.out.print("頂点" + v + "に向かう最短経路はありません");
        } else {
            print_path(startNode, pi[v]);
            //      System.out.print("⇒" + v);
        }
    }

    double getDist(Node node, Node otherNode) {
        return dist(node.x, node.y, otherNode.x, otherNode.y);
    }

    boolean isEmpty() {
        for (int i = 0; i < nodeCount; i++) {
            if (q[i] == 1) {
                return false;
            }
        }
        return true;
    }
}

暇があればこちらも説明とか載せていきたい。

遊び方

ノードをクリックしてドラッグすると動かすことができます。
経路にかかわるノードを移動させてやると最短経路が変わるのがみえるかと。

キーの"d"を押すと出発点と目標点を変更することができます。
最短経路が見つからないような点の組み合わせの場合や、出発点と目標点が直接結ばれておりつまらない場合は適当に変更してやってください。

最後に

無事ダイクストラ法で求めた経路を表示できるようになりましたが、結果を表示するだけでなくどうやってその最短経路を求めたのかというプロセスも表示していきたいですね。