Homework 12-4
=
###### tags: `Course - Algorithmics`
## Figure 25.2.
## Pseudo Code

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