Floyd-Warshall < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hi Leute!
Oben in der Aufgabenstellung ist die Distanzmatrix [mm] $D^0$ [/mm] gegeben. Ich hab mich nun an der Distanzmatrix [mm] $D^1$ [/mm] versucht und dabei auf dieses Ergebnis gekommen: ![[a]](/images/paperclip.gif "Dateianhänge") berechnete Distanzmatrix
Berechnet hab ich das ganz so mit diesem Algorithmus:
for k=1 to 6
for i=1 to 6
for j=1 to 6
[mm] d_{ij}^k=min\left(d_{ij}^{k-1}, d_{ik}^{k-1} +d_{kj}^{k-1} \right)
[/mm]
end for
end for
end for
Die ersten und die letzten Werte sehen so aus:
i=1, k=1, j=1: [mm] $d_{11}^1=min\left(d_{11}^{1-1}, d_{11}^{1-1} +d_{11}^{1-1} \right) [/mm] = [mm] min\left( 0,0 \right) [/mm] = 0$ (diagonales Element) (dieses Ergebnis braucht nicht mit dem Element an der Stelle verglichen werden, welches noch in der [mm] $D^1$ [/mm] steht, da diagonale Elemente eh immer 0 sind)
i=1, k=1, j=2: [mm] $d_{12}^1=min\left(d_{12}^{1-1}, d_{11}^{1-1} +d_{12}^{1-1} \right) [/mm] = [mm] min\left( \infty, 0+\infty \right) [/mm] = [mm] \infty$ [/mm] (dieses Ergebnis muss natürlich jetzt noch mit dem Element an der Stelle verglichen werden, welches noch in der [mm] $D^1$ [/mm] steht, denn es soll ja auch wirklich "echt kleiner" sein)
.
.
.
i=6, k=1, j=5: [mm] $d_{65}^1=min\left(d_{65}^{1-1}, d_{61}^{1-1} +d_{15}^{1-1} \right) [/mm] = [mm] min\left( \infty, \infty+(-1) \right) [/mm] = [mm] \infty$ [/mm] (dieses Ergebnis muss natürlich jetzt noch mit dem Element an der Stelle verglichen werden, welches noch in der [mm] $D^1$ [/mm] steht, denn es soll ja auch wirklich "echt kleiner" sein)
i=6, k=1, j=6: [mm] $d_{66}^1=min\left(d_{66}^{1-1}, d_{61}^{1-1} +d_{16}^{1-1} \right) [/mm] = [mm] min\left( 0, \infty+\infty \right) [/mm] = 0$ (diagonales Element) (dieses Ergebnis braucht nicht mit dem Element an der Stelle verglichen werden, welches noch in der [mm] $D^1$ [/mm] steht, da diagonale Elemente eh immer 0 sind)
Stimmt das alles so? Könnt ihr mir da helfen?
Dateianhänge:
Anhang Nr. 1 (Typ: png) [nicht öffentlich]
Anhang Nr. 2 (Typ: png) [nicht öffentlich]
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:20 Fr 01.02.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
![[a]](uploads/forum/00947154/forum-i00947154-n001.png "Dateianhänge"){kind=small}
gegebene Distanzmatrix![[a]](uploads/forum/00947154/forum-i00947154-n002.png "Dateianhänge"){kind=small}
berechnete Distanzmatrix