---
title: "Graphes - Plus court chemin suite"
date: "2023-06-23"
---

# Questions

* A quoi sert l'algorithme de Dijkstra?

. . .

* A trouver le plus court chemin entre un sommet, $s$, d'un graphe pondéré et tous les autres sommets.
* Quelle est la limitation de l'algorithme de Dijkstra?

. . .

* Les poids doivent être positifs.
* Résumer les étapes de l'algorithme de Dijkstra.

. . .

* `distance[source] = 0`, `distance[reste]=inf`;
* enfiler tous les sommets, `distance <=> priorité`;
* tant qu'il y a des sommets dans la file:
    * u = défiler;
    * pour tous les sommets `v` dans le voisinage de `u`;
    * mettre à jour `distance[v]` (priorité et précédence) si `distance[v] > distance[u] + w(u,v)`.


# Plus cours chemin pour toute paire de sommets

## Comment faire pour avoir toutes les paires?

. . .

* Appliquer Dijkstra sur tous les sommets d'origine.
* Complexité:
    * Graphe dense: $\mathcal{O}(|V|)\mathcal{O}(|V|^2\log|V|)=\mathcal{O}(|V|^3\log|V|)$.
    * Graphe peu dense: $\mathcal{O}(|V|)\mathcal{O}(|V|\log|V|)=\mathcal{O}(|V|^2\log|V|)$.

. . .

## Solution alternative: Floyd--Warshall

* Pour toutes paires de sommets $u,v\in V$, trouver le chemin de poids minimal reliant $u$ à $v$.
* Complexité $\mathcal{O}(|V|^3)$, indiqué pour graphes denses.
* Fonctionne avec la matrice d'adjacence.

# Algorithme de Floyd--Warshall

## Idée générale

* Soit l'ensemble de sommets $V=\{1, 2, 3, 4, ..., n\}$.
* Pour toute paire de sommets, $i,j$, on considère tous les chemins passant par les sommets intermédiaires $\in\{1, 2, ..., k\}$ avec $k\leq n$.
* On garde pour chaque $k$ la plus petite valeur.

## Principe

* A chaque étape, $k$, on vérifie s'il est plus court d'aller de $i$ à $j$ en passant par le sommet $k$.
* Si à l'étape $k-1$, le coût du parcours est $p$, on vérifie si $p$ est plus petit que $p_1+p_2$, le chemin de $i$ à $k$, et $k$ à $j$ respectivement.

# Algorithme de Floyd--Warshall

## The algorithme

Soit $d_{ij}(k)$ le plus court chemin de $i$ à $j$ passant par les sommets $\in\{1,2,...,k\}$

$$
d_{ij}(k)=\left\{
\begin{array}{ll}
         w(i,j), & \mbox{si } k=0,\\
         \min(d_{ij}(k-1),d_{ik}(k-1)+d_{kj}(k-1)), & \mbox{sinon}.
\end{array}
\right.
$$

# Algorithme de Floyd--Warshall (exemple)


::: columns

:::: column

![Le graphe, $D=w$.](figs/floyd_exemple.png)


::::

:::: column

## Que vaut $D^{(0)}$ (3min)?

. . .

$$
D^{(0)}=\begin{bmatrix}
0      & 2      & 4      & \infty & 3 \\
2      & 0      & 8      & \infty & 1 \\
6      & 2      & 0      & 4      & 3 \\
1      & \infty & \infty & 0      & 5 \\
\infty & \infty & \infty & 1      & 0 \\
\end{bmatrix}
$$

::::

:::

# Algorithme de Floyd--Warshall (exemple)


::: columns

:::: column

## On part de $D^{(0)}$?

$$
D^{(0)}=\begin{bmatrix}
0      & 2      & 4      & \infty & 3 \\
2      & 0      & 8      & \infty & 1 \\
6      & 2      & 0      & 4      & 3 \\
1      & \infty & \infty & 0      & 5 \\
\infty & \infty & \infty & 1      & 0 \\
\end{bmatrix}
$$


::::

:::: column

## Que vaut $D^{(1)}$ (3min)?

. . .

$$
D^{(0)}=\begin{bmatrix}
0      & 2          & 4               & \infty & 3 \\
2      & 0          & \mathbf{6}      & \infty & 1 \\
6      & 2          & 0               & 4      & 3 \\
1      & \mathbf{3} & \mathbf{5}      & 0      & \mathbf{4} \\
\infty & \infty     & \infty          & 1      & 0 \\
\end{bmatrix}
$$

::::

:::

# Algorithme de Floyd--Warshall (exemple)


::: columns

:::: column

## On part de $D^{(0)}$

$$
D^{(0)}=\begin{bmatrix}
0      & 2      & 4      & \infty & 3 \\
2      & 0      & 8      & \infty & 1 \\
6      & 2      & 0      & 4      & 3 \\
1      & \infty & \infty & 0      & 5 \\
\infty & \infty & \infty & 1      & 0 \\
\end{bmatrix}
$$


::::

:::: column

## Que vaut $D^{(1)}$ (3min)?

. . .

$$
D^{(1)}=\begin{bmatrix}
0      & 2          & 4               & \infty & 3 \\
2      & 0          & \mathbf{6}      & \infty & 1 \\
6      & 2          & 0               & 4      & 3 \\
1      & \mathbf{3} & \mathbf{5}      & 0      & \mathbf{4} \\
\infty & \infty     & \infty          & 1      & 0 \\
\end{bmatrix}
$$

## Exemple

$$
D_{42}^{(1)}=D_{41}^{(0)}+D_{12}^{(0)}=1+2<\infty.
$$

::::

:::

# Algorithme de Floyd--Warshall (exemple)

::: columns

:::: column

## On part de $D^{(1)}$

$$
D^{(1)}=\begin{bmatrix}
0      & 2          & 4      & \infty & 3 \\
2      & 0          & 6      & \infty & 1 \\
6      & 2          & 0      & 4      & 3 \\
1      & 3          & 5      & 0      & 4 \\
\infty & \infty     & \infty & 1      & 0 \\
\end{bmatrix}
$$


::::

:::: column

## Que vaut $D^{(2)}$ (3min)?

. . .

$$
D^{(2)}=\begin{bmatrix}
0          & 2          & 4      & \infty & 3 \\
2          & 0          & 6      & \infty & 1 \\
\mathbf{4} & 2          & 0      & 4      & 3 \\
1          & 3          & 5      & 0      & 4 \\
\infty     & \infty     & \infty & 1      & 0 \\
\end{bmatrix}
$$

::::

:::

# Algorithme de Floyd--Warshall (exemple)

::: columns

:::: column

## On part de $D^{(2)}$

$$
D^{(2)}=\begin{bmatrix}
0          & 2          & 4      & \infty & 3 \\
2          & 0          & 6      & \infty & 1 \\
4          & 2          & 0      & 4      & 3 \\
1          & 3          & 5      & 0      & 4 \\
\infty     & \infty     & \infty & 1      & 0 \\
\end{bmatrix}
$$


::::

:::: column

## Que vaut $D^{(3)}$ (3min)?

. . .

$$
D^{(3)}=\begin{bmatrix}
0          & 2          & 4      & \mathbf{8}  & 3 \\
2          & 0          & 6      & \mathbf{10} & 1 \\
4          & 2          & 0      & 4           & 3 \\
1          & 3          & 5      & 0           & 4 \\
\infty     & \infty     & \infty & 1           & 0 \\
\end{bmatrix}
$$

::::

:::

# Algorithme de Floyd--Warshall (exemple)

::: columns

:::: column

## On part de $D^{(3)}$

$$
D^{(3)}=\begin{bmatrix}
0          & 2          & 4      & 8  & 3 \\
2          & 0          & 6      & 10 & 1 \\
4          & 2          & 0      & 4  & 3 \\
1          & 3          & 5      & 0  & 4 \\
\infty     & \infty     & \infty & 1  & 0 \\
\end{bmatrix}
$$

::::

:::: column

## Que vaut $D^{(4)}$ (3min)?

. . .

$$
D^{(4)}=\begin{bmatrix}
0          & 2          & 4         & 8  & 3 \\
2          & 0          & 6         & 10 & 1 \\
4          & 2          & 0         & 4  & 3 \\
1          & 3          & 5         & 0  & 4 \\
\mathbf{2} & \mathbf{4} & \mathbf{6} & 1  & 0 \\
\end{bmatrix}
$$

::::

:::

# Algorithme de Floyd--Warshall (exemple)

::: columns

:::: column

## On part de $D^{(4)}$

$$
D^{(4)}=\begin{bmatrix}
0          & 2          & 4         & 8  & 3 \\
2          & 0          & 6         & 10 & 1 \\
4          & 2          & 0         & 4  & 3 \\
1          & 3          & 5         & 0  & 4 \\
2          & 4          & 6         & 1  & 0 \\
\end{bmatrix}
$$

::::

:::: column

## Que vaut $D^{(5)}$ (3min)?

. . .

$$
D^{(5)}=\begin{bmatrix}
0          & 2          & 4         & \mathbf{4} & 3 \\
2          & 0          & 6         & \mathbf{2} & 1 \\
4          & 2          & 0         & 4          & 3 \\
1          & 3          & 5         & 0          & 4 \\
2          & 4          & 6         & 1          & 0 \\
\end{bmatrix}
$$

::::

:::

# Algorithme de Floyd--Warshall

## The pseudo-code (10min)

* Quelle structure de données?
* Quelle initialisation?
* Quel est le code pour le calcul de la matrice $D$?

# Algorithme de Floyd--Warshall

## The pseudo-code

* Quelle structure de données?

```C
int distance[n][n];
```

. . .

* Quelle initialisation?

```C
matrice ini_floyd_warshall(distance, n, w)
    pour i de 1 à n
        pour j de 1 à n
            distance[i][j] = w(i,j)
    retourne distance
```

# Algorithme de Floyd--Warshall

## The pseudo-code

* Quel est le code pour le calcul de la matrice $D$?

```C
matrice floyd_warshall(distance, n, w)
    pour k de 1 à n
        pour i de 1 à n
            pour j de 1 à n
                distance[i][j] = min(distance[i][j], 
                    distance[i][k] + distance[k][j])
    retourne distance
```

# Algorithme de Floyd--Warshall

## La matrice de précédence

* On a pas encore vu comment reconstruire le plus court chemin!
* On définit, $P_{ij}^{(k)}$, qui est le prédécesseur du sommet $j$ depuis $i$ avec les sommets intermédiaires $\in\{1, 2, ..., k\}$.
$$
P^{(0)}_{ij}=\left\{
\begin{array}{ll}
         \mbox{vide}, & \mbox{si } i=j\mbox{, ou }w(i,j)=\infty\\
         i, & \mbox{sinon}.
\end{array}
\right.
$$

* Mise à jour
$$
P^{(k)}_{ij}=\left\{
\begin{array}{ll}
         P^{(k-1)}_{\mathbf{i}j}, & \mbox{si } d_{ij}^{(k)}\leq d_{ik}^{(k-1)}+d_{kj}^{(k-1)}\\
         P^{(k-1)}_{\mathbf{k}j}, & \mbox{sinon}.
\end{array}
\right.
$$

. . .

* Moralité: si le chemin est plus court en passant par $k$, alors il faut utiliser son prédécesseur!

# Algorithme de Floyd--Warshall

## La matrice de précédence (pseudo-code, 3min)

. . .

```C
matrice, matrice floyd_warshall(distance, n, w)
    pour k de 1 à n
        pour i de 1 à n
            pour j de 1 à n
                n_distance = distance[i][k] + distance[k][j]
                if n_distance < distance[i][j]
                    distance[i][j] = n_distance
                    précédence[i][j] = précédence[k][j]
    retourne distance, précédence
```

# Algorithme de Floyd--Warshall (exercice)


::: columns

:::: column

![Le graphe, $D=w$.](figs/floyd_exemple.png)


::::

:::: column

## Que vaut $P^{(0)}$ (3min)?

. . .

$$
P^{(0)}=\begin{bmatrix}
-          & 1          & 1         & -          & 1 \\
2          & -          & 2         & -          & 2 \\
3          & 3          & -         & 3          & 3 \\
4          & -          & -         & -          & 4 \\
-          & -          & -         & 5          & - \\
\end{bmatrix}
$$

::::

:::

# Algorithme de Floyd--Warshall (exercice)


::: columns

:::: column

![Le graphe, $D=w$.](figs/floyd_exemple.png)


::::

:::: column

## Que vaut $P^{(5)}$ (10min)?

. . .

$$
P^{(5)}=\begin{bmatrix}
-          & 1          & 1         & 5          & 1 \\
2          & -          & 1         & 5          & 2 \\
2          & 3          & -         & 3          & 3 \\
4          & 1          & 1         & -          & 1 \\
4          & 1          & 1         & 5          & - \\
\end{bmatrix}
$$

::::

:::

# Exercice: retrouver le chemin entre 1 et 4 (5min)

$$
P=\begin{bmatrix}
-          & 1          & 1         & 5          & 1 \\
2          & -          & 1         & 5          & 2 \\
2          & 3          & -         & 3          & 3 \\
4          & 1          & 1         & -          & 4 \\
4          & 1          & 1         & 5          & - \\
\end{bmatrix}
$$

. . .

## Solution

* Le sommet $5=P_{14}$, on a donc, $5\rightarrow 4$, on veut connaître le prédécesseur de 5.
* Le sommet $1=P_{15}$, on a donc, $1\rightarrow 5\rightarrow 4$. The end.

# Exercice complet

## Appliquer l'algorithme de Floyd--Warshall au graphe suivant

![The exorcist.](figs/floyd_exercice.png){width=50%}

* Bien indiquer l'état de $D$ et $P$ à chaque étape!
* Ne pas oublier de faire la matrice d'adjacence évidemment...

# La suite

* Sans transition.... la suite!

# Trouver un réseau électrique pour

![Ces maisons n'ont pas d'électricité.](figs/arbre_couvrant_vide.png)

# Solution: pas optimale

![Le réseau simple, mais nul.](figs/arbre_couvrant_mal.png)

* La longueur totale des câbles est super longue!

# Solution: optimale

![Le meilleur réseau.](figs/arbre_couvrant_bien.png)

# Formalisation: Les arbres couvrants

## Application: minimisation des coûts

* Équipement d'un lotissement avec des lignes électriques/téléphoniques, des canalisations, ...

. . .

* Pour réduire les coûts, on cherche à minimiser la longueur totale des câbles/tuyaux.

. . .

* Les lignes/tuyaux forment un *arbre couvrant*.

. . .

* La meilleure option est un *arbre couvrant minimal*.


# Formalisation: Les arbres couvrants

* Qu'est-ce qu'un arbre couvrant? Des idées? De quel objet on part? Où va-t-on?

. . .

* Un arbre couvrant d'un graphe non-orienté et connexe est:
    * un arbre inclus dans le graphe qui connecte tous les sommets du graphe.

. . .

![Exemple d'arbres couvrants d'un graphe connexe.](figs/arbre_couvrant_exemples.png)

# Arbres couvrants

* Quels algorithmes que nous avons déjà vus permettent de construire des arbres couvrants?

. . .

* Les parcours en largeur et en profondeur!

. . .

![Graphe, et parcours comme arbres couvrants.](figs/arbres_couvrants_parcours.png)

# Arbres couvrants minimaux

* Un *arbre couvrant minimal* est un sous-graphe d'un graphe non-orienté pondéré $G(V,E)$, tel quel:
    * C'est un arbre (graphe acyclique);
    * Il couvre tous les sommets de $G$ et contient $|V|-1$ arêtes;
    * Le coût total associé aux arêtes de l'arbre est minimum parmi tous les arbres couvrants possibles.

. . .

* Est-il unique?

. . .

* Pas forcément.

# Arbres couvrants minimaux

* Comment générer un arbre couvrant minimal?

![Un graphe, connexe, non-orienté, pondéré, et son arbre couvrant minimal.](figs/arbre_couvrant_minimal_exemple.png)

# Algorithme de Prim

::: columns

:::: column

## Un exemple

![Le graphe de départ.](figs/prim_0.png)

::::

:::: column

## On part de `e` (au hasard)

![Le sommet `e` est couvert.](figs/prim_1.png)

::::

:::

# Algorithme de Prim

::: columns

:::: column

## On choisit comment? 

![Quelle arête choisir?](figs/prim_1.png)

. . .

* L'arête la plus courte sortant d'un sommet déjà visité, et entrant dans un sommet non-visité.

::::

:::: column

. . .

## L'arête `e->d`

![Le sommet `d` est couvert.](figs/prim_2.png)

::::

:::

# Algorithme de Prim

::: columns

:::: column

## On choisit comment? 

![Quelle arête choisir?](figs/prim_2.png)

. . .

* L'arête la plus courte sortant d'un sommet déjà visité, et entrant dans un sommet non-visité.

::::

:::: column

. . .

## L'arête `d->a`

![Le sommet `a` est couvert.](figs/prim_3.png)

::::

:::

# Algorithme de Prim

::: columns

:::: column

## On choisit comment? 

![Quelle arête choisir?](figs/prim_3.png)

. . .

* L'arête la plus courte sortant d'un sommet déjà visité, et entrant dans un sommet non-visité.

::::

:::: column

. . .

## L'arête `d->c`

![Le sommet `c` est couvert.](figs/prim_4.png)

::::

:::

# Algorithme de Prim

::: columns

:::: column

## On choisit comment? 

![Quelle arête choisir?](figs/prim_4.png)

. . .

* L'arête la plus courte sortant d'un sommet déjà visité, et entrant dans un sommet non-visité.

::::

:::: column

. . .

## L'arête `e->b`

![Le sommet `b` est couvert.](figs/prim_5.png)

* Game over!

::::

:::

# Algorithme de Prim

## Structures de données

* Dans quoi allons nous stocker les sommets?

. . .

* File de priorité min.
* Autre chose?

. . .

* Tableau des distances (comme pour Dijkstra).
* Autre chose?

. . .

* Tableau des parents (presque comme pour Dijkstra).
* Autre chose?

. . .

* Non.

# Algorithme de Prim

## Initialisation: Pseudo-code (2min)

. . .

```C
file_priorité, distance, parent initialisation(graphe)
    r = aléatoire(graphe)
    distance[r] = 0
    parent[r] = indéfini
    fp = file_p_vide()
    pour v dans sommets(graphe)
        si v != r
            distance[v] = infini
            parent[v]   = indéfini
        fp = enfiler(fp, v, distance[v])
    retourne fp, distance, parent
```

# Algorithme de Prim

## Algorithme: Pseudo-code (5min)

. . .

```C
sommets, parent prim(file_priorité, distance, parent)
    sommets = vide
    tant que !est_vide(file_priorité)
        u, fp = défiler(file_priorité)
        sommets = insérer(sommets, u)
        pour v dans voisinage de u et pas dans sommets 
        // ou dans file_priorité
            si w(u, v) < distance[v]
                parent[w] = u
                distance[w] = w(u, v)
                fp = changer_priorité(fp, w, w(u, v))
    retourne sommets, parent
```

# Exemple d'algorithme de Prim

::: columns

:::: {.column width="40%"}

## Un exemple

![Étape 1.](figs/prim_1.png)

::::

:::: column

```
FP |  e  |  d  |  b  |  c  |  a  |
----------------------------------
D  |  0  | inf | inf | inf | inf |

   |  e  |  d  |  b  |  c  |  a  |
----------------------------------
P  |  -  |  -  |  -  |  -  |  -  |
```

## Devient?

. . .

```
FP |  d  |  b  |  c  |  a  |
----------------------------
D  |  4  |  5  |  5  | inf |

   |  e  |  d  |  b  |  c  |  a  |
----------------------------------
P  |  -  |  e  |  e  |  e  |  -  |
```

::::

:::

# Exemple d'algorithme de Prim

::: columns

:::: {.column width="40%"}

## Un exemple

![Étape 2.](figs/prim_2.png)

::::

:::: column

```
FP |  d  |  b  |  c  |  a  |
----------------------------
D  |  4  |  5  |  5  | inf |

   |  e  |  d  |  b  |  c  |  a  |
----------------------------------
P  |  -  |  e  |  e  |  e  |  -  |
```

## Devient?

. . .

```
FP |  a  |  c  |  b  |
----------------------
D  |  2  |  4  |  5  |

   |  e  |  d  |  b  |  c  |  a  |
----------------------------------
P  |  -  |  e  |  e  |  d  |  d  |
```

::::

:::

# Exemple d'algorithme de Prim

::: columns

:::: {.column width="40%"}

## Un exemple

![Étape 3.](figs/prim_3.png)

::::

:::: column

```
FP |  a  |  c  |  b  |
----------------------
D  |  2  |  4  |  5  |

   |  e  |  d  |  b  |  c  |  a  |
----------------------------------
P  |  -  |  e  |  e  |  d  |  d  |
```

## Devient?

. . .

```
FP |  c  |  b  |
----------------
D  |  4  |  5  |

   |  e  |  d  |  b  |  c  |  a  |
----------------------------------
P  |  -  |  e  |  e  |  d  |  d  |
```

::::

:::

# Exemple d'algorithme de Prim

::: columns

:::: {.column width="40%"}

## Un exemple

![Étape 4.](figs/prim_4.png)

::::

:::: column

```
FP |  c  |  b  |
----------------
D  |  4  |  5  |

   |  e  |  d  |  b  |  c  |  a  |
----------------------------------
P  |  -  |  e  |  e  |  d  |  d  |
```

## Devient?

. . .

```
FP |  b  |
----------
D  |  5  |

   |  e  |  d  |  b  |  c  |  a  |
----------------------------------
P  |  -  |  e  |  e  |  d  |  d  |
```

::::

:::

# Exemple d'algorithme de Prim

::: columns

:::: {.column width="40%"}

## Un exemple

![Étape 5.](figs/prim_4.png)

::::

:::: column

```
FP |  b  |
----------
D  |  5  |

   |  e  |  d  |  b  |  c  |  a  |
----------------------------------
P  |  -  |  e  |  e  |  d  |  d  |
```

## Devient?

. . .

```
FP |
----
D  |

   |  e  |  d  |  b  |  c  |  a  |
----------------------------------
P  |  -  |  e  |  e  |  d  |  d  |
```

::::

:::

# Exercice: algorithme de Prim

## Appliquer l'algorithme de Prim à (15min):

![En démarrant du sommet $V_1$.](figs/prim_exercice.png)

# Exercice: algorithme de Prim

## Solution

![](figs/prim_solution.png)

# Complexité de l'algorithme de Prim

\footnotesize

```C
file_priorité, distance, parent initialisation(graphe)
    // choix r et initialisation
    pour v dans sommets(graphe)
O(|V|)  // initialisation distance et parent
        fp = enfiler(fp, v, distance[v])
    retourne fp, distance, parent
sommets, parent prim(file_priorité, distance, parent)
    sommets = vide
    tant que !est_vide(file_priorité)
O(|V|)  u, fp = défiler(file_priorité)
        sommets = insérer(sommets, u)
        pour v dans voisinage de u et pas dans sommets
    O(|E|)  si w(u, v) < distance[v]
                // màj dista + parent
        O(|V|)  fp = changer_priorité(fp, w, w(u, v))
    retourne sommets, parent
```

* $O(|V|)+O(|E|)+O(|V|^2)=O(|E|+|V|^2)$
* Remarque: $O(|E|)$ n'est pas mutliplié par $O(|V|)$, car les arêtes parcourues qu'une fois en **tout**.