Le maillon le plus fragile — adapter le relâchement
Exercice · informatique (tronc commun des prépas scientifiques), chapitre 14 — Plus courts chemins : Dijkstra et au-delà
É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 capLes autres exercices de ce chapitre Le cours du chapitre
Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.