Hallo,
hab folgende Aufgabe:
"Implementieren Sie den Dijkstra-Algorithmus in einer Klasse GraphAlgorithms, basierend auf folgender Methodensignatur.
Der Algorithmus von Dijkstra liefert – ausgehend von einem fix gegebenen Startknoten – zu jedem Knoten immer den Vorgängerknoten auf dem kürzesten Pfad zurück zum Startknoten. Daher soll Ihre Methode computePredecessors eine entsprechende Map<Node, Node> zurückliefern, wobei jeder Knoten auf seinen Vorgängerknoten gemappt wird. Diese Information soll in der Methode computeShortestPath verwendet werden, um den kürzesten Pfad zwischen zwei Knoten als Liste von Knoten zu ermitteln.
Erweitern Sie die Klasse GraphAlgorithms um Methoden zur Breitensuche (BFS) und Tiefensuche (DFS), wobei jeweils das Ergebnis als Liste von Knoten in der entsprechenden Reihenfolge dargestellt wird:
"
Zusätzlich sind schon folgende Klassen vorhanden:
Node, Edge, Directed Graph
Steh da grad irgendwie auf dem Schlauch. Wie kennzeiche ich zum Beispiel, dass der Knoten schon besucht wurde?
Könnt ihr mir mit den Methoden weiterhelfen?
Danke
flaco
hab folgende Aufgabe:
"Implementieren Sie den Dijkstra-Algorithmus in einer Klasse GraphAlgorithms, basierend auf folgender Methodensignatur.
Java:
public class GraphAlgorithms {
public static Map<Node, Node> computePredecessors(DirectedGraph graph, Node start);
public static List<Node> computeShortestPath(DirectedGraph graph, Node start, Node destination);
}Der Algorithmus von Dijkstra liefert – ausgehend von einem fix gegebenen Startknoten – zu jedem Knoten immer den Vorgängerknoten auf dem kürzesten Pfad zurück zum Startknoten. Daher soll Ihre Methode computePredecessors eine entsprechende Map<Node, Node> zurückliefern, wobei jeder Knoten auf seinen Vorgängerknoten gemappt wird. Diese Information soll in der Methode computeShortestPath verwendet werden, um den kürzesten Pfad zwischen zwei Knoten als Liste von Knoten zu ermitteln.
Erweitern Sie die Klasse GraphAlgorithms um Methoden zur Breitensuche (BFS) und Tiefensuche (DFS), wobei jeweils das Ergebnis als Liste von Knoten in der entsprechenden Reihenfolge dargestellt wird:
Java:
public static List<Node> DFS(DirectedGraph graph, Node start);
public static List<Node> BFS(DirectedGraph graph, Node start);Zusätzlich sind schon folgende Klassen vorhanden:
Node, Edge, Directed Graph
Steh da grad irgendwie auf dem Schlauch. Wie kennzeiche ich zum Beispiel, dass der Knoten schon besucht wurde?
Könnt ihr mir mit den Methoden weiterhelfen?
Danke
flaco
Zuletzt bearbeitet:
