--- 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  :::: :::: 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  :::: :::: 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 & 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 {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  # Solution: pas optimale  * La longueur totale des câbles est super longue! # Solution: optimale  # 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. . . .  # 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) . . . ```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  :::: :::: 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 ```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**.