Go to Qiita Advent Calendar 2024 Top
LoginSignup
2
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@NekoCan

[Processing]ダイクストラ法の探索を可視化

Last updated at Posted at 2021-06-08

#導入
地図アプリとか乗換案内アプリとか、移動する時にコストを考えないといけない場合の探索はダイクストラ法が使われるんですって
で、実行したら出来たわけですが、

  • その過程がわかりにくいので見えたい
  • 座標がバラバラでコンソール表示がつらい

という理由から可視化しました

#実行結果
ダイクストラ法Processing.gif
##解説

状況 画像
スタート image.png
ゴール image.png
未探索のノード緑 image.png
探索中のノード青 image.png
探索済のノード赤 image.png
移動コスト image.png
ノードまでの最小コスト image.png
探索対象ノード image.png
探索先 image.png
最小コスト経路 image.png

に変化させながら探索してます
##入力
スタート地点、ゴール地点、探索終了後にもう1回探索するか(y or n)
image.png

#参考
##processing導入の参考サイト
IntelliJ IDEAでProcessingを書く
##グラフ（マップ）とダイクストラ法の手順の参考
ダイクストラ (Dijkstra) 法

#ソースコード
##内訳
Processingを実行する都合上、処理は1つのクラスに全部押込みました
内訳を説明すると

  1. Nodeクラス
  2. Edgeクラス
  3. グローバル変数
  4. メインメソッド（影薄い）
  5. Processing
    1. settting()
    2. setup()
    3. draw()ここでダイクストラ法を順々に実行
  6. 特に重要じゃないメソッド
  7. マップの状況を描くメソッド

合計：258行
300行いってないのでセーフ

##コード
###Dijkstra_List

Dijkstra_List.java
import processing.core.*;

import java.util.ArrayList;
import java.util.Scanner;

//processing導入の参考サイト
//https://qiita.com/shion1118/items/49b803b3217e642cfbd1
//グラフの参考
//https://nw.tsuda.ac.jp/lec/dijkstra/
public class Dijkstra_List extends PApplet {
    private class Node {
        String name;//ノード名
        int cost;//最小コスト
        Node minFrom;//最短距離の来た道
        ArrayList<Edge> edge;//エッジのリスト
        Determine determine;//確定状況
        PVector pos;//位置

        Node(String name, PVector pos) {
            this.name = name;
            this.pos = new PVector(pos.x * width, pos.y * height);
            cost = Integer.MAX_VALUE;
            edge = new ArrayList<>();
            determine = Determine.未確定;
        }

        @Override
        public String toString() {
            return getColor() + name + "\u001b[00m";
        }

        public void draw() {
            fill(pColor());
            noStroke();
            ellipse(pos.x, pos.y, 20, 20);
            fill(0);
            text(name, pos.x, pos.y + 5);
            text((cost == Integer.MAX_VALUE ? "∞" : cost + ""), pos.x, pos.y - 15);
        }

        private String getColor() {
            StringBuilder str = new StringBuilder("\u001b[00;");
            switch (determine) {
                case 未確定 -> str.append("32");
                case 確定中 -> str.append("33");
                case 確定済 -> str.append("31");
            }
            return str.append("m").toString();
        }

        private int pColor() {
            return switch (determine) {
                case 未確定 -> color(100, 255, 100);
                case 確定中 -> color(100, 100, 255);
                case 確定済 -> color(255, 100, 100);
            };
        }
    }

    public class Edge {
        final Node TO;
        final int COST;
        Edge(int cost, Node to) {
            this.COST = cost;
            this.TO = to;
        }
    }

    Scanner sc;
    Node[] graph;
    int start = -1, goal = -1;
    Node currentNode;
    int searchEdgeIndex = -1;
    DijkstraMode flow = DijkstraMode.スタート設定;

    public static void main(String[] args) {
        PApplet.main("Dijkstra_List");
    }

    @Override
    public void settings() {
        size(1500, 500);//windowサイズ
    }

    @Override
    public void setup() {
        frameRate(2);
        getSurface().setAlwaysOnTop(true);//windowを常に前面にする
        textAlign(CENTER);
        sc = new Scanner(System.in);
        init();
    }

    void init() {
        setData();
        start = goal = searchEdgeIndex = -1;
        currentNode = null;
        flow = DijkstraMode.スタート設定;
        printMap();
    }

    @Override
    public void draw() {
        switch (flow) {
            case スタート設定 -> {
                while ((start = searchName(input("start name"))) == -1) {
                    for (Node n : graph) System.out.print(n.name + " ");
                    System.out.println("：の中から選んでください");
                }
                flow = DijkstraMode.ゴール設定;
            }
            case ゴール設定 -> {
                while ((goal = searchName(input("goal name"))) == -1) {
                    for (Node n : graph) System.out.print(n.name + " ");
                    System.out.println("：の中から選んでください");
                }
                System.out.println("探索開始");
                graph[start].cost = 0;
                flow = DijkstraMode.最短距離ノード設定;
            }
            case 最短距離ノード設定 -> {
                int minCostNode = minCost();
                if (minCostNode == -1) {
                    flow = DijkstraMode.ルート確定;
                    break;
                }
                currentNode = graph[minCostNode];
                currentNode.determine = Determine.確定中;
                searchEdgeIndex = 0;
                flow = DijkstraMode.接続ノードコスト更新;
            }
            case 接続ノードコスト更新 -> {
                Edge edge = currentNode.edge.get(searchEdgeIndex++);
                if (edge.TO.determine != Determine.確定済 && currentNode.cost + edge.COST < edge.TO.cost) {
                    edge.TO.determine = Determine.確定中;
                    edge.TO.cost = currentNode.cost + edge.COST;
                    edge.TO.minFrom = currentNode;
                    //System.out.println(currentNode + " to "+edge.TO +" cost"+ edge.TO.cost);
                }
                if (searchEdgeIndex >= currentNode.edge.size()) {
                    searchEdgeIndex = -1;
                    flow = DijkstraMode.ノードを確定;
                }
            }
            case ノードを確定 -> {
                currentNode.determine = Determine.確定済;
                flow = DijkstraMode.最短距離ノード設定;
            }
            case ルート確定 -> {
                if (input("continue ? y or other word").equals("y")) {
                    init();
                    return;
                } else exit();
            }
        }
        printMap();
    }

    int minCost() {
        int index = -1, min = Integer.MAX_VALUE;
        for (int i = 0; i < graph.length; i++) {
            if (graph[i].determine == Determine.確定済) continue;
            if (graph[i].cost >= min) continue;
            min = graph[i].cost;
            index = i;
        }
        return index;
    }

    void setData() {
        graph = new Node[8];
        graph[0] = new Node("A", new PVector(0.1f, 0.5f));
        graph[1] = new Node("B", new PVector(0.3f, 0.3f));
        graph[2] = new Node("C", new PVector(0.4f, 0.6f));
        graph[3] = new Node("D", new PVector(0.3f, 0.8f));
        graph[4] = new Node("E", new PVector(0.6f, 0.1f));
        graph[5] = new Node("F", new PVector(0.7f, 0.2f));
        graph[6] = new Node("G", new PVector(0.7f, 0.7f));
        graph[7] = new Node("H", new PVector(0.9f, 0.5f));
        setBranch(0, 1, 1);
        setBranch(0, 2, 7);
        setBranch(0, 3, 2);
        setBranch(1, 4, 2);
        setBranch(1, 5, 4);
        setBranch(2, 5, 2);
        setBranch(2, 6, 3);
        setBranch(3, 6, 5);
        setBranch(4, 5, 1);
        setBranch(5, 7, 6);
        setBranch(6, 7, 2);
    }

    void setBranch(int from, int to, int cost) {
        graph[from].edge.add(new Edge(cost, graph[to]));
        graph[to].edge.add(new Edge(cost, graph[from]));
    }

    int searchName(String name) {
        for (int i = 0; i < graph.length; i++) if (graph[i].name.equals(name)) return i;
        return -1;
    }

    String input(String name) {
        System.out.print(name + "\t->");
        return sc.next();
    }

    void printMap() {
        background(200);
        for (Node node : graph) for (Edge edge : node.edge) edgeLine(node, edge, color(255));//エッジを描画
        if (searchEdgeIndex != -1) { //接続してるノードのコストを更新する様子の線
            edgeLine(currentNode, currentNode.edge.get(searchEdgeIndex), color(50, 50, 255));
        }
        if (start != -1) {//スタート地点をマーク
            noFill();
            stroke(50, 255, 50);
            strokeWeight(3);
            ellipse(graph[start].pos.x, graph[start].pos.y, 30, 30);
            text("Start", graph[start].pos.x, graph[start].pos.y + 30);
        }
        if (goal != -1) {
            noFill();
            stroke(255, 50, 50);
            strokeWeight(3);//ゴール地点をマーク
            ellipse(graph[goal].pos.x, graph[goal].pos.y, 30, 30);
            text("Goal", graph[goal].pos.x, graph[goal].pos.y + 30);

            if (graph[goal].minFrom != null) {//ゴールへのルートがある場合は表示
                stroke(color(100, 255, 100));
                strokeWeight(4);
                for (Node n = graph[goal]; n.minFrom != null; n = n.minFrom)
                    line(n.pos.x, n.pos.y, n.minFrom.pos.x, n.minFrom.pos.y);
            }
        }
        if (currentNode != null) {//最短距離を確定させるノードをマーク
            noFill();
            stroke(50, 50, 255);
            strokeWeight(2);
            ellipse(currentNode.pos.x, currentNode.pos.y, 25, 25);
        }
        //各ノードを表示
        for (Node node : graph) node.draw();
        //進行モードを表示
        getSurface().setTitle(flow.name());
    }

    void edgeLine(Node node, Edge edge, int color) {
        PVector center = node.pos.copy().add(edge.TO.pos).mult(0.5f);
        stroke(color);
        line(node.pos.x, node.pos.y, edge.TO.pos.x, edge.TO.pos.y);
        fill(0);
        text(edge.COST, center.x, center.y - 5);
    }

}

###DijkstraMode

DijkstraMode.java
public enum DijkstraMode {
    スタート設定, ゴール設定, 最短距離ノード設定, 接続ノードコスト更新, ノードを確定, ルート確定
}

###Determine

Determine.java
public enum Determine {
    未確定, 確定中, 確定済
}

#まとめ
結果だけ得るよりも、途中経過を得る方がアルゴリズムがよく理解できるような気がします
ダイクストラ法Processing.gif

##苦労した点

  • ダイクストラ法をアニメーションするために処理を分割する
  • 文字サイズや色

アルゴリズムに関係ない所で苦労します。本当にありがとうございました。

2
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
2
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?