Bellman-Ford

Programmation dynamique • Cours-TP 2A

Plus courts chemins dans un graphe orienté - Algorithme de Bellman-Ford

Soit $G = (S, A, w)$ , un graphe orienté et pondéré ci-dessous ne possédant pas de circuits de poids négatif.

Si $i$ représente le nombre de sauts autorisés pour atteindre un sommet et $d_{i} (v)$ la distance du sommet de départ $s_{0}$ au sommet $v$ en effectuant $i$ sauts, alors cela peut se traduit mathématiquement par :

d_{i} (v) = {\begin{matrix} 0 & si i = 0 et v = s_{0} \\ + \infty & si i = 0 et v \neq s_{0} \\ \min (d_{i - 1} (v), \min_{arcs (u,v)} (d_{i - 1} (u) + w (u, v))) & sinon \end{matrix}

Par cette formule, on exprime bien la distance entre $s_{0}$ et $v$ (le poids du chemin minimal) en $i$ saut en fonction des distances de $s_{0}$ à $v$ en $i - 1$ sauts, c'est-à-dire la solution optimale du problème en fonction des solutions optimales des sous-problèmes.

On considère le graphe suivant :

1

Indice

Construire la liste d'adjacence en associant chaque sommet à ses voisins pondérés. Il s'agit de créer une liste de liste de tuple (sommet, poids).

Représenter le graphe orienté et pondéré dessiné ci-dessus sous la forme d'une liste d'adjacence stockée dans la variable g.
2

Indice

Parcourir la structure imbriquée avec les indices des sommets pour extraire les triplets source-cible-poids.

Écrire une fonction ladj_to_triplets(g) qui renvoie la liste des triplets (u, v, poids). Par exemple ladj_to_triplets([[ (1, 3) ]]) renvoie [(0, 1, 3)].
3

Indice

Initialiser les distances à l'infini et la source à zéro puis étudier chaque arête.

Écrire une fonction bellman_ford(g, s0) qui calcule les plus courts chemins depuis la source s0 et renvoie le couple (liste_des_distances, liste_des_prédécesseurs). Par exemple bellman_ford([[ (1, 5) ]], 0) renvoie ([0, 5], [0, 0]).
4

Indice

Parcourir chaque liste de voisins pour accumuler les prédécesseurs pondérés dans une nouvelle structure.

Écrire une fonction pred(g) qui calcule les prédécesseurs pondérés de chaque sommet et renvoie cette structure de données. Par exemple pred([[ (1, 2) ]]) renvoie [[], [(0, 2)]].
5

Indice

Vérifier la mémoire cache avant de calculer la valeur minimale en combinant les appels récursifs sur les prédécesseurs.

Écrire une fonction distance(s, i, s0, pred, memo) qui calcule la distance minimale vers le sommet s en utilisant au plus i arêtes et renvoie ce résultat mémorisé. Par exemple distance(1, 1, 0, [[], [(0, 5)]], {}) renvoie 5.
6

Indice

Itérer sur tous les sommets pour récupérer leurs distances optimales via la fonction de récurrence mémorisée.

Écrire une fonction bellman_ford_desc(g, s0) qui calcule les distances depuis la source s0 et renvoie la liste de ces distances. Se servir des fonctions précédentes ! Par exemple bellman_ford_desc([[ (1, 5) ]], 0) renvoie [0, 5].