TU Wien:Diskrete Mathematik für Informatik UE (Gittenberger)/Übungen WS13/Beispiel 23

Use the algorithm of Floyd-Warshall to compute all distances in the following graph.

Solution

$x_y=e^t$

$D^{(1)}=\left(\begin{array}{ccccccc}0& 4& 5& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }\\ \mathrm{\infty }& 0& 6& 3& 10& \mathrm{\infty }& \mathrm{\infty }\\ \mathrm{\infty }& \mathrm{\infty }& 0& 4& \mathrm{\infty }& 9& \mathrm{\infty }\\ \mathrm{\infty }& \mathrm{\infty }& 3& 0& 6& 3& \mathrm{\infty }\\ \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& 4& 0& 3& 2\\ \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& 2& 0& 2\\ \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& 0\end{array}\right)$

$D^{(1)}=\left(\begin{array}{ccccccc}0& 4& 5& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }\\ \mathrm{\infty }& 0& 6& 3& 10& \mathrm{\infty }& \mathrm{\infty }\\ \mathrm{\infty }& \mathrm{\infty }& 0& 4& \mathrm{\infty }& 9& \mathrm{\infty }\\ \mathrm{\infty }& \mathrm{\infty }& 3& 0& 6& 3& \mathrm{\infty }\\ \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& 4& 0& 3& 2\\ \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& 2& 0& 2\\ \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& 0\end{array}\right)$ $D^{(2)}=\left(\begin{array}{ccccccc}0& 4& 5& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }\\ \mathrm{\infty }& 0& 6& 3& 10& \mathrm{\infty }& \mathrm{\infty }\\ \mathrm{\infty }& \mathrm{\infty }& 0& 4& \mathrm{\infty }& 9& \mathrm{\infty }\\ \mathrm{\infty }& \mathrm{\infty }& 3& 0& 6& 3& \mathrm{\infty }\\ \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& 4& 0& 3& 2\\ \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& 2& 0& 2\\ \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& 0\end{array}\right)$ $D^{(3)}=\left(\begin{array}{ccccccc}0& 4& 5& 7& 14& \mathrm{\infty }& \mathrm{\infty }\\ \mathrm{\infty }& 0& 6& 3& 10& \mathrm{\infty }& \mathrm{\infty }\\ \mathrm{\infty }& \mathrm{\infty }& 0& 4& \mathrm{\infty }& 9& \mathrm{\infty }\\ \mathrm{\infty }& \mathrm{\infty }& 3& 0& 6& 3& \mathrm{\infty }\\ \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& 4& 0& 3& 2\\ \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& 2& 0& 2\\ \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& 0\end{array}\right)$ $D^{(4)}=\left(\begin{array}{ccccccc}0& 4& 5& 7& 14& 14& \mathrm{\infty }\\ \mathrm{\infty }& 0& 6& 3& 10& 15& \mathrm{\infty }\\ \mathrm{\infty }& \mathrm{\infty }& 0& 4& \mathrm{\infty }& 9& \mathrm{\infty }\\ \mathrm{\infty }& \mathrm{\infty }& 3& 0& 6& 3& \mathrm{\infty }\\ \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& 4& 0& 3& 2\\ \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& 2& 0& 2\\ \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& 0\end{array}\right)$ $D^{(5)}=\left(\begin{array}{ccccccc}0& 4& 5& 7& 13& 10& \mathrm{\infty }\\ \mathrm{\infty }& 0& 6& 3& 9& 6& \mathrm{\infty }\\ \mathrm{\infty }& \mathrm{\infty }& 0& 4& 10& 7& \mathrm{\infty }\\ \mathrm{\infty }& \mathrm{\infty }& 3& 0& 6& 3& \mathrm{\infty }\\ \mathrm{\infty }& \mathrm{\infty }& 7& 4& 0& 3& 2\\ \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& 2& 0& 2\\ \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& 0\end{array}\right)$ $D^{(6)}=\left(\begin{array}{ccccccc}0& 4& 5& 7& 13& 10& 15\\ \mathrm{\infty }& 0& 6& 3& 9& 6& 11\\ \mathrm{\infty }& \mathrm{\infty }& 0& 4& 10& 7& 12\\ \mathrm{\infty }& \mathrm{\infty }& 3& 0& 6& 3& 8\\ \mathrm{\infty }& \mathrm{\infty }& 7& 4& 0& 3& 2\\ \mathrm{\infty }& \mathrm{\infty }& 9& 6& 2& 0& 2\\ \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& 0\end{array}\right)$ $D^{(7)}=\left(\begin{array}{ccccccc}0& 4& 5& 7& 12& 10& 12\\ \mathrm{\infty }& 0& 6& 3& 8& 6& 8\\ \mathrm{\infty }& \mathrm{\infty }& 0& 4& 9& 7& 9\\ \mathrm{\infty }& \mathrm{\infty }& 3& 0& 5& 3& 5\\ \mathrm{\infty }& \mathrm{\infty }& 7& 4& 0& 3& 2\\ \mathrm{\infty }& \mathrm{\infty }& 9& 6& 2& 0& 2\\ \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& 0\end{array}\right)=D^{(8)}$

Materialien

Neues Material hinzufügen

E

• Exercise 23.png (details)