Dijkstra Algorithmus Hilfe!!

dijkstra2000

Mitglied
Hey, ich bräuchte schnelle Hilfe zu meinem Algorithmus.

Ich habe mehrere Klassen, darunter eine Klasse Graph, einer Liste, Knoten und Kanten. Alle jeweils mit Methoden.
Dazu habe ich jetzt noch die Klasse Klasse erstellt.

Wie kann ich den schnellsten Weg von einem Knoten zu einem bestimmten Knoten finden? Hier meine Lösungsansatz:


private Graph Klassengraph;


public Klasse()
{


Klassengraph = new Graph();


Vertex test1 = new Vertex("Test1");
klassengraph.addVertex(test1);

Vertex test2 = new Vertex("Test2");
klassengraph.addVertex(test2);



Edge k1 = new Edge(test1,test2,4);
//Stellt euch noch andere Knoten und Kanten vor

}

public Vertex kürzesteEntfernung(String pName1)
{
Vertex name1 = klassengraph.getVertex(pName1);
List<Edge> nachbar = klassengraph.getEdges(name1);
nachbar.toFirst();
double minimum = nachbar.getContent().getWeight();

while(nachbar.hasAccess())
{

}
}
 

EinNickname9

Bekanntes Mitglied
Wir machen selbstverständlich KEINE Hausaufgaben, aber können bei konkreten Fragen weiterhelfen.

Du hast also eine Adjazenzliste, keine -Matrix, sehe ich das richtig? Dann könnte es frickelig werden, weil Du ja jeden Nachfolger brauchst: https://www.geeksforgeeks.org/dijkstras-algorithm-for-adjacency-list-representation-greedy-algo-8/

Ich würde sagen, fang erstmal hier an zu lesen: https://de.wikipedia.org/wiki/Dijkstra-Algorithmus#Algorithmus_in_Pseudocode

und bei konkreten Fragen meldest Du Dich nochmal. Einfach sagen: "Macht mal!", funktioniert so nicht.
 

dijkstra2000

Mitglied
Wir machen selbstverständlich KEINE Hausaufgaben, aber können bei konkreten Fragen weiterhelfen.

Du hast also eine Adjazenzliste, keine -Matrix, sehe ich das richtig? Dann könnte es frickelig werden, weil Du ja jeden Nachfolger brauchst: https://www.geeksforgeeks.org/dijkstras-algorithm-for-adjacency-list-representation-greedy-algo-8/

Ich würde sagen, fang erstmal hier an zu lesen: https://de.wikipedia.org/wiki/Dijkstra-Algorithmus#Algorithmus_in_Pseudocode

und bei konkreten Fragen meldest Du Dich nochmal. Einfach sagen: "Macht mal!", funktioniert so nicht.
Danke für deine Nachricht inkl. der Hilfen, auch wenn das meiste nur Links sind. Und recherchieren könnte ich auch selbst.

Also eine Hausaufgabe ist das eher weniger. Aber das macht nichts.
"Macht mal!" habe ich ebenfalls nicht erwähnt. Ich habe nur gesagt, dass ich nicht weiterkomme und somit Hilfe benötige. Ob das jetzt nur ein Tipp sein soll oder direkt die komplette Lösung ist, kann jeder selbst entscheiden und dann kommentieren. Das wichtigste ist, dass ich das, wie das Programm abläuft und was es macht, verstehen möchte. Allerdings will ich nicht zu viel Zeit mit recherchieren vergeuden, das hat so einige Gründe. Deshalb dachte ich mir, hier im Java Forum sind einige kompetente Leute die mir das schnell, super einfach erklären können.
 

mihe7

Top Contributor
Naja, die Frage ist halt, was Du erklärt haben willst. Den "schnellsten Weg" (wie ist der definiert?) zwischen zwei Knoten kannst Du per Dijkstra oder A* ermitteln.
 

dijkstra2000

Mitglied
Naja, die Frage ist halt, was Du erklärt haben willst. Den "schnellsten Weg" (wie ist der definiert?) zwischen zwei Knoten kannst Du per Dijkstra oder A* ermitteln.
Jede Verbindung (also Kante) hat ein Gewicht. Der schnellste Weg ist also: Kleinste Summe der Gewichte der Kanten.

test1 ist der Anfangsknoten. test2 gibt man als Parameter ein. Dann müsste der Algorithmus doch irgendwie alle Kanten berücksichtigen die zu test2 hingehen. Aber irgendwie macht das kein Sinn, weil ja auch andere Knoten dazwischen sein können...
 

dijkstra2000

Mitglied
Warum machst du es dann nicht, anstatt hier eine Komplettlösung anzufordern? Man bräuchte mehr Informationen über den Graphen und wie dieser hinterlegt ist... Und A* ist auch nicht schlecht.
Deinen ersten Satz habe ich bereits beantwortet:
1. "Allerdings will ich nicht zu viel Zeit mit recherchieren vergeuden, das hat so einige [private] Gründe"
2. "Ob das jetzt nur ein Tipp sein soll oder direkt die komplette Lösung ist, kann jeder selbst entscheiden und dann kommentieren."

Ja ich habe den Konstruktor mit reingeschrieben. Ich hoffe das reicht um sich den Graphen vorzustellen?

A* ist bestimmt gut. Aber ich habe in letzter Zeit so viele Algorithmen und sonst was kennengeleiteten, da verliere ich den Überblick was für was ist...
 

mihe7

Top Contributor
Jede Verbindung (also Kante) hat ein Gewicht. Der schnellste Weg ist also: Kleinste Summe der Gewichte der Kanten.
OK, nachdem ich da keinen Ansatz für eine Heuristik sehe, fällt A* schon mal flach. Dann konzentrieren wir uns mal auf Dijkstra.

Aber irgendwie macht das kein Sinn, weil ja auch andere Knoten dazwischen sein können...
Doch, genau darum geht es. Der Algorithmus ist im Wiki-Link von @eineNick bestens beschrieben. Es wäre jetzt irgendwie schwachsinnig, das jetzt alles hier zu wiederholen.

Im Prinzip lässt sich das 1:1 umsetzen, wenn Du https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/PriorityQueue.html verwendest.
 

EinNickname9

Bekanntes Mitglied
@dijkstra2000 Fang doch mal an zu lesen, anstatt hier eine Lösung erschleichen zu wollen...


A* is basically an informed variation of Dijkstra.
A* is considered a "best first search" because it greedily chooses which vertex to explore next, according to the value of f(v) [f(v) = h(v) + g(v)] - where h is the heuristic and g is the cost so far.

Note that if you use a non informative heuristic function: h(v) = 0 for each v: you get that A* chooses which vertex to develop next according to the "so far cost" (g(v)) only, same as Dijkstra's algorithm - so if h(v) = 0, A* defaults to Dijkstra's Algorithm.
...
A* is both complete (finds a path if one exists) and optimal (always finds the shortest path) if you use an Admissible heuristic function. If your function is not admissible - all bets are off.
...
h(n): approximate cost from node n to goal node. It is a heuristic function. This heuristic function should never overestimate the cost. That means, the real cost to reach goal node from node n should be greater than or equal h(n). It is called admissible heuristic.

Das soll Folgendes bedeuten: Fällt die Luftlinienheuristik flach, weil es, wie du beschreibst @mihe7 , eine kostengünstigere Verbindung zwischen zwei Knoten geben kann als die Luftlinie und sich die Luftlinienheuristik damit überschätzt, fällt auch A* flach...

Das heißt konkret, dass du den Algorithmus einfach so wie auf Wikipedia beschrieben mit einer PQ umsetzen kannst... Gute Nacht. :)
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
U Meinung zum Dijkstra Algorithmus Java Basics - Anfänger-Themen 6
U Dijkstra Algorithmus Laufzeit Java Basics - Anfänger-Themen 3
M Dijkstra Algorithmus in Graphen auf mehrere verschiedene Knoten anwenden lassen Java Basics - Anfänger-Themen 11
S Dijkstra Algorithmus funktioniert nicht Java Basics - Anfänger-Themen 4
S GraphNode --- Dijkstra Algorithmus : NullPointerException Java Basics - Anfänger-Themen 1
B PriorityQueue im dijkstra Algorithmus implementieren Java Basics - Anfänger-Themen 4
S Dijkstra-Algoritmus Java Basics - Anfänger-Themen 7
Binary.Coder Tipp für Ein-/Ausgabe für Dijkstra Java Basics - Anfänger-Themen 6
K Dijkstra implementierung 2.0 Java Basics - Anfänger-Themen 19
T Dijkstra auf adjazenzmatrix Java Basics - Anfänger-Themen 7
laxla123 Eigenschaften eines Algorithmus (determiniert vs.. deterministisch) Java Basics - Anfänger-Themen 2
C Gewinnspiel erstellen mit Algorithmus Java Basics - Anfänger-Themen 3
C negamax-Algorithmus für Tic-Tac-Toe spielt manchmal falsch Java Basics - Anfänger-Themen 10
H Minimax Algorithmus in Tic Tac Toe Java Basics - Anfänger-Themen 3
M Minimax-Algorithmus für Vier gewinnt Java Basics - Anfänger-Themen 11
ohneInformatik; Trockentest Algorithmus, mathematischen Zusammenhang angeben Java Basics - Anfänger-Themen 3
M Minimax-Algorithmus Java Basics - Anfänger-Themen 17
mervanpolat Binary Search Algorithmus ausführen Java Basics - Anfänger-Themen 1
J Rekursiver Algorithmus Java Basics - Anfänger-Themen 9
M monte carlo Algorithmus für 4 gewinnt Java Basics - Anfänger-Themen 12
izoards Sortier Algorithmus für Bounding Box Elememte Links nach Rechts und von Oben nach Unten Java Basics - Anfänger-Themen 33
S Algorithmus entwicklen, der zu einem gegebenen Datum die Jahreszeit ermittelt Java Basics - Anfänger-Themen 13
rosima26 Merge-Algorithmus Java Basics - Anfänger-Themen 53
C Ein Algorithmus soll schneller werden Java Basics - Anfänger-Themen 24
U Den Kuchen aufteilen - aber wie? (Rebalancing-Algorithmus) Java Basics - Anfänger-Themen 14
s_1895 Pseudocode Naiver Algorithmus Java Basics - Anfänger-Themen 17
H String verschlüsseln - eigener Algorithmus Java Basics - Anfänger-Themen 104
T Algorithmus für Index mit min-Wert Java Basics - Anfänger-Themen 2
Düsseldorf2002 Testen meines Algorithmus Java Basics - Anfänger-Themen 1
D Primzahlen Rechner nach Eratostenes von Kyrene Algorithmus Java Basics - Anfänger-Themen 2
KogoroMori21 Frage zum Euklidischen Algorithmus Java Basics - Anfänger-Themen 11
S Algorithmus java searchAll IKey Java Basics - Anfänger-Themen 4
S Algorithmus Datensätze einfügen wenn... Java Basics - Anfänger-Themen 26
KogoroMori21 MergeSort Algorithmus Java Basics - Anfänger-Themen 2
KogoroMori21 Textdatei einlesen im Array (Selection Sort Algorithmus) Java Basics - Anfänger-Themen 3
fendix Compiler-Fehler Algorithmus zur Bestimmung von Primzahlen Java Basics - Anfänger-Themen 7
S Algorithmus (reelle Zahl <65536 von dezimal zu dual) max. 10 Nachkommastellen Java Basics - Anfänger-Themen 4
G Algorithmus Graphen Java Basics - Anfänger-Themen 10
D Input/Output fehlerhafter Algorithmus zum Ersetzen von Array-Werten nach logischem Schema Java Basics - Anfänger-Themen 1
N Selection Algorithmus: Methode wird nicht erkannt (BlueJ) Java Basics - Anfänger-Themen 3
L Math.exp also eigenen Algorithmus Java Basics - Anfänger-Themen 2
Kirby.exe Algorithmus entwickeln Java Basics - Anfänger-Themen 37
M Algorithmus Max-Heap? Java Basics - Anfänger-Themen 3
I Labyrinth auf der Basis eines rekursiven Algorithmus Java Basics - Anfänger-Themen 27
CptK Best Practice Algorithmus nach jedem Schritt zum Visualisieren pausieren Java Basics - Anfänger-Themen 3
A Algorithmus effizienter machen Java Basics - Anfänger-Themen 1
V Algorithmus zur fortlaufenden Berechnung des duechscjnt Java Basics - Anfänger-Themen 1
O Labyrinth Algorithmus Java Basics - Anfänger-Themen 3
G Quicksort Algorithmus Java Basics - Anfänger-Themen 12
S Binäre-Suche Algorithmus Java Basics - Anfänger-Themen 1
D Algorithmus in Pseudocode mit log2(n) Operationen erstellen Java Basics - Anfänger-Themen 3
C Laufzeit eines Sortier-Algorithmus ermitteln Java Basics - Anfänger-Themen 4
H aufgabe java luhn algorithmus Java Basics - Anfänger-Themen 10
A Datenstruktur für Savings Algorithmus und Planung von kleinen Programmierprojekten Java Basics - Anfänger-Themen 1
J Algorithmus für eine Reihe implementieren Java Basics - Anfänger-Themen 2
N Denksportaufgabe durch Algorithmus lösen Java Basics - Anfänger-Themen 2
S Problem mit einem rekursivem FloodFill Algorithmus Java Basics - Anfänger-Themen 62
B Algorithmus Square und Multiply Java Basics - Anfänger-Themen 3
J Algorithmus - Strings auf eigene Reihenfolge miteinander vergleichen Java Basics - Anfänger-Themen 4
D Frage Boyer-Moore Algorithmus Java Basics - Anfänger-Themen 7
M Komplexität Algorithmus Java Basics - Anfänger-Themen 8
H Zeichen im algorithmus Java Basics - Anfänger-Themen 4
B Code Verständnisfragen - FLoyd Warshall Algorithmus Java Basics - Anfänger-Themen 1
B Algorithmus zum entmischen einer Zahlenfolge Java Basics - Anfänger-Themen 15
X Minimax-Algorithmus über alle Kanten möglich? - Kanten darstellen Java Basics - Anfänger-Themen 1
T Algorithmus zur Überprüfung eines binären Suchbaums Java Basics - Anfänger-Themen 2
K Best Practice Algorithmus für Berechnung von Zahlenreihenfolge Java Basics - Anfänger-Themen 12
M Simpler Algorithmus läuft extrem langsam. Java Basics - Anfänger-Themen 3
K Erste Schritte Brute Force Algorithmus Java Basics - Anfänger-Themen 2
L Frage zu BubbleSort Algorithmus Java Basics - Anfänger-Themen 2
B gibt es ein Stundenplan-Algorithmus? Java Basics - Anfänger-Themen 11
O Algorithmus-Problem Java Basics - Anfänger-Themen 5
P Euklidischer Algorithmus Java Basics - Anfänger-Themen 9
L Greates Commong Dividend - euklidischer Algorithmus, modulos not positive Java Basics - Anfänger-Themen 5
J Euklidischer Algorithmus Java Basics - Anfänger-Themen 1
S Quicksort Algorithmus Java Basics - Anfänger-Themen 2
B Rekursive Algorithmus schreiben Java Basics - Anfänger-Themen 8
V Algorithmus in einer Methode ausführen Java Basics - Anfänger-Themen 3
M Implementierung des Knuth-Morris-Pratt-Algorithmus Java Basics - Anfänger-Themen 0
M Dijkstras Algorithmus Java Basics - Anfänger-Themen 5
S Zusammenhang Datenstruktur/Algorithmus Java Basics - Anfänger-Themen 1
M Simulation - Algorithmus Java Basics - Anfänger-Themen 3
F Erste Schritte Hilfe beim Algorithmus finden Java Basics - Anfänger-Themen 8
D Algorithmus für Punkte auf einem Kreis Java Basics - Anfänger-Themen 0
D Algorithmus zu gegebener Laufzeit implementieren Java Basics - Anfänger-Themen 1
B Doppelte Werte aus Array entfernen ohne Import - Algorithmus Java Basics - Anfänger-Themen 5
C Ideen für einen Algorithmus Java Basics - Anfänger-Themen 1
F Best Practice Algorithmus optimieren - Binaeruhr Java Basics - Anfänger-Themen 2
S Euklid Algorithmus zur Berechnung des GGTs Java Basics - Anfänger-Themen 2
L Welcher Algorithmus ist das ? Java Basics - Anfänger-Themen 9
J Rekursiver Horner-Schema-Algorithmus - Verstehe ich ihn richtig? Java Basics - Anfänger-Themen 2
O Java Zufalls-Verteil-Algorithmus Java Basics - Anfänger-Themen 3
P ganz simpler algorithmus Java Basics - Anfänger-Themen 3
C Sortieren ohne Algorithmus Java Basics - Anfänger-Themen 8
J Algorithmus: Grad von floating zu Grad/Minute/Sekunde Java Basics - Anfänger-Themen 3
A Text Verschriebung/Algorithmus(?) Java Basics - Anfänger-Themen 8
R Rekursionsformel für Laufzeit von Algorithmus Java Basics - Anfänger-Themen 3
E Algorithmus für kart. Produkt: als int [] Feld repräsentiert Java Basics - Anfänger-Themen 10
U Peterson Algorithmus Java Basics - Anfänger-Themen 13
algebraiker Collections Bräuchte Hilfe bei dem Algorithmus - LinkedHashMap Java Basics - Anfänger-Themen 2

Ähnliche Java Themen

Neue Themen


Oben