cours_24.md

title: "Graphes - Plus court chemin"
date: "2023-05-24"

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

initialiser(graphe) // tous sommets sont non-visités
file = visiter(sommet, vide) // sommet est un sommet du graphe au hasard
tant que !est_vide(file)
    v = défiler(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

graph LR;
    1---2;
    1---3;
    1---4;
    2---3;
    2---6;
    3---6;
    3---4;
    3---5;
    4---5;

Illustration: parcours en profondeur

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)

. . .

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

Que fait visiter?

. . .

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

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?

. . .

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

Exemples d'application de plus court chemin

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

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

• 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

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)

. . .

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)
        u = min(q, distance) // plus petite distance dans q
        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
    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 précédent.

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

Algorithme de Dijkstra

tab, tab dijkstra(graph, s, t)
    pour chaque v dans graphe
        distance[v] = infini
        précédent[v] = indéfini
        q = ajouter(q, v)
    distance[s] = 0
    tant que non_vide(q)
        u = min(q, distance) // plus petite distance dans q
        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
                précédent[v] = u
    retourne distance, précédent

Algorithme de Dijkstra

Comment reconstruire un chemin ?

. . .

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

Algorithme de Dijkstra

::: columns

:::: column

::::

:::: column

. . .

::::

:::

Algorithme de Dijkstra

::: columns

:::: column

::::

:::: column

. . .

::::

:::

Algorithme de Dijkstra

::: columns

:::: column

::::

:::: column

. . .

::::

:::

Algorithme de Dijkstra

::: columns

:::: column

::::

:::: column

. . .

::::

:::

Algorithme de Dijkstra

::: columns

:::: column

::::

:::: column

. . .

::::

:::

Algorithme de Dijkstra

::: columns

:::: column

::::

:::: column

. . .

::::

:::

Algorithme de Dijkstra

::: columns

:::: column

::::

:::: column

. . .

::::

:::

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?