Algorithme de Bellman-Ford

composantes connexes. . . . . . 1 . . . . . . . . 2 7 Quelques algorithmes dans les graphes 7.1 Probl`mes de cheminement. Plus court chemin . . . . . . . . e 7.2 Algorithme de Ford-Bellman . . . . . . . . . . . . . . . . . . 7.2.1 Principe de l’algorithme . . . . . . . . . . . . . . . . . 7.2.2 Complexit´ . . . . . . . . . . . . . . . . . . . . . . . . e 7.2.3 Enonc´ formel de l’algorithme . . . . . . . . . . . . . . e 7.3 Algorithme de Dijkstra . . . . . . . . . . . . . . . . . . . . . . 7.3.1 Principe

Table des matières Statut de ce document Résumé 1 Introduction 1.1 Limitations du protocole . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Organisation de ce document . . . . . . . . . . . . . . . . . . . . . . . . . . . . Algorithmes à vecteurs de distance 2.1 S’accommoder des changements dans la topologie 2.2 Éviter l’instabilité . . . . . . . . . . . . . . . . . . . 2.2.1 Horizon partagé . . . . . . . . . . . . . . . 2.2.2 Mises à jour déclenchées . . . . . . . . . . . Spécifications

la longueur d’un chemin quelconque comme la somme des longueurs des arcs qui le composent. Un problème fondamental, et qui se pose fréquemment dans les applications, est celui de la recherche de chemins de longueur minimale ou maximale. Les algorithmes, permettant d’obtenir de tels chemins, sont utiles pour la recherche de flots et d’ordonnancements optimaux. 1. Formulation du problème Soit G = (X, U) un 1-graphe orienté sans boucle comportant n sommets. A tout arc ( xi , x j )  U est associé

Note La règle (appelée « principe d’optimalité ») commune aux algorithmes de recherche de plus courts chemins peut s’énoncer ainsi : un plus court chemin [S1, Sn] entre deux sommets S1 et Sn d’un graphe est constitué de plus courts chemins reliant deux sommets du chemin [S1, Sn] ; on la démontre par l’absurde sans problème. La recherche du plus court chemin passe donc par la recherche des plus courts chemins reliant S1 à tous les sommets du graphe susceptibles de se trouver sur le trajet ;

alors : � une clique est un sous-graphe (induit) complet de G, � un stable est un sous-graphe induit de G sans arcs/arêtes. Trouver une clique d'ordre k dans un graphe est un problème NP-complet, ce qui implique qu'il n'existe pas à ce jour un algorithme résolvant ce problème de façon exacte avec une complexité polynomiale (elle est exponen- tielle). Le problème consistant à trouver la plus grande clique d'un graphe est appelé � problème de la clique maximum �, et est encore plus di�cile ! (il est

|1 |Haut du formulaire | | |Quel algorithme est exécuté par les protocoles de routage d’état des liaisons pour calculer le chemin le plus | | |court vers les réseaux de destination ?

4.1 Un algorithme de coloration . . . . . . . . . . . . . . . . . 1.4.2 Histoire . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5 Problème de plus court chemin : . . . . . . . . . . . . . . . . . . . 1.5.1 Définitions et propriétés : . . . . . . . . . . . . . . . . . . 1.5.2 Le Cas des graphes sans circuits : Algorithme de Roy (Rang). 1.5.3 Le cas où tous les poids sont positifs : Algorithme de Dijkstra 1.5.4 Le cas où les poids sont de signe quelconque : Algorithme de Ford-Bellman . . .

Exercice Calculer les degrés de tous les sommets du graphe précédent. II. Chemin de longueur minimal ou de longueur maximale 1) Absence de circuit dans un graphe. L’absence de circuit est indispensable pour l’utilisation de plusieurs algorithmes de recherche de chemin optimal. Les hypothèses suivantes doivent être vérifiées :  Pour un problème à maximum, pas de circuits de valeur positive.  Pour un problème à minimum, pas de circuits de valeur négative. Voici un organigramme permettant

........23 C. ALGORITHMES POLYNOMIAUX DE BASE POUR LES GRAPHES................27 1. 2. 3. 4. 5. Définition de la polynomialité :............................................................27 Codage des graphes :.........................................................................29 Algorithme de bonne numérotation d'un graphe :...................................32 Recherche d'un couplage maximal :.....................................................36 Autres algorithmes de graphe :......

Le problème a un sens si G ne contient pas de circuit de coût négatif (appelé circuit absorbant). • On peut alors se limiter aux chemins élémentaires (sans nœuds répétés), avec au plus n - 1 arcs. Cette propriété est exploitée par tous les algorithmes. 21/10/2011 5LDD-AcheminementChemins optimaux 3/25 • Exemples a) PCC dans les réseaux de transport • Nœuds = villes ou carrefours, arcs = routes ou rues, coûts = distances ou temps. • Ces données sont vendues sur CD par l'IGN, Michelin et TeleAtlas*