Java - Distanzmatrix Algorithmus, Wie ansetzen?
Hallo, ich bin gerade dabei ein Graphenprogramm zu schreiben und stecke bisschen bei der Distanzmatrix.
Ich weiß nicht ob sich jemand bei Graphentheorie auskennt oder nicht aber der Algorithmus für die Distanzmatrix ist relativ einfach. Nur das umsetzen in Code fällt mir sehr schwer und deswegen hoffe ich, dass ihr mir vielleicht dabei helfen könnt..
Der Algorithmus für eine Distanzmatrix lautet so:
Man hat eine Eingangsmatrix (Adjazentmatrix).
Die könnte so aussehen:
Man markiert sich alle Nuller die in der Adjazentmatrix vorkommen (AUßER DIE HAUPTDIAGONALE, DIE BLEIBT UNBERÜHRT).
Dann erstellt man sich eine eigene Matrix die man "DistanzMatrix" nennen kann und setzt alle Nuller die eben in der Adjazentmatrix vorkommen auf "Unendlich" oder auch auf INTEGER.MAX_VALUE in der Programmiersprache .
Das schaut dann so aus:
Also haben wir jetzt 2 Matrizen. Bis dahin habe ich es auch geschafft in meinem Programm. Die Ausgabe schaut bei mir so aus:
Die "-9" sind alle Nuller, die auf UNENDLICH gesetzt sind (siehe zweites Bild).
Der nächste Schritt ist es die Potenzen der Eingangsmatrix (Adjazentmatrix) zu berechnen. Das habe ich ebenfalls schon geschafft im Code.
Das heißt, die Adjazentmatrix (siehe Bild 1) wurde potenziert und so könnte das Ergebnis der Potenzberechnug aussehen.
Man schaut sich jetzt alle Nuller (außer die Hauptdiagonale von der Eingangsmatrix an (siehe Bild 1)) und markiert sich nur die Zahlen (rot), die sich von der Potenzierung der Eingangsmatrix verändert haben. (Außer die Nuller (=Neue Nuller die durch die Potenzierung entstanden sind bleiben auch weiterhin eine Null))
Und der letzte Schritt ist es jetzt, die von mir erstellte DistanzMatrix upzudaten, indem ich im ersten Schritt alle rote Zahlen von A²(G) in 2 umwandle. Alle Nuller die übrig bleiben, werden wieder in UNENDLICH umgewandelt.
Und das wird jetzt so oft wiederholt, bis es keine UNENDLICH Zeichen mehr in der Distanzmatrix gibt. Und aus UNENDLICH wird 3. Und immer so weiter.. Falls es zb nach der fünften Potenzierung immer noch Nuller bzw UNENDLICH Werte gibt dann wird aus UNENDLICH 5.
Somit ist D³(G) das Ergebnis.
Ich hoffe ich konnte es ausführlich genug erklären
Danke
2 Antworten
Mir ist nicht ganz klar, wo Dein Problem steckt. Soweit ich erkennen kann, gilt:
- Aⁿ enthält die Zahl der n-Pfade von i nach j. Interessant ist nur, ob da eine 0 steht oder nicht.
- Dⁿ enthält die minimale Pfadlänge von i nach j, oder ∞, wenn es keinen Pfad der Länge ≤n gibt.
Um Dⁿ aus Dⁿ⁻¹ und Aⁿ zu berechnen, schaust Du Dir einfach jeden noch unbekannten Wert Dⁿ⁻¹(i,j)=∞ an und überschreibst ihn mit Dⁿ(i,j):=n, falls ein n-Pfad von i nach j existiert, also Aⁿ(i,j)>0 ist:
boolean update ( int[][] D, int[][] An, int n )
{
boolean changed = false;
for ( int i=0; i<D.length; ++i )
for ( int j=0; j<D.length; ++j )
if ( D[i][j]>n && An[i][j]>0 )
{
D[i][j] = n;
changed = true;
}
return changed;
}
Wenn es keine Änderungen mehr gibt, kann man abbrechen. Das klappt auch, wenn der Graph nicht zusammenhängend ist und einige Distanzen noch ∞ sind.
Man schaut sich jetzt alle Nuller (außer die Hauptdiagonale von der Eingangsmatrix an (siehe Bild 1)) und markiert sich nur die Zahlen (rot), die sich von der Potenzierung der Eingangsmatrix verändert haben.
Ich sehe keinen Grund, die Werte in Aⁿ irgendwie zu markieren. Du prüfst einen Eintrag Aⁿ(i,j) doch eh nur, wenn bisher noch kein Pfad von i nach j gefunden wurde.
Übrigens würde ich mit D⁰ statt D¹ anfangen: D⁰(i,j):=∞, D⁰(i,i):=0. Dein D¹ berechnet sich beim ersten update(D⁰, A¹, 1).
Danke für den Kommentar, es hat mir auf jeden Fall weiter geholfen!
Aber es geht leider immer noch nicht bzw warhscheinlich habe ich etwas übersehen..
Mein Code für die Berechnung der Distanzmatrix schaut jetzt so aus:
public void Distanzmatrix() throws PersonalException
{
int[][] distanzMatrix = new int[dimension][dimension];
int[][] neuePotenz = new int[20][20];
@SuppressWarnings("unused")
int hauptdiagonale;
int unendlich = -9;
// Hauptdiagonale der Matrix wird erfasst und gespeichert. Alle restlichen Nuller werden als "unendlich" bezeichnet und gespeichert //
for (int i = 0; i < Matrix.length; i++)
{
for (int j = 0; j < Matrix[i].length; j++)
{
if(i == j)
{
hauptdiagonale = this.Matrix[i][j];
}
else if (Matrix[i][j] == 0)
{
this.Matrix[i][j] = unendlich;
}
// System.out.print(Matrix[i][j] + " ");
}
System.out.println();
}
System.out.println();
// Speichert die jetzige Matrix in "distanzMatrix" //
for (int i = 0; i < Matrix.length; i++)
{
for (int j = 0; j < Matrix[i].length; j++)
{
distanzMatrix[i][j] = Matrix[i][j];
System.out.print(distanzMatrix[i][j] + " ");
}
System.out.println();
}
//Ab hier beginnt der Teil den du mir erklärt hast
for(int k = 1; k < Matrix.length; k++)
{
update(distanzMatrix, neuePotenz, k);
for(int i = 0; i < Matrix.length; i++)
{
for (int j = 0; j < Matrix.length; j++)
{
if (neuePotenz[i][j] > 0 && distanzMatrix[i][j] == unendlich)
{
distanzMatrix[i][j] = k;
}
System.out.println(distanzMatrix[i][j]);
}
}
}
}
public boolean update (int[][] D, int[][] An, int n)
{
boolean changed = false;
for (int i = 0; i < D.length; i++ )
for (int j = 0; j < D.length; j++ )
if (D[i][j] > n && An[i][j] > 0 )
{
D[i][j] = n;
changed = true;
}
System.out.println(changed);
return changed;
}
Danke!!!
Der Code ist etwas aus dem Zusammenhang gerissen. Ich nehme an, dass Matrix und this.Matrix dasselbe sind und die Adjazenzmatrix darstellen.
Problem 1:
Du initialisiert die distanzMatrix falsch. Du darfst Matrix dabei nicht ändern, weil Du sie noch mehrfach brauchst. So sollte es aussehen:
int[][] distanzMatrix = new int[dimension][dimension];
int unendlich = -9;
for (int i = 0; i < Matrix.length; i++)
{
for (int j = 0; j < Matrix[i].length; j++)
{
if(i == j)
{
// (i,i) hat die Distanz 0:
distanzMatrix[i][j] = 0;
}
else if (Matrix[i][j] == 0)
{
// (i,j) ohne Kante haben eine unbekannte Distanz:
distanzMatrix[i][j] = unendlich;
}
else
{
// (i,j) mit Kante haben die Distanz 1:
distanzMatrix[i][j] = 1;
}
// System.out.print(distanzMatrix[i][j] + " ");
}
System.out.println();
}
Problem 2:
//Ab hier beginnt der Teil den du mir erklärt hast
for(int k = 1; k < Matrix.length; k++)
Du hast oben bereits alle Pfade der Länge 0 und 1 gesetzt. Jetzt suchst Du nach weiteren Pfaden ab Länge k=2.
Problem 3:
update(distanzMatrix, neuePotenz, k);
for(int i = 0; i < Matrix.length; i++)
{
//...
Meine update-Funktion macht praktisch dasselbe wie Dein nachfolgender Schleifenrumpf. (Nur habe ich angenommen, dass ∞ sehr groß ist. Mein Test D[i][j]>n funktioniert für -9 nicht, und deshalb tut meine Funktion effektiv nichts. Aber so oder so: Die doppelte Suche nach Pfaden der Länge k ist zwar nicht falsch, aber völlig überflüssig. Lass den update()-Aufruf einfach wieder weg.
Problem 4:
Du verwendest zwar neuePotenz für Matrix^k, berechnest sie aber nie. Das muss in jedem Schleifendurchlauf passieren:
int[][] neuePotenz = Matrix; // "Matrix hoch 1"
for(int k = 2; k < Matrix.length; k++)
{
// Matrix hoch k-1 --> Matrix hoch k:
neuePotenz = malMatrix(neuePotenz);
for(int i = 0; i < Matrix.length; i++)
{
//...
Beachte, dass malMatrix() das übergebene Argument nicht ändern darf, sondern eine neue Matrix erzeugen und zurückgeben muss:
public int[][] malMatrix(int[][] faktor)
{
int[][] produkt = new int[Matrix.length][Matrix.length];
for (int i = 0; i < Matrix.length; i++)
{
// produkt[i][j] berechnen
}
return produkt;
}
VIELEN VIELEN VIELEN DANK!!! Ich habe es endlich geschafft !!! Nur dank dir!!
Tausend Dank !!!!
Danke!
Hoffe du hast noch einen angenehmen Tag
Ausgabe auf der konsole:
Meine Ausgabe auf der Konsole habe ich unten als eigenen Kommentar gepostet