Implementace - Dijkstrův algoritmus – Java – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

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

 

Hledá se programátor! Plat 1 800 € + bonusy (firma Boxmol.com)
Petr Pavlíček
~ Anonymní uživatel
1 příspěvek
10. 5. 2013   #1
-
0
-

 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();
    }}}
Nahlásit jako SPAM
IP: 78.45.24.–
Reklama
Reklama
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 19 hostů

Podobná vlákna

C# implementace ffdshow — založil Jiří

Implementace grafu — založil Ondřej Benda

Implementace Z-Buffer — založil Yimo

Implementace operator[][] — založil cibule

Moderátoři diskuze

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý