Implementace - Dijkstrův algoritmus – Java – Fórum – Programujte.com

 Pokouším se implementovat Dijkstrův algoritmus, ale stále nedostávám požadovaný výstup. 

Při použití níže uvedeného kódu dostávám v outputu::

0 3 6 8 2 6 0 3 3 2

3 0 4 2 0 0 1 8 5 5

6 4 0 6 0 9 3 9 7 0

8 2 6 0 5 8 7 8 0 4

2 0 0 5 0 4 5 2 1 0

atd. (do matice 10x10)

Distances from node 1:
Total distance:0. Through nodes: 0
Total distance:0. Through nodes: 1

atd.

public class Dijkstra {

private static int[] predicessors;
private static int[] distance;

/**
 * Dijkstra algorithm to compute shortest distances from startNode to all other nodes.
 *
 * @param graph Graph with the nodes to run Dijkstra on.
 * @param startIndex Index of start node to begin the search.
 */
public static void call(Graph graph, int startIndex) {
int lengthOfMatrix = graph.getItems().length;
distance = new int[lengthOfMatrix]; // shortest known distance from "startIndex"
predicessors = new int[lengthOfMatrix]; // preceeding node in path
distance[startIndex] = 0;
predicessors[startIndex] = startIndex;
int currentIndex;
while ((currentIndex = chooseClosestNode(graph)) != -1) {
    graph.getItems()[currentIndex].setVisited(true);
    for (int neighbour = 0; neighbour < lengthOfMatrix; neighbour++) {
        if (graph.getEdges()[currentIndex][neighbour] > 0) {
            if (!graph.getItems()[neighbour].isVisited()) {
                if (distance[neighbour] > (distance[currentIndex] + graph.getEdges()[currentIndex][neighbour])) {
                    distance[neighbour] = (distance[currentIndex] + graph.getEdges()[currentIndex][neighbour]);
                    predicessors[neighbour] = currentIndex;
                }
            }
        }
    }
}

}
/**
 * Chooses the index of currently closest, not visited node in the graph.
 * 
 * @param graph Graph to be searched.
 * @return Index of the closes node or -1 if all nodes visited
 */
private static int  chooseClosestNode(Graph graph) {
    int minimalDistance = Integer.MAX_VALUE;
    int minimalIndex = -1;
    for (int i = 0; i < graph.getItems().length; i++) {
    if (!graph.getItems()[i].isVisited()) {
        if (minimalDistance > distance[i]) {
            minimalDistance = distance[i];
            minimalIndex = i;
        }
        }
     }
return minimalIndex;
}

/**
 * Prints path from start node (set in call method) to the node from parameter.
 *
 * @param nodeIndex Index of the end node where to print path.
 */
public static void printPath(int nodeIndex) {
    if (distance[nodeIndex] == 0) {
        System.out.print(nodeIndex);
    } else if (distance[nodeIndex] == 1000) {
        System.out.print(" Path doesn´t exists.");
    } else {
        printPath(predicessors[nodeIndex]);
        System.out.print(" -> " + nodeIndex);
    }
}

public static int[] getPredicessors() {
    return predicessors;
}

public static int[] getDistance() {
    return distance;
}

}

Samozřejmě používám další třídy Graph, Item a Main.

public static void main(String[] args) {

    Graph graph = new Graph();
    graph.print();
    System.out.println();

    Dijkstra.call(graph, 6);
    System.out.println("Distances from node 1:");
    for (int i = 0; i < graph.getItems().length; i++) {
        System.out.print(i + ". Total distance:" + Dijkstra.getDistance()[i] + ". Through nodes: ");
        Dijkstra.printPath(i);
        System.out.println();
    }}}