0

ダイクストラ法をmain関数内の「課題追加部分」で実装するのですが方法がわかりません...
実装方法を見ても①から意味がわからない状態です...

import java.util.*;

public class Dijkstra {
    public static void main(String[] args) {
        final List<LocatedVertex> vertices = Arrays.asList(new LocatedVertex[]{
                new LocatedVertex(0, 40, 150),
                new LocatedVertex(1, 110, 80),
                new LocatedVertex(2, 110, 150),
                new LocatedVertex(3, 110, 220),
                new LocatedVertex(4, 190, 80),
                new LocatedVertex(5, 190, 150),
                new LocatedVertex(6, 190, 220),
                new LocatedVertex(7, 260, 150) });
        final List<WeightedEdge> edges = Arrays.asList(new WeightedEdge[] {
                new WeightedEdge(0, 1, 101, 45),
                new WeightedEdge(0, 2, 102, 12),
                new WeightedEdge(0, 3, 103, 53),
                new WeightedEdge(1, 2, 104, 7),
                new WeightedEdge(1, 5, 105, 14),
                new WeightedEdge(2, 3, 106, 47),
                new WeightedEdge(2, 4, 107, 5),
                new WeightedEdge(2, 5, 108, 26),
                new WeightedEdge(2, 6, 109, 16),
                new WeightedEdge(3, 5, 110, 8),
                new WeightedEdge(4, 1, 111, 9),
                new WeightedEdge(4, 7, 112, 23),
                new WeightedEdge(5, 4, 113, 2),
                new WeightedEdge(5, 6, 114, 20),
                new WeightedEdge(5, 7, 115, 11),
                new WeightedEdge(6, 3, 116, 18),
                new WeightedEdge(6, 7, 117, 7) });
        final AdjacencyList aList = new AdjacencyList(8, edges);


        GraphDrawer.drawDirectedGraph(vertices, aList, "対象のグラフ"); 


        List<WeightedEdge> spt = new ArrayList<WeightedEdge>();
        //課題追加部分
        /*①始点となるノードを決定
          ②始点となるノード以外の点を、未定義(または無限大)に設定
          ③始点のノードに隣接する全ノードの距離を求める
          ④最短距離のノードを確定する
          ⑤確定したノードに隣接している全ノードの距離を求める
                - 新しく計算された距離が現在の距離より短い ⇒ 新しく計算された距離を、確定距離とする
                - それ以外 ⇒ 現在の距離を、そのまま確定距離としておく
          ⑥現時点で、確定していないノードのうち最短距離のノードを確定する
          ⑦全ノードが確定されるまで、操作⑤~⑥を繰り返す       */

        List<LocatedVertex> s = vertices; //初期値S=V
        int[] d = new int[100];  //視点から頂点への重み和の最小値
        int[] p = new int[s.size()]; //1こ前の頂点
        while(!s.isEmpty()){
            int u = 0;
        }

        GraphDrawer.drawDirectedGraph(vertices, spt, "最短経路木");  
    }
}
import java.util.*;

/**
 * 隣接リスト
 *
 *
 */
public class AdjacencyList {

    private VertexAdjacencyList[] lists; // 隣接リスト

    /**
     * 頂点数を設定するコンストラクタ
     *
     * @param n
     *            頂点数
     */
    public AdjacencyList(int n) {
        lists = new VertexAdjacencyList[n];
        for (int i = 0; i < n; i++)
            lists[i] = new VertexAdjacencyList();
    }

    /**
     * 頂点数と辺集合から設定するコンストラクタ
     *
     * @param n
     *            頂点数
     * @param edges
     *            辺集合のList
     */
    public AdjacencyList(int n, List<WeightedEdge> edges) {

        this(n);

        for (WeightedEdge e : edges) {

            lists[e.getHead()].add(new WeightedEdgeRecord(e.getToe(), e.getLabel(), e.getWeight()));
        }

        for (int i = 0; i < n; i++) {

            Collections.sort(lists[i], new Comparator<WeightedEdgeRecord>() {
                @Override
                public int compare(WeightedEdgeRecord r1, WeightedEdgeRecord r2) {
                    return r1.toe - r2.toe;
                }
            });

        }
    }

    /**
     * 頂点数を戻すメソッド
     *
     * @return 頂点数
     */
    public int getNum() {

        return lists.length;
    }

    /**
     * 頂点番号idに頂点toeへの重みweightの辺を追加する
     *
     * @param id
     *            頂点番号
     * @param toe
     *            辺の終点
     * @param label
     *            ラベル
     * @param weight
     *            辺の重み
     */
    public void addEdge(int id, int toe, int label, int weight) {

        lists[id].add(new WeightedEdgeRecord(toe, label, weight));
    }

    /**
     * 指定の辺の重みを戻す
     *
     * @param id1
     *            始点
     * @param id2
     *            終点
     * @return 重み
     */
    public WeightedEdge getWeightedEdge(int id1, int id2) {

        WeightedEdge e = null;

        for (WeightedEdgeRecord r : lists[id1]) {

            if (r.toe == id2) {
                e = new WeightedEdge(id1, id2, r.label, r.weight);
                break;
            }
        }

        return e;
    }

    /**
     * 頂点番号idを起点にする重みつき有向辺のリストを戻す
     *
     * @param id
     *            頂点番号
     * @return 重みつき有向辺のリスト
     */
    public List<WeightedEdge> getWeightedEdges(int id) {

        List<WeightedEdge> ret = new ArrayList<>();

        for (WeightedEdgeRecord record : lists[id]) {
            ret.add(new WeightedEdge(id, record.toe, record.label, record.weight));
        }

        return ret;

    }

    public String toString() {

        String ret = "adjacency list:\n";

        for (int i = 0; i < lists.length - 1; i++)
            ret += String.format("%2d:%s\n", i, lists[i]);

        ret += String.format("%2d:%s\n", lists.length - 1, lists[lists.length - 1]);

        return ret;
    }

    /**
     * 1頂点に対する隣接リスト
     */
    private class VertexAdjacencyList extends LinkedList<WeightedEdgeRecord> {

        private static final long serialVersionUID = 1L;

        public String toString() {

            String ret = "";

            for (WeightedEdgeRecord r : this) {
                ret += "->" + r;
            }

            return ret;
        }
    }

    /**
     * 隣接リストのレコード
     */
    private class WeightedEdgeRecord {

        private int toe; // 隣接頂点
        private int label; // ラベル
        private int weight; // 重み

        private WeightedEdgeRecord(int toe, int label, int weight) {

            this.toe = toe;
            this.label = label;
            this.weight = weight;
        }

        public String toString() {

            return String.format("[%d,%d]", toe, weight);
        }

    }

}
import java.awt.geom.Point2D;

/**
 * 座標付き頂点
 */
public class LocatedVertex {

    /**
     * 頂点番号
     */
    private int id;

    /**
     * x座標
     */
    private int xPos = 0;

    /**
     * y座標
     */
    private int yPos = 0;

    /**
     * 頂点番号のみを与えるコンストラクタ
     * @param id 頂点番号
     */
    public LocatedVertex(int id) {
        this.id = id;
    }

    /**
     * 頂点番号と座標を与えるコンストラクタ
     * @param id 頂点番号
     * @param xPos x座標
     * @param yPos y座標
     */
    public LocatedVertex(int id, int xPos, int yPos) {
        this(id);
        this.xPos = xPos;
        this.yPos = yPos;
    }

    public int getId() {
        return id;
    }

    public Point2D.Double getPos(){

        return new Point2D.Double(xPos, yPos);
    };

}

/**
 * 重みつきグラフの辺を表すクラス
 *
 */
public class WeightedEdge {

    /**
     * 有向辺の場合は起点頂点
     */
    private int head;

    /**
     * 有向辺の場合は終点頂点
     */
    private int toe;

    /**
     * 辺のラベル
     */
    private int label;

    /**
     * 辺の重み
     */
    private int weight;

    /**
     * 起点,終点,辺ラベル,重みを与えるコンストラクタ
     * @param head 起点
     * @param toe 終点
     * @param label 辺ラベル
     * @param weight 重み
     */
    public WeightedEdge(int head, int toe, int label, int weight) {

        this.head = head;
        this.toe = toe;
        this.label = label;
        this.weight = weight;
    }

    public int getHead() {
        return head;
    }

    public int getToe() {
        return toe;
    }

    public int getWeight() {
        return weight;
    }

    /**
     * 起点頂点のidが終点頂点のidより大きいかを判定
     * @return true/false
     */
    public boolean isAnti() {

        return head > toe;
    }

    public int getLabel() {
        return label;
    }

    @Override
    public String toString() {

        String ret;

        if (weight != 0)
            ret = String.format("%d", weight);
        else
            ret = "";

        return ret;
    }
}

5
  • 上手く行ってないと思われている理由を質問文に含めて頂けませんでしょうか? 入力の例と、出力の例(エラーが出るならそのエラー、想定外の出力が出るなら想定していた出力と実際の出力)があると良さそうです :) 今のままだと回答しようとした方は何時バグるのかを考えるところから始めないといけないので、ちょっと大変です。
    – nekketsuuu
    Commented 2019年5月24日 14:05
  • 申し訳ございません。まず実装方法が検討つかないので実装とテストをするにさえ至っていない状態です汗
    – user32953
    Commented 2019年5月24日 14:11
  • 2
    では、どの部分を実装しようとして、どんなことを考えて上手くいかなかったのかを文章化して頂けると回答しやすそうです :) 単に「質問:私の代わりに実装してほしい」→「回答:これで動きます」だと根本的な解決にならないことがままあるからです。
    – nekketsuuu
    Commented 2019年5月24日 14:40
  • 1
    追記ありがとうございます! 1つ目のコードブロックの「課題追加部分」というコメントの下のコードを書きたいということですよね?(こういうことも書いておいてくださるとありがたいです) それではコメントには①~⑦まで手順が書かれていますが、①から分からないということでしょうか。
    – nekketsuuu
    Commented 2019年5月24日 15:32
  • すみません。そういうことになります。
    – user32953
    Commented 2019年5月25日 1:01

2 件の回答 2

1

以下の順番で理解していくのは如何でしょうか。

1. アルゴリズムを理解する

プログラムのことは一度忘れて、ダイクストラ法が何をしているアルゴリズムなのか、具体的なグラフに対してダイクストラ法を手で実行してみることで理解してみましょう。多少手間ですが、1ステップごとに状態がどう変化していくのかをノートに書いていき、ダイクストラ法の感覚を理解してください。「例示は理解の試金石」です。

2. プログラムで表現する

プログラムでダイクストラ法をどのように表現するのか確認してみましょう。「グラフ」をJavaのどのようなデータ構造で表現していて、①~⑦までの手順をどのようなコードで書けそうでしょうか。

今回のプログラムでは、グラフを頂点の集合と有向辺の集合の組とみなして、頂点の集合を List<LocatedVertex> 型の変数 vertices で、有向辺の集合を List<WeightedEdge> 型の変数 edges で表現しています。処理の都合上それぞれの頂点には座標の情報もついていますが、ダイクストラ法にとって本質的なのは頂点番号です。辺の方は、頂点番号ふたつで辺の開始点と終了点を指定し、更に辺の重みを指定しています。

続いて①から順番に、どうやったらプログラムとして書けるか考えていきます。「①始点となるノードを決定」では、頂点集合 vertices の中でどれが始点か覚えておくという処理です。ダイクストラ法では始点は最初から決まってるものなので「決定」というより元々の入力を表現すれば良いです。今回頂点には頂点番号がつけられているので、頂点番号だけ覚えておくようにしてみます。今回は 0 番の頂点を始点としたことにしてみましょう。

int u = 0

ここで一旦実行してみて、エラーが無いことを確認します。無ければ次に進みます。

続いて「②始点となるノード以外の点を、未定義(または無限大)に設定」は、説明がちょっと分かりにくいので噛み砕くと「各頂点に対して "始点からその頂点までの最短経路の距離" を表す変数を用意し、始点以外を未定義(または無限大)で初期化しておく」ということをします。さて、どのように実装すれば良いでしょう。頂点番号から距離が分かる辞書があれば良さそうです。もし頂点番号が必ず 0 から始まって 1 ずつ増えるのであれば、配列を使えば OK でしょう。

int[] d = new int[vertices.size()];       // d[i] が 頂点番号 i の頂点に対する「その頂点までの距離」
int inf = (int)Double.POSITIVE_INFINITY;  // 大きな整数値を用意
for (int i = 1; i < d.length; i++) {
    d[i] = inf;                           // 今回は大きな整数値で初期化してみます (整数における "無限大" のように扱えます)
}

ここで一旦実行してみて、エラーが無いことを確認します。無ければ次に進みます。

③から最後までここに書いてしまうと回答が長くなりすぎてしまうのでここまでにして、この先も同じように手順をソースコードとして表現していき、エラーが出ないか確認してみましょう。特に「確定していないノード」をどうやって表現するかがポイントです。Wikipedia に載っている疑似コードや、検索したら見つかるソースコードがヒントになるでしょう。

もし個別によく分からない箇所があれば、問題を細かく分割して新しい質問として投稿してみてください。

3. テストする

ダイクストラ法が実装できたら、自分が思っているものが実装できたかどうかテストしてみましょう。ひとつの入力例で確認して OK でも、他の入力例ではバグが判明するかもしれません。いくつかの入力例を用意し、上手く動いているか確認してみましょう。

0

①始点となるノードを決定

初めは, 決め打ちで始点を決定します.

②始点となるノード以外の点を、未定義(または無限大)に設定

Double.POSITIVE_INFINITYを使うと正の無限大に設定できます.

③始点のノードに隣接する全ノードの距離を求める

ソースを読むと, AdjacencyList#getWeightedEdges(int id)で始点ノードから伸びる有向グラフのリストを取得できるようです.このリストから距離d[i]を更新できると思います.

④最短距離のノードを確定する

距離の集合d[i]の中で最も小さい&選択されていないノードを確定します.具体的には,始点の距離dは0なので,距離集合d[i]の中では最小になりますが,始点は既に選択済みとして扱われるべきなので,最短距離ノードとして確定してはいけません.

⑤確定したノードに隣接している全ノードの距離を求める

これは,③と同じ処理で解決できると思います.

  • 新しく計算された距離が現在の距離より短い ⇒ 新しく計算された距離を、確定距離とする
  • それ以外 ⇒ 現在の距離を、そのまま確定距離としておく

⑥現時点で、確定していないノードのうち最短距離のノードを確定する

これも④と同じ処理で解決できると思います.

一つわからないのは,int[] d = new int[100]の部分で,多分s.size()だと思います.(始点から頂点への重み和の最小値の数は,頂点の数しかないため)

List<LocatedVertex> s = vertices; //初期値S=V
        int[] d = new int[100];  //視点から頂点への重み和の最小値
        int[] p = new int[s.size()]; //1こ前の頂点
        while(!s.isEmpty()){
            int u = 0;
        }

この質問に回答するには、ログインする必要があります。