頂点 + エッジを動的に生成しようとしていますが、座標間の最短パスを計算しようとするとエラーが発生します。
TestDijkstra3.java:
package maze_drawing;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.io.UnsupportedEncodingException;
import java.util.PriorityQueue;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
class Vertex implements Comparable<Vertex>
{
public final String name;
public static String faceDirection;
public Edge[] adjacencies;
public double minDistance = Double.POSITIVE_INFINITY;
public Vertex previous;
public Vertex(String argName) {
name = argName;
}
public String toString() {
return name;
}
public int compareTo(Vertex other)
{
return Double.compare(minDistance, other.minDistance);
}
}
class Edge
{
public final Vertex target;
public final String direction;
public Edge(Vertex argTarget, String argDirection){
target = argTarget;
direction = argDirection;
}
}
public class TestDijkstra3
{
public static void computePaths(Vertex source, String faceDirection)
{
source.minDistance = 0;
double turningweight = 0;
String robotDirection = faceDirection;
PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>();
vertexQueue.add(source);
while (!vertexQueue.isEmpty()) {
Vertex u = vertexQueue.poll();
// Visit each edge exiting u
for (Edge e : u.adjacencies)
{
Vertex v = e.target;
//double weight = e.weight;
String direction = e.direction; //DIRECTION TO DESTINATION
double distanceThroughU = u.minDistance + 10 + turningweight;
if (distanceThroughU < v.minDistance) {
vertexQueue.remove(v);
v.minDistance = distanceThroughU ;
v.previous = u;
robotDirection = direction;
vertexQueue.add(v);
}
}
}
}
public static List<Vertex> getShortestPathTo(Vertex target)
{
List<Vertex> path = new ArrayList<Vertex>();
for (Vertex vertex = target; vertex != null; vertex = vertex.previous)
path.add(vertex);
Collections.reverse(path);
return path;
}
public static void main(String args[]) throws FileNotFoundException, UnsupportedEncodingException
{
int startX = 0;
int startY = 0;
int endX = 3;
int endY = 3;
String facing = "N";
String start = ""+startX+""+startY;
String end = ""+endX+""+endY;
Vertex v00 = new Vertex("00");
Vertex v10 = new Vertex("10");
Vertex v20 = new Vertex("20");
Vertex v30 = new Vertex("30");
Vertex v40 = new Vertex("40");
Vertex v50 = new Vertex("50");
Vertex v60 = new Vertex("60");
Vertex v01 = new Vertex("01");
Vertex v11 = new Vertex("11");
Vertex v21 = new Vertex("21");
Vertex v31 = new Vertex("31");
Vertex v41 = new Vertex("41");
Vertex v51 = new Vertex("51");
Vertex v61 = new Vertex("61");
Vertex v02 = new Vertex("02");
Vertex v12 = new Vertex("12");
Vertex v22 = new Vertex("22");
Vertex v32 = new Vertex("32");
Vertex v42 = new Vertex("42");
Vertex v52 = new Vertex("52");
Vertex v62 = new Vertex("62");
Vertex v03 = new Vertex("03");
Vertex v13 = new Vertex("13");
Vertex v23 = new Vertex("23");
Vertex v33 = new Vertex("33");
Vertex v43 = new Vertex("43");
Vertex v53 = new Vertex("53");
Vertex v63 = new Vertex("63");
Vertex v04 = new Vertex("04");
Vertex v14 = new Vertex("14");
Vertex v24 = new Vertex("24");
Vertex v34 = new Vertex("34");
Vertex v44 = new Vertex("44");
Vertex v54 = new Vertex("54");
Vertex v64 = new Vertex("64");
Vertex v05 = new Vertex("05");
Vertex v15 = new Vertex("15");
Vertex v25 = new Vertex("25");
Vertex v35 = new Vertex("35");
Vertex v45 = new Vertex("45");
Vertex v55 = new Vertex("55");
Vertex v65 = new Vertex("65");
Vertex v06 = new Vertex("06");
Vertex v16 = new Vertex("16");
Vertex v26 = new Vertex("26");
Vertex v36 = new Vertex("36");
Vertex v46 = new Vertex("46");
Vertex v56 = new Vertex("56");
Vertex v66 = new Vertex("66");
v00.adjacencies = new Edge[]{ new Edge(v10, "E"), new Edge(v01, "N") };
v10.adjacencies = new Edge[]{ new Edge(v00, "S"), new Edge(v20, "E") };
v20.adjacencies = new Edge[]{ new Edge(v10, "W"), new Edge(v21, "N"), new Edge(v30, "E") };
v30.adjacencies = new Edge[]{ new Edge(v20, "W"), new Edge(v31, "N"), new Edge(v40, "E") };
v40.adjacencies = new Edge[]{ new Edge(v30, "W"), new Edge(v50, "E") };
v50.adjacencies = new Edge[]{ new Edge(v40, "W"), new Edge(v51, "N") };
v60.adjacencies = new Edge[]{ new Edge(v61, "N") };
v01.adjacencies = new Edge[]{ new Edge(v02, "N"), new Edge(v00, "S") };
v11.adjacencies = new Edge[]{ new Edge(v12, "N") };
v21.adjacencies = new Edge[]{ new Edge(v31, "E"), new Edge(v20, "S") };
v31.adjacencies = new Edge[]{ new Edge(v21, "W"), new Edge(v30, "S") };
v41.adjacencies = new Edge[]{ new Edge(v51, "E"), new Edge(v42, "N") };
v51.adjacencies = new Edge[]{ new Edge(v50, "S"), new Edge(v41, "W") };
v61.adjacencies = new Edge[]{ new Edge(v60, "S"), new Edge(v62, "N") };
v02.adjacencies = new Edge[]{ new Edge(v01, "S"), new Edge(v03, "N") };
v12.adjacencies = new Edge[]{ new Edge(v11, "S"), new Edge(v13, "N"), new Edge(v22, "E") };
v22.adjacencies = new Edge[]{ new Edge(v12, "W"), new Edge(v32, "E") };
v32.adjacencies = new Edge[]{ new Edge(v22, "W"), new Edge(v42, "E") };
v42.adjacencies = new Edge[]{ new Edge(v32, "W"), new Edge(v41, "S"), new Edge(v43, "N") };
v52.adjacencies = new Edge[]{ new Edge(v62, "E") };
v62.adjacencies = new Edge[]{ new Edge(v52, "W"), new Edge(v61, "S"), new Edge(v63, "N") };
v03.adjacencies = new Edge[]{ new Edge(v13, "E"), new Edge(v02, "S"), new Edge(v04, "N") };
v13.adjacencies = new Edge[]{ new Edge(v03, "W"), new Edge(v23, "E"), new Edge(v12, "S") };
v23.adjacencies = new Edge[]{ new Edge(v13, "W"), new Edge(v33, "E") };
v33.adjacencies = new Edge[]{ new Edge(v34, "N"), new Edge(v23, "W") };
v43.adjacencies = new Edge[]{ new Edge(v42, "S"), new Edge(v44, "N"), new Edge(v53, "E") };
v53.adjacencies = new Edge[]{ new Edge(v43, "W") };
v63.adjacencies = new Edge[]{ new Edge(v62, "S"), new Edge(v64, "N") };
v04.adjacencies = new Edge[]{ new Edge(v05, "N"), new Edge(v03, "S") };
v14.adjacencies = new Edge[]{ new Edge(v15, "N"), new Edge(v24, "E") };
v24.adjacencies = new Edge[]{ new Edge(v14, "W"), new Edge(v25, "N") };
v34.adjacencies = new Edge[]{ new Edge(v33, "S"), new Edge(v35, "N") };
v44.adjacencies = new Edge[]{ new Edge(v45, "N"), new Edge(v43, "S") };
v54.adjacencies = new Edge[]{ new Edge(v64, "E") };
v64.adjacencies = new Edge[]{ new Edge(v54, "W"), new Edge(v65, "N"), new Edge(v63, "S") };
v05.adjacencies = new Edge[]{ new Edge(v06, "N"), new Edge(v04, "S") };
v15.adjacencies = new Edge[]{ new Edge(v14, "S") };
v25.adjacencies = new Edge[]{ new Edge(v26, "N"), new Edge(v24, "S") };
v35.adjacencies = new Edge[]{ new Edge(v36, "N"), new Edge(v34, "S") };
v45.adjacencies = new Edge[]{ new Edge(v55, "E"), new Edge(v44, "S") };
v55.adjacencies = new Edge[]{ new Edge(v45, "W") };
v65.adjacencies = new Edge[]{ new Edge(v64, "S"), new Edge(v66, "N") };
v06.adjacencies = new Edge[]{ new Edge(v16, "E"), new Edge(v05, "S") };
v16.adjacencies = new Edge[]{ new Edge(v06, "W"), new Edge(v26, "E") };
v26.adjacencies = new Edge[]{ new Edge(v16, "W"), new Edge(v25, "S") };
v36.adjacencies = new Edge[]{ new Edge(v35, "S"), new Edge(v46, "E") };
v46.adjacencies = new Edge[]{ new Edge(v36, "W"), new Edge(v56, "E") };
v56.adjacencies = new Edge[]{ new Edge(v46, "W"), new Edge(v66, "E") };
v66.adjacencies = new Edge[]{ new Edge(v56, "W"), new Edge(v65, "S") };
Vertex[] vertices = { v00, v10, v20, v30, v40, v50, v60, v01, v11, v21, v31, v41, v51, v61, v02, v12, v22, v32, v42, v52, v62, v03, v13, v23, v33, v43, v53, v63, v04, v14, v24, v34, v44, v54, v64, v05, v15, v25, v35, v45, v55, v65, v06, v16, v26, v36, v46, v56, v66 };
Vertex[] vertices2 = new Vertex[49];
System.out.println("Start");
HentMazeFil mazeFile = new HentMazeFil();
String lineCoords;
Vertex v[] = new Vertex[67];
String Rest[] = new String[67];
String wholeLine[] = new String[49];
for (int i = 0; i < 49; i++) {
lineCoords = mazeFile.nextLineCoords();
if (lineCoords != null) {
v[Integer.parseInt(lineCoords.substring(0, 2))] = new Vertex(lineCoords.substring(0, 2));
Rest[Integer.parseInt(lineCoords.substring(0, 2))] = new String(lineCoords.substring(2, 6));
wholeLine[i] = lineCoords;
}
else {
System.out.println("Line = Null"); // End of while loop.
break;
}
lineCoords = mazeFile.nextLineCoords(); // Skipping "extra lines" from Linux files.
}
//System.out.println(vertices);
//System.out.println(vertices2);
String line;
//Adding edges
for (int i = 0; i < 49; i++) {
line = wholeLine[i];
v[Integer.parseInt(line.substring(0, 2))] = new Vertex(line.substring(0, 2));
Rest[Integer.parseInt(line.substring(0, 2))] = new String(line.substring(2, 6));
if (line.charAt(2) == '0') {
if (line.charAt(3) == '0') {
if (line.charAt(4) == '0') {
if (line.charAt(5) == '0') {
v[Integer.parseInt(line.substring(0, 2))].adjacencies = new Edge[] {new Edge (v[Integer.parseInt(line.substring(0, 2))+1], "N") ,new Edge (v[Integer.parseInt(line.substring(0, 2))+10], "E"), new Edge (v[Integer.parseInt(line.substring(0, 2))-1], "S"), new Edge (v[Integer.parseInt(line.substring(0, 2))-10], "W")};
}
else {
v[Integer.parseInt(line.substring(0, 2))].adjacencies = new Edge[] {new Edge (v[Integer.parseInt(line.substring(0, 2))+1], "N") ,new Edge (v[Integer.parseInt(line.substring(0, 2))+10], "E"), new Edge (v[Integer.parseInt(line.substring(0, 2))-1], "S")};
}
}
else if (line.charAt(5) == '0') {
v[Integer.parseInt(line.substring(0, 2))].adjacencies = new Edge[] {new Edge (v[Integer.parseInt(line.substring(0, 2))+1], "N") ,new Edge (v[Integer.parseInt(line.substring(0, 2))+10], "E"), new Edge (v[Integer.parseInt(line.substring(0, 2))-10], "W")};
}
else {
v[Integer.parseInt(line.substring(0, 2))].adjacencies = new Edge[] {new Edge (v[Integer.parseInt(line.substring(0, 2))+1], "N") ,new Edge (v[Integer.parseInt(line.substring(0, 2))+10], "E")};
}
}
else if (line.charAt(4) == '0') {
if (line.charAt(5) == '0') {
v[Integer.parseInt(line.substring(0, 2))].adjacencies = new Edge[] {new Edge (v[Integer.parseInt(line.substring(0, 2))+1], "N"), new Edge (v[Integer.parseInt(line.substring(0, 2))-1], "S"), new Edge (v[Integer.parseInt(line.substring(0, 2))-10], "W")};
}
else {
v[Integer.parseInt(line.substring(0, 2))].adjacencies = new Edge[] {new Edge (v[Integer.parseInt(line.substring(0, 2))+1], "N") , new Edge (v[Integer.parseInt(line.substring(0, 2))-1], "S")};
}
}
else if (line.charAt(5) == '0') {
v[Integer.parseInt(line.substring(0, 2))].adjacencies = new Edge[] {new Edge (v[Integer.parseInt(line.substring(0, 2))+1], "N") , new Edge (v[Integer.parseInt(line.substring(0, 2))-10], "W")};
}
else {
v[Integer.parseInt(line.substring(0, 2))].adjacencies = new Edge[] {new Edge (v[Integer.parseInt(line.substring(0, 2))+1], "N")};
}
}
else if (line.charAt(3) == '0') {
if (line.charAt(4) == '0') {
if (line.charAt(5) == '0') {
v[Integer.parseInt(line.substring(0, 2))].adjacencies = new Edge[] {new Edge (v[Integer.parseInt(line.substring(0, 2))+10], "E"), new Edge (v[Integer.parseInt(line.substring(0, 2))-1], "S"), new Edge (v[Integer.parseInt(line.substring(0, 2))-10], "W")};
}
else {
v[Integer.parseInt(line.substring(0, 2))].adjacencies = new Edge[] {new Edge (v[Integer.parseInt(line.substring(0, 2))+10], "E"), new Edge (v[Integer.parseInt(line.substring(0, 2))-1], "S")};
}
}
else if (line.charAt(5) == '0') {
v[Integer.parseInt(line.substring(0, 2))].adjacencies = new Edge[] {new Edge (v[Integer.parseInt(line.substring(0, 2))+10], "E"), new Edge (v[Integer.parseInt(line.substring(0, 2))-10], "W")};
}
else {
v[Integer.parseInt(line.substring(0, 2))].adjacencies = new Edge[] {new Edge (v[Integer.parseInt(line.substring(0, 2))+10], "E")};
}
}
else if(line.charAt(4) == '0') {
if (line.charAt(5) == '0') {
v[Integer.parseInt(line.substring(0, 2))].adjacencies = new Edge[] {new Edge (v[Integer.parseInt(line.substring(0, 2))-1], "S"), new Edge (v[Integer.parseInt(line.substring(0, 2))-10], "W")};
}
else {
v[Integer.parseInt(line.substring(0, 2))].adjacencies = new Edge[] {new Edge (v[Integer.parseInt(line.substring(0, 2))-1], "S")};
}
}
}//end of i loop
int z = 0;
for (int i = 0; i < 67; i++) {
if (v[i] != null) {
vertices2[z] = v[i];
//System.out.println(vertices2[z]);
z++;
}
}
System.out.println("v[0] = "+v[0]);
for (Edge e :v[0].adjacencies) {
System.out.println("Target: "+e.target);
}
System.out.println("v[1] = "+v[1]);
for (Edge e :v[1].adjacencies) {
System.out.println("Target: "+e.target);
}
System.out.println("End");
for (int i = 0; i < 49; i++) {
if (vertices[i].toString().equals(start)) {
computePaths(vertices[i], facing);
}
}
for (int i = 0; i < 49; i++) {
if (vertices[i].toString().equals(end)) {
System.out.println("Distance to " + vertices[i] + ": " + vertices[i].minDistance);
List<Vertex> path = getShortestPathTo(vertices[i]);
System.out.println("Path: " + path);
PrintWriter writer = new PrintWriter("traversalfile.txt", "UTF-8");
for (int j = 0; j < path.size()-1; j++) {
int directionValue = Integer.parseInt(path.get(j+1).toString())-Integer.parseInt(path.get(j).toString());
if (directionValue == 1) {
System.out.println("N");
writer.println("N");
}
else if (directionValue == 10) {
System.out.println("E");
writer.println("E");
}
else if (directionValue == -1) {
System.out.println("S");
writer.println("S");
}
else if (directionValue == -10) {
System.out.println("W");
writer.println("W");
}
else {
System.out.println("Something went wrong");
}
}
writer.close();
}
}
}
}
ご覧のとおり、コードに沿って 2 つのオプションがあります。ハードコーディングされた頂点 + エッジ (最初の部分) を使用したソリューションで、正常に動作しています。もう 1 つは、.txt ファイルから を読み取り、そこから変換するより動的なアプローチです。これらの読み取り値を頂点 + エッジに変換します。私のエラーは、コードの最後で「vertices」->「vertices2」を変更すると、動的頂点メソッドを使用する必要があるため、次のエラーが表示されます:「開始 v[0] = 00 ターゲット: 01 ターゲット: 10 v[1] = 01 ターゲット: 02 ターゲット: 00 スレッド「メイン」での終了例外 java.lang.NullPointerException maze_drawing.TestDijkstra3.computePaths(TestDijkstra3.java:60) で maze_drawing.TestDijkstra3.main(TestDijkstra3.java: 341) //これは "computePaths(vertices2[i], Facing);" Java Result: 1" にあります
ただし、(上記のコードのように)「頂点」を指定して実行すると、結果は問題ありません。
開始 v[0] = 00 ターゲット: 01 ターゲット: 10 v[1] = 01 ターゲット: 02 ターゲット: 00 33 までの終了距離: 60.0 パス: [00, 01, 02, 03, 13, 23, 33] N N N E E E
何らかの理由で、「頂点」と「頂点 2」の間に何らかの違いがあるはずです。for ループでそれらを出力すると、次のようになります。
出力: V1: 00 V2: 00 V1: 10 V2: 01 V1: 20 V2: 02 V1: 30 V2: 03 V1: 40 V2: 04 ... など
ここでうまくいきません：
int z = 0;
for (int i = 0; i < 67; i++) {
if (v[i] != null) {
vertices2[z] = v[i];
System.out.println(vertices2[z]);
z++;
}
}
したがって、2 つの問題があります。1. 上記の for ループを変更する方法がわからないため、最初に @10 を読み取り (どのように表示されるかについては「newtestmap.map」を参照)、次に @1 を読み取ります。2.配列の順序がvertices2でちょっと混乱していても、「computepath」は機能するはずだと思いますが、機能しません。
問題がどこにあるかわかりますか?
前もって感謝します。
HentMazeFil.java :
package maze_drawing;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class HentMazeFil {
java.io.File file;
String lineCoords;
Scanner input;
public HentMazeFil() {
file = new java.io.File("newtestmap.map");
try {
input = new Scanner(file);
} catch (FileNotFoundException ex) {
System.out.println("File dont exist");
}
}
public String nextLineCoords() {
if (input.hasNext()) {
lineCoords = input.nextLine();
return lineCoords;
}
return null;
}
}
新しいtestmap.map:
000011
101010
200010
300010
401010
500110
600111
010101
110111
211001
311100
410011
511100
610101
020101
120001
221010
321010
420100
521011
620100
030001
131000
231010
330110
430001
531110
630101
040101
140011
240110
340101
440101
541011
640100
050101
151101
250101
350101
451001
551110
650101
061001
161010
261100
361001
461010
561010
661100