所以我有这个 GraphUtility 类，它可以处理我正在创建的图形系统的所有输入。我的问题是 dijkstra 方法没有按照我希望的方式工作。我确信我的文件读取工作正常，因为它适用于广度优先搜索。
/**
* GraphUtility class
*/
public class GraphUtility {
// Class variable
private Graph graph;
/**
* Default constructor for class
*/
public GraphUtility() {
graph = null;
}
/**
* Getter for graph
* @return graph
*/
public Graph getGraph() {
return graph;
}
/**
* Setter for graph
* @param graph
*/
public void setGraph(Graph graph) {
this.graph = graph;
}
/**
* TODO: Documentation
* @param file given file path
* @throws Exception if error or exception occurs
*/
public void readFile(File file) throws Exception {
try (BufferedReader br = new BufferedReader(new FileReader(file))) {
graph = new Graph();
String line;
int y = 0;
while ((line = br.readLine()) != null) {
String[] tokens = line.split(",");
populateVertices(tokens.length);
for (int x = 0; x < tokens.length; x++) {
int weight = Integer.parseInt(tokens[x].trim());
if (weight != 0) {
Vertex sourceVertex = graph.getNodes().get(y);
Vertex destinationVertex = graph.getNodes().get(x);
graph.addEdge(sourceVertex, destinationVertex, weight);
}
}
y++;
}
} catch (Exception e) {
e.printStackTrace();
throw new Exception("Error reading the file.");
}
}
private void populateVertices(int verticesCount) {
if (graph != null) {
List<Vertex> vertices = new ArrayList<>();
String labels = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
char symbol;
for (int i = 0; i < verticesCount; i++) {
symbol = labels.charAt(i);
Vertex vertex = new Vertex(String.valueOf(symbol));
vertex.setId(i); // Assign unique ID to each vertex
vertices.add(vertex);
graph.addVertex(vertex);
}
graph.setNodes(vertices);
} else {
graph = new Graph();
}
}
public static double[] dijkstra(Graph graph, Vertex source) {
double[] distance = new double[graph.getNodes().size()];
boolean[] visited = new boolean[graph.getNodes().size()];
// Initialize distances
Arrays.fill(distance, Integer.MAX_VALUE);
distance[source.getId()] = 0;
// Use PriorityQueue to efficiently get the minimum distance vertex
PriorityQueue<VertexDistancePair> pq = new PriorityQueue<>();
pq.add(new VertexDistancePair(source, 0));
while (!pq.isEmpty()) {
VertexDistancePair currentPair = pq.poll();
Vertex currentVertex = currentPair.getVertex();
if (!visited[currentVertex.getId()]) {
visited[currentVertex.getId()] = true;
for (Edge neighbor : currentVertex.getNeighbors()) {
int neighborIndex = neighbor.getEnd().getId();
if (!visited[neighborIndex]) {
double newDist = distance[currentVertex.getId()] + neighbor.getWeight();
if (newDist < distance[neighborIndex]) {
distance[neighborIndex] = newDist;
pq.add(new VertexDistancePair(neighbor.getEnd(), (int) newDist));
}
}
}
}
}
// Add this inside your dijkstra method before the return statement
System.out.println("Debug Output:");
System.out.println("Vertex IDs: " + Arrays.toString(graph.getNodes().stream().map(Vertex::getId).toArray()));
System.out.println("Edge Weights: " + graph.getEdges().stream().map(Edge::getWeight).collect(Collectors.toList()));
System.out.println("Distances: " + Arrays.toString(distance));
return distance;
}
}
class VertexDistancePair implements Comparable<VertexDistancePair> {
private Vertex vertex;
private int distance;
public VertexDistancePair(Vertex vertex, int distance) {
this.vertex = vertex;
this.distance = distance;
}
public Vertex getVertex() {
return vertex;
}
public int getDistance() {
return distance;
}
@Override
public int compareTo(VertexDistancePair other) {
return Double.compare(this.distance, other.distance);
}
}
这是我的顶点类
public class Vertex{
//Class variables
private String label;
private List<Edge> neighbors;
private int id;
public Vertex() {
label = "";
neighbors = null;
}
public Vertex(String label) {
this.label = label;
this.neighbors = new ArrayList<>();
}
public Vertex(String label, List<Edge> neighbors) {
this.label = label;
this.neighbors = neighbors;
}
public void setLabel(String label) {
this.label = label;
}
public void setNeighbors(List<Edge> neighbors) {
this.neighbors = neighbors;
}
public String getLabel() {
return label;
}
public List<Edge> getNeighbors() {
return neighbors;
}
public String toString() {
return label;
}
public boolean equals(Object obj) {
if (this == obj) {
return true;
}
if (obj == null || getClass() != obj.getClass()) {
return false;
}
Vertex otherVertex = (Vertex) obj;
return label.equals(otherVertex.label);
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
}
这是我的边缘课程
public class Edge {
// Class Variables
private Vertex start;
private Vertex end;
private int weight;
private int id;
/**
* Default Constructor
*/
public Edge() {
start = null;
end = null;
weight = 0;
id = 0;
}
/**
* Constructor for edge without weight
* @param start : vertex
* @param end : vertex
*/
public Edge(Vertex start, Vertex end) {
this.start = start;
this.end = end;
this.weight = 0;
id = 0;
}
/**
* Constructor for edge with weight
* @param start
* @param end
* @param weight
*/
public Edge(Vertex start, Vertex end, int weight) {
this.start = start;
this.end = end;
this.weight = weight;
}
/**
* Setter for start vertex
* @param start : Vertex
*/
public void setStart(Vertex start) {
this.start = start;
}
/**
* Setter for end vertex
* @param end : Vertex
*/
public void setEnd(Vertex end) {
this.end = end;
}
/**
* Setter for weight of edge
* @param weight : double
*/
public void setWeight(int weight) {
this.weight = weight;
}
/**
* Setter for ID
* @param id : id
*/
public void setId(int id) {
this.id = id;
}
/**
* Getter for start
* @return : Vertex
*/
public Vertex getStart() {
return start;
}
/**
* Getter for end
* @return : Vertex
*/
public Vertex getEnd() {
return end;
}
/**
* Getter for weight
* @return : weight
*/
public double getWeight() {
return weight;
}
/**
* Getter for id
* @return id
*/
public int getId() {
return id;
}
/**
* toString method
* @return string representation
*/
public String toString() {
return "(" + start + "," + end + ")";
}
}
这是我的图表课
public class Graph {
//Class variables
private List<Vertex> nodes; // nodes are a list of vertices
private List<Edge> edges;
private int count;
/**
* Default Constructor
*/
public Graph() {
nodes = new ArrayList<>();
edges = new ArrayList<>();
count = 0;
}
/**
* Constructor
* @param nodes : List<Vertex
* @param count : int
*/
public Graph(List<Vertex> nodes, int count) {
this.nodes = nodes;
this.count = count;
}
/**
* Method to add a vertex
* @param vertex : Vertex
*/
public void addVertex(Vertex vertex) {
if (!nodes.contains(vertex)) {
this.nodes.add(vertex);
this.count++;
}
}
/**
* Method to add edge
* @param start : Vertex
* @param end : Vertex
*/
public void addEdge(Vertex start, Vertex end) {
edges.add(new Edge(start, end));
}
public void addEdge(Vertex start, Vertex end, int weight) {
edges.add(new Edge(start, end,weight));
}
/**
* Setter to set nodes
* @param nodes : List<Vertex
*/
public void setNodes(List<Vertex> nodes) {
this.nodes = nodes;
}
/**
* Setter to set edges
* @param edges : List<Edge
*/
public void setEdges(List<Edge> edges) {
this.edges = edges;
}
/**
* Setter to set count
* @param count
*/
public void setCount(int count) {
this.count = count;
}
/**
* Getter to get nodes
* @return
*/
public List<Vertex> getNodes() {
return nodes;
}
/**
* Getter to get edges
*/
public List<Edge> getEdges() {
return edges;
}
/**
* Getter for count
* @return
*/
public int getCount() {
return count;
}
/**
* toString method
* @return string representation
*/
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("V={");
for (Vertex vertex : this.nodes) {
sb.append(vertex + ",");
}
sb.append("}\n");
sb.append("E={");
for (Edge edge : this.edges) {
sb.append(edge + ",");
}
sb.append("}");
return sb.toString();
}
}
这是我创建 GraphUtility 类对象以及尝试调用 dijkstra 方法的地方。
public class Test {
public static void main(String[] args) {
// Instantiate GraphUtility and read graph from file
GraphUtility graphUtility = new GraphUtility();
try {
File file = new File("graphs/weighted-directed-matrix"); // Replace with your file path
graphUtility.readFile(file);
} catch (Exception e) {
e.printStackTrace();
return;
}
// Get the graph from GraphUtility
Graph graph = graphUtility.getGraph();
// Choose a source vertex (you can change this as needed)
Vertex source = graph.getNodes().get(0);
// Dijkstra's algorithm
double[] distance = dijkstra(graph, graph.getNodes().get(0));
// Printing results
for (int i = 0; i < graph.getNodes().size(); i++) {
String vertexLabel = graph.getNodes().get(i).getLabel();
String distanceString = (distance[i] == Integer.MAX_VALUE) ? "Unreachable" : String.valueOf(distance[i]);
System.out.println("Vertex: " + vertexLabel + " & Distance from Source: " + distanceString);
}
}
}
文件“graphs/weighted-directed-matrix”的内容包括：
2,2,2,4,2
4,5,1,3,4
1,2,3,3,5
3,5,5,6,5
3,5,3,4,5
这是我的输出：
Debug Output:
Vertex IDs: [0, 1, 2, 3, 4]
Edge Weights: [2.0, 2.0, 2.0, 4.0, 2.0, 4.0, 5.0, 1.0, 3.0, 4.0, 1.0, 2.0, 3.0, 3.0, 5.0, 3.0, 5.0, 5.0, 6.0, 5.0, 3.0, 5.0, 3.0, 4.0, 5.0]
Distances: [0.0, 2.147483647E9, 2.147483647E9, 2.147483647E9, 2.147483647E9]
Vertex: A & Distance from Source: 0.0
Vertex: B & Distance from Source: Unreachable
Vertex: C & Distance from Source: Unreachable
Vertex: D & Distance from Source: Unreachable
Vertex: E & Distance from Source: Unreachable
我不明白为什么我与 B、C、D 和 E 源的距离显示无法到达。此外，我希望实现一个系统，在该系统中，我可以将结束顶点与起始顶点一起传递给 dijkstra 方法，并让我的代码仅输出从起始顶点到结束顶点的行进路径。我该如何解决我的问题并实现此功能。我一整天都在研究这个问题，但我无法弄清楚我所提供的代码中问题出在哪里。我知道这个问题是在另一篇文章中使用另一种方法回答的，但我真的很想知道我自己的代码哪里出了问题。
有两个问题：
您的
dijkstra for (Edge neighbor : currentVertex.getNeighbors())
...但是
getNeighbors()要解决此问题，请将以下方法添加到
Vertex public void addEdge(Edge edge) {
this.neighbors.add(edge);
}
接下来，从
addEdgeGraph public void addEdge(Vertex start, Vertex end, int weight) {
Edge edge = new Edge(start, end, weight);
edges.add(edge);
start.addEdge(edge); // <--- calling the newly added method
}
在
GraphUtilityreadFilepopulateVerticesgraph.nodesgraph.nodesgraph.edgesgraph.nodes 中的节点要纠正此问题，请确保在您尚未注册时仅拨打
populateVertices所以改变这个：
populateVertices(tokens.length);
至：
if (graph.getCount() == 0) {
populateVertices(tokens.length);
}
通过这两个修复，它应该可以工作。