---
title: "Graphes - Plus court chemin"
date: "2023-06-02"
---

# Rappel du dernier cours

* Qu'est-ce qu'un graphe? Un graphe orienté? Un graphe pondéré?

. . .

* Ensemble de sommets et arêtes, avec une direction, possédant une pondération.
* Comment représenter un graphe informatiquement?

. . .

* Liste ou matrice d'adjacence.
* Quel est le parcours que nous avons vu?

. . .

* Le parcours en largeur.

# Le parcours en largeur

## Le pseudo-code

* Utilisation d'une **file**

```C
initialiser(graphe) // tous sommets sont non-visités
file = visiter(sommet, vide) // sommet est un sommet 
                             // du graphe
tant que !est_vide(file)
    v = defiler(file)
    file = visiter(v, file)

file visiter(sommet, file)
    sommet = visité
    pour w = chaque arête de sommet
        si w != visité
            file = enfiler(file, w)
    retourne file
```

# Complexité du parcours en largeur

## Étape 1

* Extraire un sommet de la file;

## Étape 2

* Traîter tous les sommets adjacents.

## Quelle est la complexité?

. . .

* Étape 1: $\mathcal{O}(|V|)$,
* Étape 2: $\mathcal{O}(2|E|)$,
* Total: $\mathcal{O}(|V| + 2|E|)$.

# Exercice

* Établir la liste d'adjacence et appliquer l'algorithme de parcours en largeur au graphe

```{.mermaid format=pdf width=400 loc=figs/}
graph LR;
    1---2;
    1---3;
    1---4;
    2---3;
    2---6;
    3---6;
    3---4;
    3---5;
    4---5;
```


# Illustration: parcours en profondeur

![Le parcours en profondeur. À quel parcours d'arbre cela ressemble-t-il?](figs/parcours_prof.pdf){width=80%}

# Parcours en profondeur

## Idée générale

* Initialiser les sommets comme non-lus
* Visiter un sommet
* Pour chaque sommet visité, on visite un sommet adjacent s'il est pas encore visité récursivement.

## Remarque

* La récursivité est équivalent à l'utilisation d'une **pile**.

# Parcours en profondeur

## Pseudo-code (5min)

. . .

```C
initialiser(graphe) // tous sommets sont non-visités
pile = visiter(sommet, vide) // sommet est un 
                             // sommet du graphe
tant que !est_vide(pile)
    v = dépiler(pile)
    pile = visiter(v, pile)
```

## Que fait visiter?

. . .

```C
pile visiter(sommet, pile)
    sommet = visité
    pour w = chaque arête de sommet
        si w != visité
            pile = empiler(pile, w)
    retourne pile
```


# Exercice

* Établir la liste d'adjacence et appliquer l'algorithme de parcours en profondeur au graphe

```{.mermaid format=pdf width=400 loc=figs/}
graph LR;
    1---2;
    1---3;
    1---4;
    2---3;
    2---6;
    3---6;
    3---4;
    3---5;
    4---5;
```

# Interprétation des parcours

* Un graphe vu comme espace d'états (sommet: état, arête: action);
    * Labyrinthe;
    * Arbre des coups d'un jeu.

. . .

* BFS (Breadth-First) ou DFS (Depth-First) parcourent l'espace des états à la recherche du meilleur mouvement.
    * Les deux parcourent *tout* l'espace;
    * Mais si l'arbre est grand, l'espace est gigantesque!

. . .

* Quand on a un temps limité
    * BFS explore beaucoup de coups dans un futur proche;
    * DFS explore peu de coups dans un futur lointain.


## Contexte: les réseaux (informatique, transport, etc.)

* Graphe orienté;
* Source: sommet `s`;
* Destination: sommet `t`;
* Les arêtes ont des poids (coût d'utilisation, distance, etc.);
* Le coût d'un chemin est la somme des poids des arêtes d'un chemin.

## Problème à résoudre

* Quel est le plus court chemin entre `s` et `t`.

# Exemples d'application de plus court chemin

## Devenir riches!

* On part d'un tableau de taux de change entre devises.
* Quelle est la meilleure façon de convertir l'or en dollar?

![Taux de change.](figs/taux_change.pdf){width=80%}

. . .

* 1kg d'or => 327.25 dollars
* 1kg d'or => 208.1 livres => 327 dollars
* 1kg d'or => 455.2 francs => 304.39 euros => 327.28 dollars

# Exemples d'application de plus court chemin

## Formulation sous forme d'un graphe: Comment (3min)?

![Taux de change.](figs/taux_change.pdf){width=80%}


# Exemples d'application de plus court chemin

## Formulation sous forme d'un graphe: Comment (3min)?

![Graphes des taux de change.](figs/taux_change_graphe.pdf){width=60%}

* Un sommet par devise;
* Une arête orientée par transaction possible avec le poids égal au taux de change;
* Trouver le chemin qui maximise le produit des poids.

. . .

## Problème

* On aimerait plutôt avoir une somme...


# Exemples d'application de plus court chemin

## Conversion du problème en plus court chemin

* Soit `taux(u, v)` le taux de change entre la devise `u` et `v`.
* On pose `w(u,w)=-log(taux(u,v))`
* Trouver le chemin poids minimal pour les poids `w`.

![Graphe des taux de change avec logs.](figs/taux_change_graphe_log.pdf){width=60%}

* Cette conversion se base sur l'idée que

$$
\log(u\cdot v)=\log(u)+\log(v).
$$

# Applications de plus courts chemins

## Quelles applications voyez-vous?

. . .

* Déplacement d'un robot;
* Planificaiton de trajet / trafic urbain;
* Routage de télécommunications;
* Réseau électrique optimal;
* ...

# Plus courts chemins à source unique

* Soit un graphe, $G=(V, E)$, une fonction de pondération $w:E\rightarrow\mathbb{R}$, et un sommet $s\in V$
  * Trouver pour tout sommet $v\in V$, le chemin de poids minimal reliant $s$ à $v$.
* Algorithmes standards:
  * Dijkstra (arêtes de poids positif seulement);
  * Bellman-Ford (arêtes de poids positifs ou négatifs, mais sans cycles).
* Comment résoudre le problèmes si tous les poids sont les mêmes?

. . .

* Un parcours en largeur!

# Algorithme de Dijkstra

## Comment chercher pour un plus court chemin?

. . .

```
si distance(u,v) > distance(u,w) + distance(w,v)
    on passe par w plutôt qu'aller directement
```

# Algorithme de Dijkstra (1 à 5)

* $D$ est le tableau des distances au sommet $1$: $D[7]$ est la distance de 1 à 7.
* Le chemin est pas forcément direct.
* $S$ est le tableau des sommets visités.

::: columns

:::: column

![Initialisation.](figs/dijkstra_0.png)

::::

:::: column

. . .

![1 visité, `D[2]=1`, `D[4]=3`.](figs/dijkstra_1.png)

::::

:::

# Algorithme de Dijkstra (1 à 5)

::: columns

:::: column

![Plus court est 2.](figs/dijkstra_1.png)


::::

:::: column

. . .

![2 visité, `D[3]=2`, `D[7]=3`.](figs/dijkstra_2.png)

::::

:::

# Algorithme de Dijkstra (1 à 5)

::: columns

:::: column

![Plus court est 3.](figs/dijkstra_2.png)


::::

:::: column

. . .

![3 visité, `D[7]=3` inchangé, `D[6]=6`.](figs/dijkstra_3.png)

::::

:::

# Algorithme de Dijkstra (1 à 5)


::: columns

:::: column

![Plus court est 4 ou 7.](figs/dijkstra_3.png)


::::

:::: column

. . .

![4 visité, `D[7]=3` inchangé, `D[5]=9`.](figs/dijkstra_4.png)

::::

:::

# Algorithme de Dijkstra (1 à 5)

::: columns

:::: column

![Plus court est `7`.](figs/dijkstra_4.png)


::::

:::: column

. . .

![7 visité, `D[5]=7`, `D[6]=6` inchangé.](figs/dijkstra_5.png)

::::

:::

# Algorithme de Dijkstra (1 à 5)

::: columns

:::: column

![Plus court est 6.](figs/dijkstra_5.png)


::::

:::: column

. . .

![`6` visité, `D[5]=7` inchangé.](figs/dijkstra_6.png)

::::

:::

# Algorithme de Dijkstra (1 à 5)

::: columns

:::: column

![Plus court est 5 et c'est la cible.](figs/dijkstra_6.png)

::::

:::: column

. . .

![The end, tous les sommets ont été visités.](figs/dijkstra_7.png)

::::

:::

# Algorithme de Dijkstra

## Idée générale

* On assigne à chaque noeud une distance $0$ pour $s$, $\infty$ pour les autres.
* Tous les noeuds sont marqués non-visités.
* Depuis du noeud courant, on suit chaque arête du noeud vers un sommet non visité et on calcule le poids du chemin à chaque voisin et on met à jour sa distance si elle est plus petite que la distance du noeud.
* Quand tous les voisins du noeud courant ont été visités, le noeud est mis à visité (il ne sera plus jamais visité).
* Continuer avec le noeud à la distance la plus faible.
* L'algorithme est terminé losrque le noeud de destination est marqué comme visité, ou qu'on a plus de noeuds qu'on peut visiter et que leur distance est infinie.

# Algorithme de Dijkstra

## Pseudo-code (5min, matrix)

\footnotesize

. . .

```C
tab dijkstra(graph, s, t)
    pour chaque v dans graphe
        distance[v] = infini
        q = ajouter(q, v)
    distance[s] = 0
    tant que non_vide(q)
    // sélection de u t.q. la distance dans q est min
        u = min(q, distance)
        si u == t // on a atteint la cible
            retourne distance
        q = remove(q, u)
        // voisin de u encore dans q
        pour chaque v dans voisinage(u, q)
        // on met à jour la distance du voisin en passant par u 
            n_distance = distance[u] + w(u, v)
            si n_distance < distance[v]
                distance[v] = n_distance
    retourne distance
```

# Algorithme de Dijkstra

* Cet algorithme, nous donne le plus court chemin mais...
* ne nous donne pas le chemin!

## Comment modifier l'algorithme pour avoir le chemin?

. . .

* Pour chaque nouveau noeud à visiter, il suffit d'enregistrer d'où on est venu!
* On a besoin d'un tableau `precedent`.

## Modifier le pseudo-code ci-dessus pour ce faire (3min matrix)

# Algorithme de Dijkstra

\footnotesize

```C
tab, tab dijkstra(graph, s, t)
    pour chaque v dans graphe
        distance[v] = infini
        precedent[v] = indéfini
        q = ajouter(q, v)
    distance[s] = 0
    tant que non_vide(q)
    // sélection de u t.q. la distance dans q est min
        u = min(q, distance) 
        si u == t
            retourne distance
        q = remove(q, u)
        // voisin de u encore dans q
        pour chaque v dans voisinage(u, q) 
            n_distance = distance[u] + w(u, v)
            si n_distance < distance[v]
                distance[v] = n_distance
                precedent[v] = u
    retourne distance, precedent
```

# Algorithme de Dijkstra

## Comment reconstruire un chemin ?

. . .

```C
pile parcours(precedent, s, t)
    sommets = vide
    u = t
    // on a atteint t ou on ne connait pas de chemin
    si u != s && precedent[u] != indéfini 
        tant que vrai 
            sommets = empiler(sommets, u)
            u = precedent[u]
            si u == s // la source est atteinte
                retourne sommets
    retourne sommets
```

# Algorithme de Dijkstra amélioré

## On peut améliorer l'algorithme

* Avec une file de priorité!

## Une file de priorité est

* Une file dont chaque élément possède une priorité,
* Elle existe en deux saveurs: `min` ou `max`:
    * File `min`: les éléments les plus petits sont retirés en premier.
    * File `max`: les éléments les plus grands sont retirés en premier.
* On regarde l'implémentation de la `max`.

## Comment on fait ça?

. . .

* On insère les éléments à haute priorité tout devant dans la file!

# Les files de priorité

## Trois fonction principales

```C
booléen est_vide(element) // triviale
element enfiler(element, data, priorite)
data defiler(element)
rien changer_priorite(element, data, priorite)
nombre priorite(element) // utilitaire
```

## Pseudo-implémentation: structure (1min)

. . .

```C
struct element
    data
    priorite
    element suivant
```

# Les files de priorité

## Pseudo-implémentation: enfiler (2min)

. . .

```C
element enfiler(element, data, priorite)
    n_element = creer_element(data, priorite)
    si est_vide(element)
        retourne n_element
    si priorite(n_element) > priorite(element)
        n_element.suivant = element
        retourne n_element
    sinon
        tmp = element
        prec = element
        tant que !est_vide(tmp) && priorite < priorite(tmp)
            prec = tmp
            tmp = tmp.suivant
        prev.suivant = n_element
        n_element.suivant = tmp
        retourne element           
```

# Les files de priorité

## Pseudo-implémentation: defiler (2min)

. . .

```C
data, element defiler(element)
    si est_vide(element)
        retourne AARGL!
    sinon
        tmp = element.data
        n_element = element.suivant
        liberer(element)
        retourne tmp, n_element
```

# Algorithme de Dijkstra avec file de priorité min

```C
distance, precedent dijkstra(graphe, s, t):
    distance[source] = 0
    fp = file_p_vide()
    pour v dans sommets(graphe)
        si v != s
            distance[v] = infini
            precedent[v] = indéfini
        fp = enfiler(fp, v, distance[v])
    tant que !est_vide(fp)
        u, fp = defiler(fp)
        pour v dans voisinage de u
            n_distance = distance[u] + w(u, v)
            si n_distance < distance[v]
                distance[v] = n_distance
                precedent[v] = u
                fp = changer_priorite(fp, v, n_distance)
    retourne distance, precedent
```

# Algorithme de Dijkstra avec file

\footnotesize

```C
distance dijkstra(graphe, s, t)
---------------------------------------------------------
    pour v dans sommets(graphe)
O(V)    si v != s
            distance[v] = infini
O(V)        fp = enfiler(fp, v, distance[v]) // notre impl est nulle
------------------O(V * V)-------------------------------
    tant que !est_vide(fp)
O(1)    u, fp = defiler(fp)
---------------------------------------------------------
O(E)    pour v dans voisinage de u
            n_distance = distance[u] + w(u, v)
            si n_distance < distance[v]
                distance[v] = n_distance
O(V)            fp = changer_priorite(fp, v, n_distance)
---------------------------------------------------------
    retourne distance
```

* Total: $\mathcal{O}(|V|^2+|E|\cdot |V|)$:
    * Graphe dense: $\mathcal{O}(|V|^3)$ 
    * Graphe peu dense: $\mathcal{O}(|V|^2)$ 

# Algorithme de Dijkstra avec file

## On peut faire mieux

* Avec une meilleure implémentation de la file de priorité:
    * Tas binaire: $\mathcal{O}(|V|\log|V|+|E|\log|V|)$.
    * Tas de Fibonnacci: $\mathcal{O}(|V|+|E|\log|V|)$
* Graphe dense: $\mathcal{O}(|V|^2\log|V|)$.
* Graphe peu dense: $\mathcal{O}(|V|\log|V|)$.

# Algorithme de Dijkstra (exercice, 5min) 

![L'exercice.](figs/dijkstra_exo.png){width=60%}

* Donner la liste de priorité, puis...

## A chaque étape donner:

* Le tableau des distances à `a`;
* Le tableau des prédécesseurs;
* L'état de la file de priorité.

# Algorithme de Dijkstra (corrigé) 

![Le corrigé partie 1.](figs/dijkstra_ex_0.png)

# Algorithme de Dijkstra (corrigé) 

![Le corrigé partie 2.](figs/dijkstra_ex_1.png)

# Algorithme de Dijkstra (corrigé) 

![Le corrigé partie 3.](figs/dijkstra_ex_2.png)

# Algorithme de Dijkstra (corrigé) 

![Le corrigé partie 4.](figs/dijkstra_ex_3.png)

# Algorithme de Dijkstra (corrigé) 

![Le corrigé partie 5.](figs/dijkstra_ex_4.png)

# Algorithme de Dijkstra (corrigé) 

![Le corrigé partie 6.](figs/dijkstra_ex_5.png)

# Limitation de l'algorithme de Dijkstra

## Que se passe-t-il pour?

![Exemple.](figs/exemple_neg.png){width=50%}

## Quel est le problème?

. . .

* L'algorithme n'essaiera jamais le chemin `s->x->y->v` et prendra direct `s->v`.
* Ce problème n'apparaît que s'il y a des poids négatifs.