我正在尝试动态生成 Vertex + 边，但是当我尝试计算坐标之间的最短路径时出现错误。
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();
}
}
}
}
如您所见，代码中有两个选项：一个解决方案，带有硬编码的顶点 + 边（第一部分），工作正常，以及一个更动态的方法，它从 .txt 文件中读取，并从中转换这些读数到顶点+边。我的错误是，当我在代码末尾更改“顶点”->“顶点2”时，所以我应该使用动态顶点方法，我得到错误：“开始 v[0] = 00 目标：01 目标：10 v[1] = 01 目标：02 目标：00 在 maze_drawing.TestDijkstra3.computePaths(TestDijkstra3.java:60) 的 maze_drawing.TestDijkstra3.main(TestDijkstra3.java: 341) //这是在 "computePaths(vertices2[i], faces);" 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++;
}
}
所以我有两个问题： 1. 我似乎不知道如何更改上面的 for 循环，所以它首先读取@10（请参阅“newtestmap.map”了解它的外观），然后是@1。2.我仍然认为“计算路径”应该可以工作，即使数组顺序在 vertices2 中有点混乱，但事实并非如此。
你能看出问题出在哪里吗？
提前致谢。
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;
}
}
newtestmap.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