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}&{\infty }&{\infty }&{\infty }&{\infty }\\{\infty }&0&6&3&10&{\infty }&{\infty }\\{\infty }&{\infty }&0&4&{\infty }&9&{\infty }\\{\infty }&{\infty }&3&0&6&3&{\infty }\\{\infty }&{\infty }&{\infty }&4&0&3&2\\{\infty }&{\infty }&{\infty }&{\infty }&2&0&2\\{\infty }&{\infty }&{\infty }&{\infty }&{\infty }&{\infty }&0\\\end{array}}\right)$

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

Materialien

Neues Material hinzufügen

E

• Exercise 23.png (details)