L'Atelier Monstre

Deux exercices d'algorithmique sur les graphes sont présentés : l'un sur le tri topologique avec vérification de cycle, l'autre sur l'algorithme de Dijkstra pour la recherche du chemin le plus court. Exercice 1 : Tri topologique des tâches Un projet est divisé en n sous-tâches, identifiées de 0 à n-1. Pour achever le projet, toutes les sous-tâc ...

Ce problème concerne un graphe non orienté comportant n sommets et m arêtes pondérées. De plus, il existe k arêtes supplémentaires connectant le sommet 1 à divers autres sommets. L'objectif est de déterminer le nombre maximal d'arêtes parmi ces k arêtes que l'on peut supprimer, tout en garantissant que les distances les plus courtes de tous les ...