informatique (tronc commun des prépas scientifiques) · Chapitre 14 · Exercice de TD
Le maillon le plus fragile — adapter le relâchement
Plus courts chemins : Dijkstra et au-delà · niveau 2
Énoncé
Adapter l'algorithme de Dijkstra pour trouver un chemin reliant la source aux autres sommets qui maximise la capacité minimale de ses arcs (goulot le plus large).
Corrigé
On modifie l'opérateur d'accumulation (la somme devient un minimum) et l'extraction (on cherche le maximum de capacité provisoire au lieu du minimum de distance) :
def chemin_du_goulot(R: dict, source) -> dict:
cap = {s: 0 for s in R}
cap[source] = float("inf")
a_traiter = set(R)
while a_traiter:
# Extraction du MAXIMUM
s = max(a_traiter, key=lambda x: cap[x])
if cap[s] == 0:
break
a_traiter.remove(s)
# Relâchement adapté
for v in R[s]:
cap[v] = max(cap[v], min(cap[s], R[s][v]))
return cap