---
# System prepended metadata

title: Homework 12-4
tags: [Course - Algorithmics]

---

Homework 12-4
=
###### tags: `Course - Algorithmics`
## Figure 25.2.
![](https://i.imgur.com/HBeJw9q.png)
## Pseudo Code
```python=
for k from 1 to n:
    for u from 1 to n:
        for v from 1 to n:
            if D[u][v] > D[u][k] + D[k][v]:
                D[u][v] = D[u][k] + D[k][v]
                P[u][v] = P[k][v]
```
## (a) Show the matrix $D$$^($$^k$$^)$ that results for each iteration of the outer loop.
Distance table:
| $D$$^($$^0$$^)$ |  1  |  2  |  3  |  4  |  5  |  6  |
|:---------------:|:---:|:---:|:---:|:---:|:---:|:---:|
|        1        |  0  |  ∞  |  ∞  |  ∞  | -1  |  ∞  |
|        2        |  1  |  0  |  ∞  |  2  |  ∞  |  ∞  |
|        3        |  ∞  |  2  |  0  |  ∞  |  ∞  | -8  |
|        4        | -4  |  ∞  |  ∞  |  0  |  3  |  ∞  |
|        5        |  ∞  |  7  |  ∞  |  ∞  |  0  |  ∞  |
|        6        |  ∞  |  5  | 10  |  ∞  |  ∞  |  0  |

|$D$$^($$^1$$^)$|  1  |  2  |  3  |  4  |  5  |  6  |
|:-------------:|:---:|:---:|:---:|:---:|:---:|:---:|
|       1       |  0  |  ∞  |  ∞  |  ∞  | -1  |  ∞  |
|       2       |  1  |  0  |  ∞  |  2  |<font color=red>0</font>|  ∞  |
|       3       |  ∞  |  2  |  0  |  ∞  |  ∞  | -8  |
|       4       | -4  |  ∞  |  ∞  |  0  |<font color=red>-5</font>|  ∞  |
|       5       |  ∞  |  7  |  ∞  |  ∞  |  0  |  ∞  |
|       6       |  ∞  |  5  | 10  |  ∞  |  ∞  |  0  |

|$D$$^($$^2$$^)$|  1  |  2  |  3  |  4  |  5  |  6  |
|:-------------:|:---:|:---:|:---:|:---:|:---:|:---:|
|       1       |  0  |  ∞  |  ∞  |  ∞  | -1  |  ∞  |
|       2       |  1  |  0  |  ∞  |  2  |  0  |  ∞  |
|       3       |<font color=red>3</font>|  2  |  0  |<font color=red>4</font>|<font color=red>2</font>| -8  |
|       4       | -4  |  ∞  |  ∞  |  0  | -5  |  ∞  |
|       5       |<font color=red>8</font>|  7  |  ∞  |<font color=red>9</font>|  0  |  ∞  |
|       6       |<font color=red>6</font>|  5  | 10  |<font color=red>7</font>|<font color=red>5</font>|  0  |

| $D$$^($$^3$$^)$ |  1  |  2  |  3  |  4  |  5  |  6  |
|:---------------:|:---:|:---:|:---:|:---:|:---:|:---:|
|        1        |  0  |  ∞  |  ∞  |  ∞  | -1  |  ∞  |
|        2        |  1  |  0  |  ∞  |  2  |  0  |  ∞  |
|        3        |  3  |  2  |  0  |  4  |  2  | -8  |
|        4        | -4  |  ∞  |  ∞  |  0  | -5  |  ∞  |
|        5        |  8  |  7  |  ∞  |  9  |  0  |  ∞  |
|        6        |  6  |  5  | 10  |  7  |  5  |  0  |

| $D$$^($$^4$$^)$ |  1  |  2  |  3  |  4  |  5  |  6  |
|:---------------:|:---:|:---:|:---:|:---:|:---:|:---:|
|        1        |  0  |  ∞  |  ∞  |  ∞  | -1  |  ∞  |
|        2        |<font color=red>-2</font>|  0  |  ∞  |  2  |<font color=red>-3</font>|  ∞  |
|        3        |<font color=red>0</font>|  2  |  0  |  4  |<font color=red>-1</font>| -8  |
|        4        | -4  |  ∞  |  ∞  |  0  | -5  |  ∞  |
|        5        |<font color=red>5</font>|  7  |  ∞  |  9  |  0  |  ∞  |
|        6        |<font color=red>3</font>|  5  | 10  |  7  |<font color=red>2</font>|  0  |

|$D$$^($$^5$$^)$|  1  |  2  |  3  |  4  |  5  |  6  |
|:-------------:|:---:|:---:|:---:|:---:|:---:|:---:|
|       1       |  0  |<font color=red>6</font>|  ∞  |<font color=red>8</font>| -1  |  ∞  |
|       2       | -2  |  0  |  ∞  |  2  | -3  |  ∞  |
|       3       |  0  |  2  |  0  |  4  | -1  | -8  |
|       4       | -4  |<font color=red>2</font>|  ∞  |  0  | -5  |  ∞  |
|       5       |  5  |  7  |  ∞  |  9  |  0  |  ∞  |
|       6       |  3  |  5  | 10  |  7  |  2  |  0  |

|$D$$^($$^6$$^)$|  1  |  2  |  3  |  4  |  5  |  6  |
|:-------------:|:---:|:---:|:---:|:---:|:---:|:---:|
|       1       |  0  |  6  |  ∞  |  8  | -1  |  ∞  |
|       2       | -2  |  0  |  ∞  |  2  | -3  |  ∞  |
|       3       |<font color=red>-5</font>|<font color=red>-3</font>|  0  |<font color=red>-1</font>|<font color=red>-6</font>| -8  |
|       4       | -4  |  2  |  ∞  |  0  | -5  |  ∞  |
|       5       |  5  |  7  |  ∞  |  9  |  0  |  ∞  |
|       6       |  3  |  5  | 10  |  7  |  2  |  0  |
## (b) List the vertices of one such shortest path from $v_6$ to $v_1$ .
Predecessor table:
|$P$$^($$^0$$^)$|  1  |  2  |  3  |  4  |  5  |  6  |
|:-------------:|:---:|:---:|:---:|:---:|:---:|:---:|
|       1       |  0  |  0  |  0  |  0  |  1  |  0  |
|       2       |  2  |  0  |  0  |  2  |  0  |  0  |
|       3       |  0  |  3  |  0  |  0  |  0  |  3  |
|       4       |  4  |  0  |  0  |  0  |  4  |  0  |
|       5       |  0  |  5  |  0  |  0  |  0  |  0  |
|       6       |  0  |  6  |  6  |  0  |  0  |  0  |

|$P$$^($$^1$$^)$|  1  |  2  |  3  |  4  |  5  |  6  |
|:-------------:|:---:|:---:|:---:|:---:|:---:|:---:|
|       1       |  0  |  0  |  0  |  0  |  1  |  0  |
|       2       |  2  |  0  |  0  |  2  |<font color=red>1</font>|  0  |
|       3       |  0  |  3  |  0  |  0  |  0  |  3  |
|       4       |  4  |  0  |  0  |  0  |<font color=red>1</font>|  0  |
|       5       |  0  |  5  |  0  |  0  |  0  |  0  |
|       6       |  0  |  6  |  6  |  0  |  0  |  0  |

|$P$$^($$^2$$^)$|  1  |  2  |  3  |  4  |  5  |  6  |
|:-------------:|:---:|:---:|:---:|:---:|:---:|:---:|
|       1       |  0  |  0  |  0  |  0  |  1  |  0  |
|       2       |  2  |  0  |  0  |  2  |  1  |  0  |
|       3       |<font color=red>2</font>|  3  |  0  |<font color=red>2</font>|<font color=red>1</font>|  3  |
|       4       |  4  |  0  |  0  |  0  |  1  |  0  |
|       5       |<font color=red>2</font>|  5  |  0  |<font color=red>2</font>|  0  |  0  |
|       6       |<font color=red>2</font>|  6  |  6  |<font color=red>2</font>|<font color=red>1</font>|  0  |

$\vdots$

|$P$$^($$^6$$^)$|  1  |  2  |  3  |  4  |  5  |  6  |
|:-------------:|:---:|:---:|:---:|:---:|:---:|:---:|
|       1       |  0  |  5  |  0  |  2  |  1  |  0  |
|       2       |  4  |  0  |  0  |  2  |  1  |  0  |
|       3       |<font color=red>4</font>|<font color=red>6</font>|  0  |<font color=red>2</font>|<font color=red>1</font>|<font color=red>3</font>|
|       4       |  4  |  5  |  0  |  0  |  1  |  0  |
|       5       |  4  |  5  |  0  |  2  |  0  |  0  |
|       6       |  4  |  6  |  6  |  2  |  1  |  0  |

* Result:
6 → 1 (See 4)
6 → 4 → 1 (See 2)
6 → 2 → 4 → 1