java - Java 中的 Dijkstra 算法

Question

我正在编写一个程序，它必须打印出图中每个节点之间的最短距离。它还需要打印出最后一跳(为获得最短路径而经过的一跳)。很难弄清楚如何找到前一个节点。下面是代码:

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;
    }
}

Answer 1

您可以使用库，而不是创建自己的类:

http://jgrapht.org/javadoc/org/jgrapht/alg/DijkstraShortestPath.html