cours_25.md

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

Questions

• 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.
• Quels sont les deux parcours que nous avons vus?

. . .

• Parcours en largeur et profondeur.
• Donner l'idée générale des deux parcours.

Illustration: plus courts chemins

Plus courts chemins

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?

. . .

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

Les files de priorité

Trois fonction principales

booléen est_vide(élément) // triviale
élément enfiler(élément, data, priorité)
data défiler(élément)
rien modifier_priorité(élément, data, priotié)
nombre priorité(data) // utilitaire

Pseudo-implémentation: structure (1min)

. . .

struct élément
    data
    priorité
    élément suivant

Les files de priorité

Pseudo-implémentation: enfiler (2min)

. . .

élément enfiler(élément, data, priorité)
    n_élément = créer_élément(data, priorité)
    si est_vide(élément)
        retourne n_élément
    si priorité(d) > priorité(e.d)
        n_élément.suivant = élément
        retourne n_élément
    sinon
        tmp = élément
        préc = élément
        tant que !est_vide(tmp) && priorité < tmp.priorité
            préc = tmp
            tmp = tmp.suivant
        prev.suivant = n_élément
        n_élément.suivant = tmp
        retourne élément           

Les files de priorité

Pseudo-implémentation: défiler (2min)

. . .

data, élément défiler(élément)
    si est_vide(élément)
        retourne AARGL!
    sinon
        tmp = élément.data
        n_élément = élément.suivant
        libérer(élément)
        retourne tmp, n_élément

Algorithme de Dijkstra avec file de priorité min

distance, précédent dijkstra(graphe, s, t):
    distance[source] = 0
    fp = file_p_vide()
    pour v dans sommets(graphe)
        si v != s
            distance[v] = infini
            précédent[v] = indéfini
        fp = enfiler(fp, v, distance[v])
    tant que !est_vide(fp)
        u, fp = défiler(fp)
        pour v dans voisinage de u
            n_distance = distance[u] + w(i, v)
            si n_distance < distance[v]
                distance[v] = n_distance
                précédent[v] = u
                fp = changer_priorité(fp, v, n_distance)
    retourne distance, précédent

Algorithme de Dijkstra avec file

\footnotesize

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 = défiler(fp)
---------------------------------------------------------
O(E)    pour v dans voisinage de u
            n_distance = distance[u] + w(i, v)
            si n_distance < distance[v]
                distance[v] = n_distance
O(V)            fp = changer_priorité(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)

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

A chaque étape donner:

• Le tableau des distances à a;
• Le tableau des prédécessueurs;
• L'état de la file de priorité.

Algorithme de Dijkstra (corrigé)

Algorithme de Dijkstra (corrigé)

Algorithme de Dijkstra (corrigé)

Algorithme de Dijkstra (corrigé)

Algorithme de Dijkstra (corrigé)

Algorithme de Dijkstra (corrigé)

Limitation de l'algorithme de Dijkstra

Que se passe-t-il pour?

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.