Ich habe mit Hilfe des Schulbuch (Klett Gym, Informatik 4, S. 127) versucht, den Dijkstra-Algorithmus umzusetzen.
In der Schule haben wir noch keine Listen gelernt. Die Aufgabe soll mit Feldern so weit wie möglich gelöst werden und ArrayList sind auch erlaubt.
Leider funktioniert mein Code noch nicht.
Bei der Ausgabe kommt noch nicht der Wert für die kürzeste Entfernung raus.
Wie kann ich die Ausgabe der kürzesten Entfernungen mir anzeigen lassen und auch die Reihenfolge der Knoten vom Start bis zum Ziel ausgeben lassen? Bei mir bricht der Code noch nicht ab, wenn ich den Zielknoten erreicht habe.
Im Programmcode ist das Attribut istBesucht nur für die Breitensuche gedacht. Für Dijkstra sollte es nicht notwendig sein???
Danke.
In der Schule haben wir noch keine Listen gelernt. Die Aufgabe soll mit Feldern so weit wie möglich gelöst werden und ArrayList sind auch erlaubt.
Leider funktioniert mein Code noch nicht.
Bei der Ausgabe kommt noch nicht der Wert für die kürzeste Entfernung raus.
Wie kann ich die Ausgabe der kürzesten Entfernungen mir anzeigen lassen und auch die Reihenfolge der Knoten vom Start bis zum Ziel ausgeben lassen? Bei mir bricht der Code noch nicht ab, wenn ich den Zielknoten erreicht habe.
Im Programmcode ist das Attribut istBesucht nur für die Breitensuche gedacht. Für Dijkstra sollte es nicht notwendig sein???
Danke.
Java:
public class Knoten{
private String bezeichnung;
private boolean istBesucht;
private Knoten vorgaenger;
private int pfadgewicht;
public Knoten(String neueBezeichnung){
bezeichnung = neueBezeichnung;
}
public String bezeichnungGeben(){
return bezeichnung;
}
public void bezeichnungSetzen(String neueBezeichnung){
bezeichnung = neueBezeichnung;
}
public boolean istBesuchtGeben(){
return istBesucht;
}
public void istBesuchtSetzen(boolean neuIstBesucht){
istBesucht = neuIstBesucht;
}
public Knoten vorgaengerGeben(){
return vorgaenger;
}
public void vorgaengerSetzen(Knoten neuerVorgaenger){
vorgaenger = neuerVorgaenger;
}
public int pfadgewichtGeben(){
return pfadgewicht;
}
public void pfadgewichtSetzen(int neuesPfadgewicht){
pfadgewicht = neuesPfadgewicht;
}
}
Code:
import java.util.*;
public class Graph{
private Knoten[] knotenfeld;
private int[][] adjazenzmatrix;
private int maxAnzahl;
private int aktAnzahl;
public Graph(int neueMaxAnzahl){
knotenfeld = new Knoten[neueMaxAnzahl];
adjazenzmatrix = new int[neueMaxAnzahl][neueMaxAnzahl];
maxAnzahl = neueMaxAnzahl;
aktAnzahl = 0;
}
public Knoten[] knotenfeldGeben(){
return knotenfeld;
}
public int[][] adjazenzmatrixGeben(){
return adjazenzmatrix;
}
public void knotenEinfuegen(Knoten k){
if(aktAnzahl < maxAnzahl){
knotenfeld[aktAnzahl] = k;
aktAnzahl++;
}
else{
System.out.println("Fehler! Es kann kein Knoten mehr eingefuegt werden.");
}
}
public void knotenEinfuegen2(Knoten k){
if (aktAnzahl < maxAnzahl){
boolean istEingefuegt = false;
int index = 0;
while ((index < maxAnzahl) && (!istEingefuegt)){
if (knotenfeld[index] == null){
knotenfeld[index] = k;
istEingefuegt = true;
}
else{
index++;
}
}
aktAnzahl++;
}
else{
System.out.println("Fehler! Es kann kein Knoten mehr eingefuegt werden.");
}
}
public void kanteHinzufuegen(int startindex, int zielindex, int wert){
if(startindex < 0 || zielindex < 0 || startindex >= aktAnzahl || zielindex >= aktAnzahl){
System.out.println("Fehler! Falscher Index. Die Kante kann nicht hinzugefuegt werden.");
}
else{
adjazenzmatrix[startindex][zielindex] = wert;
}
}
public void kanteEntfernen(int startindex, int zielindex){
if(adjazenzmatrix[startindex][zielindex] == 0 || startindex >= aktAnzahl || zielindex >= aktAnzahl){
System.out.println("Fehler! Die Kante kann nicht entfernt werden.");
}
else{
adjazenzmatrix[startindex][zielindex] = 0;
}
}
public void alleKantenEntfernen(){
for(int i = 0; i < maxAnzahl; i++){
for(int j = 0; j < maxAnzahl; j++){
adjazenzmatrix[i][j] = 0;
}
}
}
public int knotenindexSuchen(Knoten k){
int index = -1;
int i = 0;
while(index < 0 && i < knotenfeld.length){
if(knotenfeld[i].equals(k)){
index = i;
}
else{
i++;
}
}
if(index < 0){
System.out.println("Fehler! Der Knoten wurde nicht gefunden.");
}
return index;
}
public int knotenindexSuchen2(String name){
int index = -1;
int i = 0;
while(index < 0 && i < knotenfeld.length){
if(knotenfeld[i].bezeichnungGeben().equals(name)){
index = i;
}
else{
i++;
}
}
if(index < 0){
System.out.println("Fehler! Der Knoten wurde nicht gefunden.");
}
return index;
}
public void kanteHinzufuegen2(String start, String ziel, int wert){
int startindex = knotenindexSuchen2(start);
int zielindex = knotenindexSuchen2(ziel);
kanteHinzufuegen(startindex, zielindex, wert);
}
public void knotenEntfernen(String name){
int knotenindex = knotenindexSuchen2(name);
if(knotenindex < 0){
System.out.println("Fehler! Der Knoten konnte nicht entfernt werden.");
}
else{
for(int i = 0; i < aktAnzahl; i++){
adjazenzmatrix[knotenindex][i] = 0;
adjazenzmatrix[i][knotenindex] = 0;
}
knotenfeld[knotenindex] = null;
}
}
public void adjazenzmatrixAusgeben(){
System.out.print(" ");
for(int i = 0; i < aktAnzahl; i++){
System.out.print(" " + i + " ");
}
System.out.println(" ");
for(int i = 0; i < aktAnzahl; i++){
System.out.print(i + " ");
for(int j = 0; j < aktAnzahl; j++){
System.out.print(" " + adjazenzmatrix[i][j] + " ");
}
System.out.println();
}
}
public void knotenfeldAusgeben(){
System.out.println("Knotendaten:");
for(int i = 0; i < aktAnzahl; i++){
System.out.println(knotenfeld[i].bezeichnungGeben());
System.out.println();
}
}
public void dijkstraAusgeben(String start, String ziel){
int startindex = knotenindexSuchen2(start);
int zielindex = knotenindexSuchen2(ziel);
if(startindex == -1 || zielindex == -1){
System.out.println("Fehler! Der Startknoten oder der Zielknoten konnte nicht gefunden werden!");
}
else{
for(int i = 0; i < aktAnzahl; i++){
if(i == startindex){
knotenfeld[startindex].pfadgewichtSetzen(0);
knotenfeld[startindex].vorgaengerSetzen(null);
knotenfeld[startindex].istBesuchtSetzen(false);
}
else{
knotenfeld[i].pfadgewichtSetzen(Integer.MAX_VALUE);
knotenfeld[i].vorgaengerSetzen(null);
knotenfeld[i].istBesuchtSetzen(false);
}
}
}
ArrayList<Integer> warteschlange = new ArrayList<Integer>(); // Warteschlange fuer die Knoten (Speichern der Indizes)
for(int i = 0; i < aktAnzahl; i++){
warteschlange.add(i); // Hinzufuegen aller Knoten
}
// knotenfeld[startindex].istBesuchtSetzen(true); // Startknoten auf "besucht" setzen
while(!warteschlange.isEmpty()){
int aktiverKnotenindex = warteschlange.remove(0);
for(int j = 0; j < aktAnzahl; j++){
if(adjazenzmatrix[aktiverKnotenindex][j] >= 0){
relaxationAusfuehren(aktiverKnotenindex, j);
}
}
System.out.println("Pfadgewicht: " + knotenfeld[aktiverKnotenindex].pfadgewichtGeben());
}
}
public void relaxationAusfuehren(int uIndex, int vIndex){
int uGewicht = knotenfeld[uIndex].pfadgewichtGeben();
int vGewicht = knotenfeld[vIndex].pfadgewichtGeben();
int kantengewicht = adjazenzmatrix[uIndex][vIndex];
if(vGewicht > uGewicht + kantengewicht){
knotenfeld[vIndex].pfadgewichtSetzen(uGewicht + kantengewicht);
knotenfeld[vIndex].vorgaengerSetzen(knotenfeld[uIndex]);
}
}
}
Code:
public class Testablauf{
private Graph g;
public void ablaufen(){
g = new Graph(5); // Der Graph hat 5 Knoten
Knoten k1 = new Knoten("A");
Knoten k2 = new Knoten("B");
Knoten k3 = new Knoten("C");
Knoten k4 = new Knoten("D");
Knoten k5 = new Knoten("E");
g.knotenEinfuegen(k1); // Index 0
g.knotenEinfuegen(k2); // Index 1
g.knotenEinfuegen(k3); // Index 2
g.knotenEinfuegen(k4); // Index 3
g.knotenEinfuegen(k5); // Index 4
g.kanteHinzufuegen(0, 1, 3); // A-B
g.kanteHinzufuegen(1, 0, 3);
g.kanteHinzufuegen(0, 2, 4); // A-C
g.kanteHinzufuegen(2, 0, 4);
g.kanteHinzufuegen(0, 4, 1); // A-E
g.kanteHinzufuegen(4, 0, 1);
g.kanteHinzufuegen(1, 2, 2); // B-C
g.kanteHinzufuegen(2, 1, 2);
g.kanteHinzufuegen(2, 3, 1); // C-D
g.kanteHinzufuegen(3, 2, 1);
g.kanteHinzufuegen(3, 4, 5); // D-E
g.kanteHinzufuegen(4, 3, 5);
g.dijkstraAusgeben("A", "D");
}
}
