Kursliste Logg inn

Informasjon

Forfatter(e) Alexis Englebert
Frist Ingen frist
Innleveringsgrense Ingen begrensning

Logg inn

Logg inn

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 :

  1. Implémenter l'algorithme de Dijkstra de manière naïve dans un graphe non-orienté.
  2. 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é.

https://inginious.info.ucl.ac.be/course/LINFO1114/plus_court_chemin/graph_example.png 
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\) :

  1. \(v :=\) un élément de \(\bar{N_s}\) qui minimise \(d(v)\) ;
  2. \(N_s := N_s \cup \{v\}\) ;
  3. pour tout \(i \in \bar{N_s}\) : \(d(i) := \min\big(d(i),\; d(v) + c(v, i)\big)\).
Spørsmål 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.
Spørsmål 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.

https://inginious.info.ucl.ac.be/course/LINFO1114/plus_court_chemin/graph_fiabilite.png

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}\).