我正在编写一个程序,该程序必须打印出图中每个节点之间的最短距离。它还需要打印出最后一跳(经过该跳以获取最短路径)。很难确定如何找到上一个节点。这是下面的代码:
public class Graph {
private Node[] nodes;
public Node[] getNodes() {
return nodes;
}
private int noOfNodes;
public int getNoOfNodes() {
return noOfNodes;
}
private Edge[] edges;
public Edge[] getEdges() {
return edges;
}
private int noOfEdges;
public int getNoOfEdges() {
return noOfEdges;
}
/**
* Constructor that builds the whole graph from an Array of Edges
*/
public Graph(Edge[] edges){
// The edges are passed in, so store them
this.edges = edges;
// Create all the nodes, ready to be updated with the edges
this.noOfNodes = calculateNoOfNodes(edges);
this.nodes = new Node[this.noOfNodes];
for (int n = 0; n < this.noOfNodes; n++) {
this.nodes[n] = new Node();
}
// Add all the edges to the nodes. Each edge is added to 2 nodes (the "to" and the "from")
this.noOfEdges = edges.length;
//while(edges.length-1 < edges.length){
for (int edgeToAdd = 0; edgeToAdd < this.noOfEdges; edgeToAdd++) {
this.nodes[edges[edgeToAdd].getFromNodeIndex()].getEdges().add(edges[edgeToAdd]);
this.nodes[edges[edgeToAdd].getToNodeIndex()].getEdges().add(edges[edgeToAdd]);
}
// }
}
/**
* Calculate the number of nodes in an array of edges
*
* @param edges An array of edges that represents the graph.
* @return The number of nodes in the graph.
*
*/
private int calculateNoOfNodes(Edge[] edges) {
int noOfNodes = 0;
for (Edge e:edges ) {
// if(e != null){
if (e.getToNodeIndex() > noOfNodes) noOfNodes = e.getToNodeIndex();
if (e.getFromNodeIndex() > noOfNodes) noOfNodes = e.getFromNodeIndex();
// }
}
noOfNodes++;
return noOfNodes;
}
//private int [] hopNode;
private int hop;
/**
* Uses Dijkstra's algorithm to calculate the shortest distance from the source to all nodes
*
*/
public void calculateShortestDistances(){
// Set node 2 as the source
this.nodes[2].setDistanceFromSource(0); // sorce based on 2
int nextNode = 2; // set
// Visit every node, in order of stored distance
for (int i = 0; i < this.nodes.length; i++) {
System.out.println("i:" + i);
// Loop round the edges that are joined to the current node
ArrayList<Edge> currentNodeEdges = this.nodes[nextNode].getEdges();
System.out.println ( "currentNodeEdges: " + currentNodeEdges.toString());
for (int joinedEdge = 0; joinedEdge < currentNodeEdges.size(); joinedEdge++) {
// Determine the joined edge neighbor of the current node
int neighborIndex = currentNodeEdges.get(joinedEdge).getneighborIndex(nextNode);
System.out.println(" neighborIndex: " + neighborIndex);
// Only interested in an unvisited neighbor
if (!this.nodes[neighborIndex].isVisited()) {
// Calculate the tentative distance for the neighbor
int tentative = this.nodes[nextNode].getDistanceFromSource() + currentNodeEdges.get(joinedEdge).getLength();
// Overwrite if the tentative distance is less than what's currently stored
if (tentative < nodes[neighborIndex].getDistanceFromSource()) {
nodes[neighborIndex].setDistanceFromSource(tentative);
//System.out.println ("tentative: "+tentative);
// hop= currentNodeEdges.get(tentative).getneighborIndex(nextNode);
//System.out.println("hop:" +hop);
}
}
//System.out.println("neighborIndex[joinedEdge]:"+neighborIndex);
}
//hopNode[i] = neighborIndex;
// All neighbors are checked so this node is now visited
nodes[nextNode].setVisited(true);
// neighbors[i] = neighborIndex;
// The next node to visit must be the one with the shortest distance.
nextNode = getNodeShortestDistanced();
hop= nextNode;
System.out.println(hop);
}
}
/**
* Scans the unvisited nodes and calculates which one has the shortest distance from the source.
*
* @return The index of the node with the smallest distance
*/
private int getNodeShortestDistanced() {
int storedNodeIndex = 0;
int storedDist = Integer.MAX_VALUE;
for (int i = 0; i < this.nodes.length; i++) {
int currentDist = this.nodes[i].getDistanceFromSource();
if (!this.nodes[i].isVisited() && currentDist < storedDist) {
storedDist = currentDist;
storedNodeIndex = i;
}
}
return storedNodeIndex;
}
//public int findNeighbor(int node){
// int hop;
// hop = getneighborIndex(node);
//return hop;
//}
/**
* Overrides Object.toString() to show the contents of the graph
*
*/
public String toString() {
String output = "Number of nodes = " + this.noOfNodes;
output += "\nNumber of edges = " + this.noOfEdges;
int sourceNode = 2;
for (int i = 0; i < this.nodes.length; i++) {
output += ("\nThe shortest distance from node "+ sourceNode + " to node " + i + " is " + nodes[i].getDistanceFromSource() +" and the hop is "+ hop+ "." ); //" and the hop node is "+hop+ "." );
}
return output;
}
}
最佳答案
您可以使用一个库,而不是创建自己的类:
http://jgrapht.org/javadoc/org/jgrapht/alg/DijkstraShortestPath.html
关于java - Java中Dijkstra的算法,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/37062405/