1
Я пишу программу, которая должна распечатать кратчайшее расстояние между каждым узлом графика. Он также должен распечатать последний прыжок (прыжок он прошел, чтобы получить кратчайший путь). Нелегко понять, как найти предыдущий узел. Вот код ниже:Djkstras Algorithm in Java
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;
}
}