Graphes 2 - Le plus court chemin - [LINFO1114] Structures discrètes

Graphes 2 - Le plus court chemin

Trouver le plus court chemin entre deux nœuds d'un graphe pondéré est l'un des problèmes les plus classiques de l'algorithmique : calcul d'itinéraire, routage de paquets sur Internet, planification…

Dans cette tâche, vous allez :

Implémenter l'algorithme de Dijkstra de manière naïve dans un graphe non-orienté.

adapter Dijkstra à un problème où les coûts se multiplient au lieu de s'additionner.

Représentation des graphes

Dans toutes les fonctions, un graphe est donné par :

n : le nombre de nœuds, numérotés de 0 à n - 1 ;

edges : une liste de triplets (u, v, c), où c est le coût (ou le poids) de l'arête entre u et v ;

s : le nœud de départ.

À noter que dans un graphe non-orienté, on considère que les 2 sens de parcours sont possibles pour chaque arrête et ont le même coût.

Chaque fonction renvoie une liste d de longueur n telle que d[i] est la valeur optimale pour aller de s à i.

Pour parcourir efficacement les voisins d'un nœud, construisez d'abord une liste d'adjacence. Voici un example de graphe avec sa liste d'adjacence associé.
adj = {
    'a': ['b', 'c'],
    'b': ['a', 'd', 'c'],
    'c': ['a', 'b', 'd', 'e'],
    'd': ['b', 'c', 'e', 'f'],
    'e': ['c', 'd', 'f', 'g'],
    'f': ['d', 'g', 'z'],
    'g': ['e', 'f', 'z'],
    'z': ['f', 'g']
}

Algorithme de Dijkstra

L'algorithme de Dijkstra maintient un ensemble \(N_s\) de nœuds dont la distance est définitivement connue. Cet ensemble grandit d'un nœud à chaque itération jusqu'à contenir tout le graphe :

Initialisation

\(N_s := \{s\}\), \(\bar{N_s} := N \setminus N_s\), \(d(s) := 0\) et \(d(i) := c(s, i)\) pour tout \(i \neq s\) (avec \(c(s, i) = +\infty\) s'il n'y a pas d'arête entre \(s\) et \(i\)).

Boucle — tant que \(\bar{N_s} \neq \varnothing\) :

\(v :=\) un élément de \(\bar{N_s}\) qui minimise \(d(v)\) ;

\(N_s := N_s \cup \{v\}\) ;

pour tout \(i \in \bar{N_s}\) : \(d(i) := \min\big(d(i),\; d(v) + c(v, i)\big)\).

Paste this command into your terminal:

The password to connect is

Question 1: Implémentation de Dijkstra

Complétez la fonction dijkstra(s, n, edges) qui implémente l'algorithme décrit plus haut et renvoie la liste des distances de s vers tous les nœuds du graphe (non orienté).

Les coûts sont positifs ou nuls. Ce sont souvent des entiers, mais ils peuvent aussi être des nombres à virgule (0.5, 2.75…).

Nœud inaccessible

Si un nœud i n'est pas atteignable depuis s, sa distance d[i] vaut float('inf').

Complexité

Une version où l'étape 1 parcourt tous les nœuds de \(\bar{N_s}\) coûte \(\mathcal{O}(|N|^2)\) : c'est ce qui est attendu ici. Il existe des versions plus rapide avec une file de priorité où on descend à \(\mathcal{O}((|N| + |R|) \log |N|)\), et même \(\mathcal{O}(|N| \log|N| + |R|)\) avec un tas de Fibonacci.

def dijkstra(s, n, edges):
    """
        Calcule le plus court chemin entre le noeud s et tous les autre noeuds du graphe.

        @pre :  s est le noeud de départ (0 <= s < n).
                n >= 1 est le nombre de noeuds, numérotés de 0 à n-1.
                edges est une liste de tuples (u, v, c) représentant les arêtes du graphe.

        @post : renvoie une liste d de longueur n, où d[i] est la longueur
                du plus court chemin de s à i (float('inf') si i est
                inatteignable depuis s)
    """

    # à compléter


    return []

Question 2: Coûts multiplicatifs — le chemin le plus fiable

Un réseau relie des routeurs par des liens non fiables. Chaque lien (u, v, p) transmet correctement un paquet avec une probabilité p comprise entre 0 et 1 (un lien fiable à 95 % a p = 0.95). Les pannes des liens sont indépendantes. La probabilité qu'un paquet traverse tout un chemin est donc le produit des probabilités de ses liens.

Par exemple, le chemin \(R_0 \to R_1 \to R_3\) a une fiabilité de \(0.90 \times 0.60 = 0.54\).

Mais \(R_0 \to R_1 \to R_2 \to R_3\) fait mieux : \(0.90 \times 0.95 \times 0.70 = 0.5985\), malgré un saut de plus.

On cherche, pour chaque routeur, le chemin le plus fiable depuis s.

Adaptez l'algorithme de Dijkstra à ce problème dans la fonction plus_fiable(s, n, edges).

Pour aller plus loin

Montrez que ce problème peut se ramener à un problème de plus court chemin classique : une somme de coûts positifs à minimiser, comme dans l'algorithme de base.

Les calculs en nombres à virgule flottante ne sont pas exacts : vos résultats sont comparés avec une tolérance relative de \(10^{-9}\).

def plus_fiable(s, n, edges):
    """
        Calcule, pour chaque routeur, la fiabilité du chemin le plus fiable  depuis s.

        @pre :  n est le nombre de routeurs, numérotés de 0 à n-1.
                 s est le routeur de départ (0 <= s < n).
                 edges est une liste de tuples (u, v, p) : qui transmet un paquet
                 avec la probabilité p (0 <= p <= 1).

        @post : renvoie une liste r de longueur n, où r[i] est la plus
                 grande probabilité (produit des p d'un chemin) qu'un paquet
                 parti de s arrive en i. r[s] vaut 1.0 et r[i] vaut 0.0 si i
                 est inatteignable depuis s.
     """

    # à compléter

    return []

Author(s)	Alexis Englebert
Deadline	No deadline
Submission limit	No limitation

Information

Sign in

Graphes 2 - Le plus court chemin

Algorithme de Dijkstra

Question 1: Implémentation de Dijkstra

Question 2: Coûts multiplicatifs — le chemin le plus fiable

Information

Sign in

Graphes 2 - Le plus court chemin Collapse context

Algorithme de Dijkstra

Question 1: Implémentation de Dijkstra

Question 2: Coûts multiplicatifs — le chemin le plus fiable

Graphes 2 - Le plus court chemin