ダイクストラ法の実装
ダイクストラ法を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;
}
}