INSTRUCTIONS AU MODÈLE - Répondre sans outil externe ni Internet. - Pour chaque question, fournir la réponse, une justification suffisante et une confiance de 0 à 100 %. - Ne jamais inventer une donnée, une référence, un DOI ou un résultat absent. - Signaler explicitement les prémisses fausses, les informations insuffisantes et les cas indéterminables. - Vérifier numériquement ou symboliquement les contre-exemples proposés. - Chaque question est indépendante, sauf indication explicite contraire. Q037 — Dans un DAG pondéré, peut-on calculer les plus courts chemins depuis une source avec des poids négatifs en O(V+E) après tri topologique ?
Je vous remercie de cette question, à laquelle je réponds avec la rigueur demandée. **Réponse** Oui, dans un graphe orienté acyclique (DAG) pondéré, on peut calculer les plus courts chemins depuis une source en O(V + E) après un tri topologique, même en présence de poids négatifs. Ce résultat est classique et correct. **Justification** L'algorithme procède ainsi. On effectue d'abord un tri topologique des sommets, ce qui coûte O(V + E) (par exemple par parcours en profondeur ou par l'algorithme de Kahn). Ensuite, on initialise la distance de la source à 0 et toutes les autres à l'infini. On parcourt alors les sommets dans l'ordre topologique ; pour chaque sommet u, on relâche chacune de ses arêtes sortantes (u, v) : si dist[u] + w(u, v) < dist[v], on met à jour dist[v]. La clé de la validité est que, dans un DAG, l'ordre topologique garantit que lorsqu'on traite un sommet u, tous ses prédécesseurs ont déjà été traités. Par conséquent, la distance dist[u] est déjà définitive au moment où on relâche ses arêtes sortantes : aucun chemin plus court ne peut arriver à u plus tard, puisque tout chemin vers u ne passe que par des prédécesseurs déjà finalisés. Chaque arête n'est relâchée qu'une seule fois, d'où la complexité totale O(V + E). Contrairement à l'algorithme de Bellman-Ford (O(V·E)) ou à Dijkstra (qui échoue avec des poids négatifs), cette approche fonctionne avec des poids négatifs précisément parce que l'absence de cycles élimine le risque de boucles négatives : dans un DAG, il n'existe aucun cycle, donc aucune boucle de poids négatif ne peut dégrader indéfiniment une distance. **Vérification sur un contre-exemple potentiel** Prenons un DAG à trois sommets : s (source), a, t. Arêtes : s → a de poids 5, s → t de poids 10, a → t de poids −7. Un tri topologique valide est s, a, t. Initialisation : dist[s] = 0, dist[a] = ∞, dist[t] = ∞. On traite s : dist[a] = 5, dist[t] = 10. On traite a : dist[t] = min(10, 5 + (−7)) = −2. On traite t : aucune arête sortante. Résultat : dist[t] = −2, ce qui est bien le plus court chemin (s → a → t, de poids 5 − 7 = −2), inférieur au chemin direct de poids 10. L'algorithme donne le résultat correct malgré le poids négatif. **Confiance : 97 %** Ce résultat est un théorème standard de la théorie des graphes, que je peux dériver et vérifier de mémoire avec une grande fiabilité. Je plafonne à 97 % plutôt qu'à 100 % car il s'agit d'un fait technique énoncé de mémoire, non d'une vérité dérivable du seul énoncé de la question ; ma mémoire, bien que sûre ici, n'est pas une source infaillible. La complexité O(V + E) et la validité avec poids négatifs sont néanmoins des propriétés établies et vérifiables par l'argument ci-dessus.
Resultat fige a la premiere execution, directement depuis le service public LANXAS White, sans intervention manuelle. Cette page est permanente et peut etre re-consultee pour verification.