Du verwendest einen veralteten Browser. Es ist möglich, dass diese oder andere Websites nicht korrekt angezeigt werden. Du solltest ein Upgrade durchführen oder ein alternativer Browser verwenden.
wie speichert man eigentlich am sinnvollsten Graphen mit Gewichten ab? Ich habe einen Graphen, in dem von bestimmten Knoten mit unterschiedlicher Gewichtung zu anderen Knoten Verbindungen bestehen.
Meine Idee war es nun, zuerst eine Arrayliste zu erstellen, dann mit einer for-Schleife diese zu durchlaufen und immer die Verbindung einzutragen und dahinter die Gewichtung.
Also beispielsweise für ArrayListe[1]:
2 1 4 2
Dies würde dann bedeuten, dass von Knoten 1 eine Verbindung zu 2 besteht mit Gewicht 1. Ebenso besteht eine Verbindung von Knoten 1 zu Knoten 4 mit Gewicht 2.
Das klingt fast so, als ob nicht deine Knoten ("nodes").... sondern deine Verbindungen (man nennt sie normalerweise "Kanten"/"edges") gewichtet wären (man sagt auch "mit Kosten versehen wären").
Was ist nun der Fall? Sind deine Knoten oder Kanten gewichtet?
Die Repräsentation eines Graphen hängt stark davon ab, wie dieser Graph aussieht und was du damit vor hast. Das geht aus deiner Frage nicht wirklich hervor. Aber eine gängige Methode ist es, für Vertices und Edges eigene Klasse zu erstellen:
Java:
class Edge {
Vertex target;
double weight;
...
}
Java:
class Vertex {
List<Edge> connections;
...
}
Das hat den Vorteil, dass du deinen Edges/Vertices noch wesentlich mehr Informationen mitgeben kannst.
Um konkret zu werden:
Ich möchte den Dijkstras Algorithmus in Java implementieren. Zunächst sind also meine Kanten gewichtet. Knoten hatte ich vor zusätzlich noch zu initiailsieren.
Wie weit bist du nun schon gekommen? Falls du NOCH NICHT angefangen hast, nimm dir den Tipp von Sesostris zu Herzen und implementiere alle Objekte die in einem Graphen vorkommen korrekt!
Also erstelle eine Klasse für Kanten, eine Klasse für Knoten, eine Klasse für einen Graphen vielleicht sogar.
Dann kannst du für Dijsktra auch noch eine Klasse "Heap" definieren, die eine sortierte Liste führt, mit Knoten, die noch "überarbeitet" werden müssen. Von dieser Liste greifst du dann später für Dijkstra immer das erste element aus der Liste (das ist der Knoten, mit dem nächstkleinsten Abstand), löscht es aus der Liste und rufst den Dijkstra-Algorithmus darauf rekursiv auf...
D.h. deine ArrayListe (erster Post) ist keine so gut idee, stattdessen versehe auch deien Klassen (wie oben genannt) mit Attributen wie "int id" und bei:
* Knoten: List<Integer> edgeIds // Liste der Kanten an einem Knoten
* Kanten: int sourceNode // QuellKnoten
int targetNode // Zielknoten
und google wird dir sicher auch noch Helfen zumindest mal einen Ansatz zu machen und hier zu posten!
Na ja, habe jetzt schon angefangen und möchte es mit der ArrayList zu Ende machen.
Kleine Zwischenfrage noch:
Wie kann man denn am einfachsten das Minimum der PriorityQueue ermitteln. Verstehe ich das richtig, dass man mit Comparator die Liste sortiert? Wie kann man einzelne Elemente der Liste ändern?
int[] knoten = new int[n];
PriorityQueue schlange = new PriorityQueue();
for(int i = 0; i < n; i++){
if(i==0){
knoten[i] = 0;
}else{
knoten[i] = Integer.MAX_VALUE();
}
schlange.add(knoten[i]);
}
[code=Java]
Nun würde ich gerne das Minimum bestimmen, was ich ja immer brauche für den Algorithmus.
Eine PriorityQueue sortiert die Elemente bereits beim Einfügen, wobei das kleinste Elemente immer am Kopf der Queue steht. Das Minimum erhältst du daher über
Code:
schlange.poll()
.
Wenn du in deiner PriorityQueue nur primitive Datentypen (zB int) einfügst, wird die natürliche Ordnung (zB 1 < 2 < ...) verwendet und du musst keinen Comparator angeben. Andernfalls wird der Comparator dem Konstruktor der PriorityQueue übergeben.
Nun zu deinem Dijkstra: In der PriorityQueue sollten sich die Vertices sortiert nach ihrer Distanz (= aufsummierte Kantengewichte) befinden, denn den Vertex mit der kleisten Distanz willst du immer als Nächstes betrachten.
Aber wo speicherst du die Distanz? Und wie willst du sie einem Knoten zuordnen?
In meinem bereits vorgestellten Konzept mit Objekten für Edges/Vertices müsstest du die Klasse Vertex nur um das Attribut distance erweitern und das Interface Comparable implementieren, um die natürliche Ordnung (bezogen auf distance) zu haben:
Java:
class Vertex implements Comparable<Vertex> {
List<Edge> connections;
double distance;
public int compareTo(Vertex other) {
return Double.compare(distance, other.distance);
}
}
Für Dijkstra wäre dann auch noch ein Attribut Vertex next bzw. previous sinnvoll, um sofort den kürzesten Weg zu erhalten.
