cours_26.md

title: "Graphes - Plus court chemin (2)"
date: "2022-05-03"
patat:
    eval:
        tai:
            command: fish
            fragment: false
            replace: true
        ccc:
            command: fish
            fragment: false
            replace: true
    images:
      backend: auto

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, ditance[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

::::

:::: 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?

int distance[n][n];

. . .

• Quelle initialisation?

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?

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 plusc 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 qu'il soit le prédécesseur!

Algorithme de Floyd--Warshall

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

. . .

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

::::

:::: 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

::::

:::: 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 & 4 & 4 & 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 & 4 & 4 & 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

• 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

Solution: pas optimale

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

Solution: optimale

Formalisation: Les arbres couvrants

Application: minimisation des coûrs

• É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 inclu dans le graphe qui connecte tous les sommets du graphe.

. . .

Arbres couvrants

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

. . .

• Les parcours en largeur et en profondeur!

. . .

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?

Algorithme de Prim

::: columns

:::: column

Un exemple

::::

:::: column

On part de e (au hasard)

::::

:::

Algorithme de Prim

::: columns

:::: column

On choisit comment?

. . .

• 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

::::

:::

Algorithme de Prim

::: columns

:::: column

On choisit comment?

. . .

• 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

::::

:::

Algorithme de Prim

::: columns

:::: column

On choisit comment?

. . .

• 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

::::

:::

Algorithme de Prim

::: columns

:::: column

On choisit comment?

. . .

• 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

::::

:::

• 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)

. . .

file_priorité, distance, parent initalisation(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)

. . .

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

::::

:::: 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

::::

:::: 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

::::

:::: 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

::::

:::: 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

::::

:::: 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):

Exercice: algorithme de Prim

Solution

Complexité de l'algorithme de Prim

\footnotesize

file_priorité, distance, parent initalisation(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.

Algorithme de Kruskal