Résultats pour « graphe orienté »
DS MP - Réseau de distribution d'eau - Analyse de graphes orientés pondérés
Une ville souhaite modéliser son réseau de distribution d'eau. Le réseau est représenté par un graphe orienté pondéré où : les sommets représentent des nœuds du réseau (châteaux d'eau, jonctions, quartiers), les arêtes orientées représentent des canalisations avec une capacité maximale (en litres/seconde).
Détecter un cycle dans un graphe orienté et non orienté
L’idée est simple : pour vérifier l’existence d’un cycle dans un graphe, il suffit de déterminer s’il existe, pour un sommet v, un chemin qui part de v et y revient ; si un tel chemin existe, alors le graphe contient un cycle.
Plus courts chemins entre toutes les paires de sommets dans un graphe orienté et pondéré - Algorithme Floyd-Warshall
L'algorithme de Floyd-Warshall change de paradigme. Son objectif est de calculer simultanément les distances minimales pour tous les couples de sommets \((i,j)\). C'est un outil indispensable pour l'analyse de réseaux denses (où le nombre d'arêtes \(A\) est proche de \(S^2\)) et pour la détection de structures pathologiques comme les cycles de poids négatifs.