关于如何考虑重组代码以使其更易于调试,我有一些建议:
- 您当前正在将最短路径信息与顶点一起存储。这不是一个好的设计。最好将图上的信息与最短路径上的易失性信息分开(并且是不可变的,即没有设置器)。
当前,仅最终顶点被打印,最小距离似乎等于无穷大。我似乎找不到问题所在,因为没有将顶点添加到“最短路径” ArrayList中。我还想打印出路径所占据的所有边缘。任何建议都非常欢迎,以下是我的完整代码,谢谢!
DijkstraShortestPath
public void computeShortestPaths(Vertex sourceVertex){
sourceVertex.setDistance(0);
PriorityQueue<Vertex> priorityQueue = new PriorityQueue<>();
priorityQueue.add(sourceVertex);
sourceVertex.setVisited(true);
while( !priorityQueue.isEmpty() ){
// Getting the minimum distance vertex from priority queue
Vertex actualVertex = priorityQueue.poll();
for(Edge edge : actualVertex.getAdjacenciesList()){
Vertex v = edge.getTargetVertex();
if(!v.isVisited())
{
double newDistance = actualVertex.getDistance() + edge.getWeight();
if( newDistance < v.getDistance() ){
priorityQueue.remove(v);
v.setDistance(newDistance);
v.setPredecessor(actualVertex);
priorityQueue.add(v);
}
}
}
actualVertex.setVisited(true);
}
}
public List<Vertex> getShortestPathTo(Vertex targetVertex){
List<Vertex> path = new ArrayList<>();
for(Vertex vertex=targetVertex;vertex!=null;vertex=vertex.getPredecessor()){
path.add(vertex);
}
Collections.reverse(path);
return path;
}
}
[Edge] >>
] >>public class Edge { private double weight; private Vertex startVertex; private Vertex targetVertex; private String extra; public Edge(double weight, Vertex startVertex, Vertex targetVertex, String extra) { this.weight = weight; this.startVertex = startVertex; this.targetVertex = targetVertex; this.extra = extra; } public double getWeight() { return weight; } public void setWeight(double weight) { this.weight = weight; } public Vertex getStartVertex() { return startVertex; } public void setStartVertex(Vertex startVertex) { this.startVertex = startVertex; } public Vertex getTargetVertex() { return targetVertex; } public void setTargetVertex(Vertex targetVertex) { this.targetVertex = targetVertex; } public String getExtra() { return extra; } public void setExtra(String extra) { this.extra = extra; } }
[顶点
] >>import java.util.ArrayList; import java.util.List; public class Vertex implements Comparable<Vertex> { private int ID; private String name; private List<Edge> adjacenciesList; private boolean visited; private Vertex predecessor; private double distance = Double.MAX_VALUE; public Vertex(int ID, String name) { //(Int ID, String name)? this.ID = ID; this.name = name; this.adjacenciesList = new ArrayList<>(); } public void addNeighbour(Edge edge) { this.adjacenciesList.add(edge); } public String getName() { return name; } public void setID(int ID) { this.ID = ID; } public int getID() { return ID; } public void setName(String name) { this.name = name; } public List<Edge> getAdjacenciesList() { return adjacenciesList; } public void setAdjacenciesList(List<Edge> adjacenciesList) { this.adjacenciesList = adjacenciesList; } public boolean isVisited() { return visited; } public void setVisited(boolean visited) { this.visited = visited; } public Vertex getPredecessor() { return predecessor; } public void setPredecessor(Vertex predecessor) { this.predecessor = predecessor; } public double getDistance() { return distance; } public void setDistance(double distance) { this.distance = distance; } @Override public String toString() { return this.name; } @Override public int compareTo(Vertex otherVertex) { return Double.compare(this.distance, otherVertex.getDistance()); } }
[Main
import java.io.BufferedReader; import java.io.File; import java.io.FileNotFoundException; import java.io.FileReader; import java.io.IOException; import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class Main { public static void main(String[] args) throws IOException { //25252 number of elements in Place.txt file Vertex[] vertex = new Vertex[25252]; int indexVertex = 0; //Delimiter used in CSV file final String DELIMITER = ","; String line = ""; //Create the file reader BufferedReader fileReader = new BufferedReader(new FileReader("Place.txt")); String IDString = null; String name = null; int ID = 0; //Read the file line by line while ((line = fileReader.readLine()) != null) { //Get all tokens available in line String[] tokens = line.split(DELIMITER); for(String token : tokens) { IDString = tokens[0]; name = tokens[1]; ID = Integer.parseInt(IDString); } vertex[indexVertex] = new Vertex(ID,name); //System.out.println(indexVertex +":" + vertex[indexVertex].getID()); indexVertex++; } //127807 number of elements in Road.txt file Edge[] edge = new Edge[127807]; int indexEdge = 0; String line2 = ""; BufferedReader fileReader2 = new BufferedReader(new FileReader("Road.txt")); String valueString = null; String vertex1IDName = null; String vertex2IDName = null; String extra = null; float value = 0; int vertex1ID = 0; int vertex2ID = 0; //Read the file line by line while ((line2 = fileReader2.readLine()) != null) { //Get all tokens available in line String[] tokens2 = line2.split(DELIMITER); for(String token1 : tokens2) { vertex1IDName = tokens2[0]; vertex2IDName = tokens2[1]; valueString = tokens2[2]; if(tokens2.length - 1 == 3) { extra = tokens2[tokens2.length - 1]; } else { extra = ""; } vertex1ID = Integer.parseInt(vertex1IDName); vertex2ID = Integer.parseInt(vertex2IDName); value = Float.parseFloat(valueString); } //System.out.println("value: "+ value + " vertex1ID:"+ vertex1ID +" vertex2ID:"+ vertex2ID+ " extra:" + extra); //if vertex 1 name or vertex 2 name in vertex.getID() for(int i = 0; i< indexVertex; i++) { if(vertex1ID == vertex[i].getID() || vertex2ID == vertex[i].getID()){ for(int j = 0; j< indexVertex; j++) { if(vertex2ID == vertex[j].getID() || vertex1ID == vertex[j].getID()) { vertex[i].addNeighbour(edge[indexEdge] = new Edge(value,vertex[i],vertex[j],extra)); //System.out.println("Edge added: "+ vertex1ID +" = " + vertex[i].getID() + " "+ vertex2ID + " = " + vertex[j].getID()); indexEdge++; } } } } } Scanner scanUserInput = new Scanner(System.in); System.out.println("Enter the Source Name:"); String sourceName = scanUserInput.nextLine(); System.out.println("Enter the Destination Name:"); String destinationName = scanUserInput.nextLine(); scanUserInput.close(); Vertex Source = new Vertex(0, null); Vertex Destination = new Vertex(0,null); for(int i = 0; i<indexVertex; i++) { if(sourceName.equals(vertex[i].getName())){ Source.setID(vertex[i].getID()); Source.setName(vertex[i].getName()); } else if(destinationName.equals(vertex[i].getName())){ Destination.setID(vertex[i].getID()); Destination.setName(vertex[i].getName()); } } DijkstraShortestPath shortestPath = new DijkstraShortestPath(); shortestPath.computeShortestPaths(Source); //print out all info List<Vertex> path = new ArrayList<>(); path = shortestPath.getShortestPathTo(Destination); //print Vertex info for(int i = 0; i<path.size(); i++ ) { System.out.println("ID:"+ path.get(i).getID() + " Name:" + path.get(i).getName()); } //print Edge info??? //System.out.println("Shortest Path is: " + shortestPath.getShortestPathTo(Destination)); System.out.println("Minimum distance: "+Destination.getDistance()); } }
[输出
] >>ID:xxxxxx名称:DestinationName最小距离:1.7976931348623157E308
当前,仅最终顶点被打印,最小距离似乎等于无穷大。我似乎找不到问题所在,因为没有将顶点添加到“最短路径”中...
关于如何考虑重组代码以使其更易于调试,我有一些建议:
Graph
类,其中包含所有顶点和边集,并且仅公开用于询问图形的方法。您应该能够独立于测试最短路径算法而进行单元测试,以确保输入后即可按预期设置图形。ShortestPath
类内-无需在类外公开它。您应该能够独立于代码来进行单元测试以读取图形main
方法中的大多数逻辑应该在单独的类中,例如GraphReader
-这些应该是可单元测试的我建议您进行那些更改-我有信心以此方式重组代码将使问题更加明显。
这里是一种可能的设计,可以给您一些我在说什么的想法。
class Vertex {
private final int id;
private final String name;
}
class Edge {
private final Vertex vertex1;
private final Vertex vertex2;
private final double weight;
}
class Graph {
private final Set<Vertex> vertices;
private final Set<Edge> edges;
public void addVertex(int id, String name) {...}
public void addEdge(int vertex1, int vertex2, double weight) {...}
}
class GraphReader {
public Graph readFromStream(InputStream input) {...}
}
class Path {
private final List<Vertex> steps;
}
class ShortestPathFinder {
public Optional<Path> findShortestPath(Graph graph) {...}
}
public static void main(String[] args) {
GraphReader graphReader = new Graph();
Graph graph = graphReader.readFromStream(System.in);
ShortestPathFinder finder = new ShortestPathFinder();
Optional<Path> possiblePath = finder.findShortestPath(graph);
if (possiblePath.isPresent())
System.out.println("Shortest path " + possiblePath.get());
}
关于如何考虑重组代码以使其更易于调试,我有一些建议: