Dijkstra Algorithmus in Java Swing implementieren?

Hallo,

ich versuche gerade, den Dijkstra-Algorithmus in Java Swing als Animation zu implementieren. Die Distanz kriegt mein Algorithmus auch immer richtig hin, an sich dürfte da also kein Fehler sein. Der Fehler liegt in der Speicherung des Weges von A nach B. Wenn es komplizierte Barrieren dazwischen gibt, dann ist er falsch und gibt nicht die korrekte Lösung.

Hier der Dijkstra-Code in Java: https://pastebin.com/cnWNkfn5

Matrix:

public static ArrayList<Integer> TreeIntoArrayList (TreeMap<Integer,ArrayList<Integer>> Liste) {
  ArrayList<Integer> Liste1 = new ArrayList<>();

  for (ArrayList<Integer> n : Liste.values()) {
    for (Integer m: n) {
      Liste1.add(m);
    }
  }

  return Liste1;
}

public static int findMinVertex(int[] distance,boolean visited[]) {
  int minVertex = -1;

  for (int i = 0; i < distance.length; i++) {
    if (!visited[i] && (minVertex == -1 || distance[i] < distance[minVertex])) {
      minVertex = i;
    }
  }

  return minVertex;
}

Also der Code ist nicht besonders sauber geschrieben.

Zu meiner Idee: Ich wollte mit der TreeMap meine Einträge nach der Entfernung sortieren.

  • Key: Entfernung von Knoten nGrün zum Knoten j (Anfangsknoten)
  • Value: Hilfsliste mit den Knoten j die darauf zutreffen

Anschließend will ich aus der TreeMap wieder eine ArrayList machen und den Knoten n in eine Variable stecken, der ja der Vorgänger von j sein sollte. Also:

VorgängerListe[j] = n

Anschließend stelle ich die Route durch Rekursion der Vorgänger her und gebe die Liste aus (nicht in dem Java Auszug drauf). Meine Vorgängerliste ist aber irgendwie nicht immer korrekt, wenn es kompliziertere Adjazenzmatrizen erhält. Sie speichert dann nur 90% richtig.

Ich habe das Gefühl, dass etwas mit meiner TreeMap nicht stimmt und dass es so vielleicht nicht geht.

Computer, Mathematik, Programmieren, Java, Programmierung, Informatik, Algorithmus
2 Antworten
Informatik Schülerwahl Optimierungsproblem (Algorithmus)?

Also, es geht um ein theoretisches Beispiel, das bald so in Praxis umgesetzt werden könnte an unserer Schule, beziehungsweiße im Unttericht behandelt werden könnte(Ferienprojekt).

Es geht um eine Schülerwahl mit Erst-, Zweit- und Dritt-Wahl! Jeder der Schüler gibt also eine Erst, zweit und drittwahl ab, je nachdem in welche der Gruppen/projekten er eingeteilt werden möchte. Jetzt hat jede Gruppe eine bestimmte Anzahl an Plätzen, sagen wir mal zweier Gruppen also eine Gruppengröße von 2, wobei es dann genau halb so viele Gruppen wie Schüler geben würde, sodass die Schüler eben genau in die Gruppen eingeteilt werden. Die Aufgabe ist jetzt, die Schüler OPTIMAL in die Gruppen einzuteilen, möglichst nach erst-, wenn nicht nach zweit und ansonsten nach dritt wunsch.

So, das klang am Anfang erstmal sehr kompliziert, bevor ich hier geschrieben habe, hab ich also ein bisschen Recherche betrieben für einen eventuellen Lösungsansatz und ein bisschen rumprobiert.

Beim Ausprobieren, habe ich konkurenz freie Schüler in ihre passende Gruppe eingeteilt und dannach alle Verteilungsmöglichkeiten durchgegangen (Brute Force) und so die optimale ermittelt.

Das ist jetzt ein bisschen umständlich und ich habe in anderen Foren von dem gleichem Problem/Aufgabe gehört. Hier wurde dieses als Optimierungsaufgabe bezeichnet, welche mit Algorithmen zu lösen wäre. (simplex Algorithmus)

Kennt jemand den besagten Algorithmus und kann diesen auf das Beispiel grob beschreiben anwenden oder kennt jemand eine bessere Möglichkeit/Algorithmus um das Problem möglichst effizient zu lösen?

Danke vielmals für jegliche Hilfe!

Schule, Programmieren, Informatik, Algorithmus, Ausbildung und Studium
1 Antwort
Algorithmus rausfinden?

Hey,

Also ich versuche grade den Algorithmus bzw die Verschlüsselung dieses Codes rauszufinden:

54648876198764616010181848149467666868477546754665576457557466667557755765566545664466556645664466456546545645645657545554454465446544466443667445677745677445667644455 477546754665576457557466667557755765566545664466556645664466456546545645645657545554454465446544466443667445677745677445667644455 645657545554454465446544466443667445677745677445667644455 477546754665576457557466667557755765566545664466556645664466456546545645645657545554454465446544466443667445677745677445667644455477546754665576457557466667557755765566545664466556645664466456546545645645657545554454465446544466443667445677745677445667644455 477546754665576457557466667557755765566545664466556645664466456546545645645657545554454465446544466443667445677745677445667644455 645657545554454465446544466443667445677745677445667644455 477546754665576457557466667557755765566545664466556645664466456546545645645657545554454465446544466443667445677745677445667644455477546754665576457557466667557755765566545664466556645664466456546545645645657545554454465446544466443667445677745677445667644455 477546754665576457557466667557755765566545664466556645664466456546545645645657545554454465446544466443667445677745677445667644455 645657545554454465446544466443667445677745677445667644455 477546754665576457557466667557755765566545664466556645664466456546545645645657545554454465446544466443667445677745677445667644455477546754665576457557466667557755765566545664466556645664466456546545645645657545554454465446544466443667445677745677445667644455 477546754665576457557466667557755765566545664466556645664466456546545645645657545554454465446544466443667445677745677445667644455 645657545554454465446544466443667445677745677445667644455 477546754665576457557466667557755765566545664466556645664466456546545645645657545554454465446544466443667445677745677445667644455477546754665576457557466667557755765566545664466556645664466456546545645645657545554454465446544466443667445677745677445667644455 477546754665576457557466667557755765566545664466556645664466456546545645645657545554454465446544466443667445677745677445667644455 645657545554454465446544466443667445677745677445667644455 477546754665576457557466667557755765566545664466556645664466456546545645645657545554454465446544466443667445677745677445667644455477546754665576457557466667557755765566545664466556645664466456546545645645657545554454465446544466443667445677745677445667644455 477546754665576457557466667557755765566545664466556645664466456546545645645657545554454465446544466443667445677745677445667644455

Es geht noch weiter aber man kann nicht so vielhier losten

Lg

Computer, Mathematik, Mathe, Informatik, Algorithmus
7 Antworten
Bei Djkstra mit negativen Kantengewichten positive Konstante addieren?

Einen wunderschönen guten boungiorno an alle,

Gegeben sei ein Graph G mit negativen Kantengewichten w ∈ ℤ \ℕ. Sei k das kleinste Gewicht einer Kante. Wir verfolgen die folgende Strategie, um die negativen Gewichte in positive zu transformieren: Addiere |k| auf jedes Kantengewicht und führe den Dijkstra-Algorithmus aus.Führt unsere Strategie zu einer korrekten Bestimmung der kürzesten Wege in G? Begründe Deine Antwort anhand eines Beispielgraphen.

Ansatz: Ich bin mir nicht sicher ob ich die Aufgabe richtig verstanden habe. Wir haben hier jetzt einen Graphen, der ausschließlich aus negativen Kantengewichten besteht. Und jetzt sollen wir |k| also das größte negative Gewicht auf jede einzelne Kante addieren und prüfen, ob Dijkstra noch korrekt funktioniert. Und genau da liegt der Hund in der Petersilie begraben. Weil Djkstra arbeitet doch ohnehin schon nicht mehr 100 % korrekt mit negativen Kantangewichten. Wie soll ich dann prüfen, ob er unter dieser Modifikation ( |k| drauf addieren ), dann noch korrekt arbeitet, wenn schon mal die Voraussetzung für korrektes Arbeiten nicht mehr erfüllt ist.

In dem Hinweis steht jetzt „Begründe Deine Antwort anhand eines Beispielgraphen“.. das hört sich so an als würden die dann nach einem Gegenbeispiel fragen.

Aber es würde sich doch nichts an den Kürzesten Wegen ändrern. Angenommen wir haben jetzt einen Graphen mit den Kantengewichten k = -10, -9, -8, -7, -6, -5, -4, -3, -2, -1. Dann wäre das kleinste Gewicht k = - 10. Also ist |k| = 10. Also überall 10 addieren

-10 + 10 = 0

-9 + 10 = -1

-8 + 10 = - 2

-1 + 10 = 9

usw.

Dann sind die Kantengewichte halt alle um 10 größer. Ändert sich nichts dran.Die Wege die früher "-10" waren und die kürzesten wahren, sind jetzt halt die Wege die "0" heißen und die kürzesten sind. Diejenigen die früher die zweitkürzesten waren und "-9" hießen, heißen jetzt halt "-1" usw.. Selbes System. Oder hat jemand ein gutes Gegenbeispiel wo es nicht funktioniert? Bei positiven Kantengewichten würde mir jetzt sowart was einfallen, aber hier sollen die Gewichte ja nur negativ sein.

Danke und einen wunderschönen sonnigen Sonntag Nachmittag

Studium, Schule, Mathematik, Mathe, rechnen, gewichte, Informatik, Theoretische Informatik, Uni, Algorithmus, Graphentheorie, Kante
2 Antworten

Meistgelesene Fragen zum Thema Algorithmus