Plus courts chemins et coloration : Dijkstra, A*, Floyd-Warshall, exercices corrigés de prépa

Q: Comment fonctionne l'algorithme de Dijkstra ?

Dijkstra calcule les distances d'une source s à tous les sommets d'un graphe dont les poids sont positifs ou nuls. On garde pour chaque sommet une distance provisoire `dist[v]`, 0 pour la source et `INF = float('inf')` ailleurs, et un prédécesseur `pred[v]`. À chaque étape, on fixe le sommet non fixé de plus petite distance provisoire, puis on relâche les arcs qui en partent : si `dist[u] + w < dist[v]`, on remplace `dist[v]` par `dist[u] + w` et `pred[v]` par `u`. Ce choix est sûr parce que tout autre chemin vers ce sommet passe par un sommet non fixé au moins aussi éloigné, et que la suite du chemin a une longueur positive ou nulle. Avec une recherche du minimum parmi tous les sommets, le coût est O(n^2). Avec un tas, où l'on ajoute un couple à chaque amélioration et où l'on ignore à l'extraction un sommet déjà fixé, il descend à O((n + p) log n), bien meilleur pour un graphe peu dense.

Q: Pourquoi Dijkstra ne marche-t-il pas avec des poids négatifs ?

Dijkstra fixe un sommet dès qu'il est le plus proche des sommets non fixés, en supposant qu'aucun chemin plus long au départ ne pourra le rattraper. Un arc de poids négatif peut le rattraper. Avec les arcs 0 → 1 de poids 2, 0 → 2 de poids 3 et 2 → 1 de poids -2, Dijkstra fixe le sommet 1 à la distance 2 avant d'examiner l'arc 2 → 1 ; or le chemin 0, 2, 1 a une longueur 3 + (-2) = 1. Le programme rend 2 sans rien signaler. Ajouter la même constante à tous les poids ne répare rien : un chemin de k arcs gagne k fois la constante, et l'ordre des longueurs change. Sur cet exemple, en ajoutant 2, le chemin rendu devient l'arc direct. Le programme ne demande Dijkstra que pour des graphes pondérés positivement ; l'algorithme de Floyd-Warshall accepte des poids négatifs, pourvu qu'il n'y ait aucun cycle de poids total négatif.

Q: Qu'est-ce que l'algorithme A* et une heuristique admissible ?

A* cherche un plus court chemin vers une seule cible t. Il fait comme Dijkstra, mais fixe à chaque étape le sommet qui minimise g(v) + h(v), où g(v) est la distance provisoire depuis la source et h(v) une estimation de la distance qui reste jusqu'à t, et il s'arrête quand t est fixé. Avec h = 0, c'est Dijkstra. L'heuristique est admissible si elle ne surestime jamais, h(v) ≤ d(v, t) ; elle est consistante si h(u) ≤ w(u, v) + h(v) pour tout arc, avec h(t) = 0, ce qui entraîne l'admissibilité. Avec une heuristique consistante, A* rend la distance (résultat admis), en fixant souvent bien moins de sommets : sur le réseau de pistes du cours, 4 ksour au lieu de 9. Sur une grille à quatre directions de pas 1, la distance de Manhattan est consistante. Une heuristique qui surestime peut faire rendre un chemin trop long.

Q: Comment fonctionne l'algorithme de Floyd-Warshall ?

Floyd-Warshall calcule les distances entre tous les couples de sommets, sur la matrice des poids, avec `INF` sans arc et 0 sur la diagonale. On note d_k(i, j) la plus courte longueur d'un chemin de i à j dont les sommets intermédiaires sont parmi 0, …, k - 1. Un plus court chemin qui a le droit de passer par k n'y passe pas, ou y passe une fois, d'où la récurrence d_(k+1)(i, j) = min (d_k(i, j), d_k(i, k) + d_k(k, j)), valable sans cycle de poids négatif. On ne garde qu'une matrice, mise à jour sur place, et la boucle sur le sommet intermédiaire k est la plus extérieure. Une matrice des successeurs, mise à jour par `S[i][j] = S[i][k]`, permet de reconstruire les chemins. Le coût est Θ (n^3) en temps et O(n^2) en mémoire. Une case négative sur la diagonale révèle un cycle de poids négatif. La matrice donne aussi l'excentricité de chaque sommet et le centre du graphe.

Q: Comment colorer un graphe par un algorithme glouton ?

Une coloration donne à chaque sommet une couleur, de sorte que deux voisins aient des couleurs différentes ; le nombre chromatique χ (G) est le plus petit nombre de couleurs possible. Le glouton prend les sommets dans un ordre donné et donne à chacun la plus petite couleur qu'aucun de ses voisins déjà colorés n'utilise ; il coûte O(n + p) et utilise au plus Δ + 1 couleurs, où Δ est le plus grand degré. Le résultat dépend de l'ordre : sur la couronne à huit sommets, il utilise 4 couleurs dans l'ordre des numéros, alors que 2 suffisent. Welsh-Powell prend les sommets par degrés décroissants ; DSATUR choisit à chaque étape le sommet dont les voisins colorés portent le plus de couleurs différentes. Aucun ne garantit χ (G). Une clique, ensemble de sommets deux à deux voisins, minore χ (G) : une coloration à k couleurs et une clique de k sommets prouvent que la coloration est optimale.

Q: Dijkstra, A*, Floyd-Warshall : quel algorithme choisir ?

Tout dépend de la question et du signe des poids. Si tous les poids sont égaux, le parcours en largeur donne les distances en nombre d'arêtes en O(n + p). Pour les distances depuis une source avec des poids positifs ou nuls, on prend Dijkstra : la version naïve, en O(n^2), convient à un graphe dense ; la version avec un tas, en O((n + p) log n), à un graphe peu dense comme un réseau de routes. Pour une seule cible et une bonne estimation de la distance restante, A* fixe en général bien moins de sommets. Pour les distances entre tous les couples, ou avec des poids négatifs sans cycle de poids négatif, on prend Floyd-Warshall, en Θ (n^3), au code très court. Pour partager une ressource entre des sommets voisins, comme des jours de livraison, des créneaux d'examen ou des fréquences, on cherche une coloration, puis une clique pour savoir si l'on peut faire mieux. Sur la copie, on justifie ce choix en une phrase.

Graphes pondérés, plus court chemin à origine unique par l'algorithme de Dijkstra avec une file de priorité, reconstruction du chemin par les prédécesseurs, algorithme A* et heuristique consistante, plus courts chemins entre tous les couples par Floyd-Warshall, coloration gloutonne d'un graphe et applications, complexités.

17méthodes
35exercices corrigés
3problèmes
23pièges
53figures

Les nombres sont ceux du chapitre complet ; chaque filière voit la partie qui correspond à son programme.

Dans un graphe pondéré, la distance de $s$ à $t$ est la plus petite somme des poids d'un chemin de $s$ à $t$ . Le chapitre traite les lignes « Recherche d'un plus court chemin dans un graphe pondéré positivement » et « Applications » du programme d'informatique de deuxième année en MP, PSI et TSI au Maroc. Il déroule l'algorithme de Dijkstra dans le tableau des distances, l'écrit en Python, d'abord en $O(n^2)$ avec une recherche du minimum, puis en $O((n + p) \log n)$ avec un tas, reconstruit les chemins par les prédécesseurs et montre pourquoi les poids doivent être positifs ou nuls. Il présente A* comme une variante heuristique de Dijkstra, avec une heuristique consistante, calcule toutes les distances par l'algorithme de Floyd-Warshall en $\Theta(n^3)$ et colore un graphe par la coloration gloutonne, Welsh-Powell et DSATUR, en encadrant le nombre chromatique. Les problèmes reprennent des sujets d'informatique du CCINP 2025 (une randonnée), du CCINP 2024 en filière TSI (la coloration d'une carte de pays) et du concours X-ENS 2023 (deux textes comparés par un plus court chemin).

Ce que tu sauras faire

Quand les pistes ont des longueurs, le moins de pistes n'est plus le moins de kilomètres. On veut l'itinéraire le plus court depuis la coopérative, vers un seul ksar ou vers tous, puis toutes les distances d'un coup, pour choisir où regrouper les réserves ; on veut enfin partager des jours ou des créneaux sans conflit entre voisins. Quatre algorithmes répondent à ces questions : Dijkstra, A*, Floyd-Warshall et la coloration gloutonne.

définir la longueur d'un chemin, la distance et le plus court chemin dans un graphe pondéré ;
dérouler l'algorithme de Dijkstra à la main dans le tableau des distances, et l'écrire en Python, d'abord avec une recherche du minimum, puis avec un tas ;
reconstruire un plus court chemin par les prédécesseurs ;
justifier la terminaison, la correction et la complexité de Dijkstra, et expliquer pourquoi les poids doivent être positifs ou nuls ;
présenter A* comme une variante heuristique de Dijkstra et choisir une heuristique ;
écrire et appliquer l'algorithme de Floyd-Warshall ;
colorer un graphe, encadrer son nombre chromatique et modéliser un problème de conflits par une coloration.

L'essentiel : Dijkstra Extrait gratuit

Un extrait de la fiche « L'essentiel » du chapitre. Les démonstrations sont dans le cours détaillé.

À retenir Principe

À chaque étape, fixer le sommet non fixé de plus petite distance provisoire (le plus petit numéro à égalité), puis relâcher les arcs qui en partent. Exact quand les poids sont positifs ou nuls ; un seul poids négatif peut le tromper (0 → 1 : 2, 0 → 2 : 3, 2 → 1 : −2 donne 2 au lieu de 1). Invariant : la valeur d'un sommet fixé est sa distance.

def dijkstra(GP, s):
    n = len(GP)
    dist = [INF] * n
    pred = [-1] * n
    fixe = [False] * n
    dist[s] = 0
    for etape in range(n):
        u = -1
        m = INF
        for v in range(n):
            if not fixe[v] and dist[v] < m:
                u = v
                m = dist[v]
        if u == -1:
            break
        fixe[u] = True
        for (v, w) in GP[u]:
            if not fixe[v] and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                pred[v] = u
    return dist, pred

Chemin : remonter de t à s par pred, puis retourner la liste (chemin_pred) ; None si pred[t] == -1 et t != s.

Avec un tas (tas-max du chapitre 3) : ranger (-dist[v], -v) à chaque amélioration ; à l'extraction, ignorer un sommet déjà fixé (entrée périmée) ; le tas reçoit au plus un couple par arc examiné.

Une méthode du chapitre Extrait gratuit

Méthode Dérouler Dijkstra à la main dans le tableau des distances

Quand l’utiliser

« Donner les étapes de l'algorithme de Dijkstra », « compléter le tableau », « quelle est la distance de $s$ à $t$ , et le chemin ».

Rappel de cours

À chaque étape, on fixe le sommet non fixé de plus petite distance provisoire, puis on relâche ses arcs vers les non fixés. Tableau : une ligne par étape, une colonne par sommet, distance avec le prédécesseur en indice, valeur fixée encadrée (cours, section 3.2).

Démarche

Écrire la règle d'égalité : le plus petit numéro (ou la première lettre) parmi les sommets de même distance.
Première ligne : $0$ pour la source, $\infty$ ailleurs ; on encadre la source.
Pour chaque voisin non fixé du sommet que l'on vient de fixer, calculer distance du sommet fixé plus poids, et ne remplacer la valeur que si elle est strictement plus petite, avec le nouveau prédécesseur.
Recopier les autres valeurs, encadrer la plus petite des non fixés ; mettre « · » sous les sommets déjà fixés.
S'arrêter quand tous les sommets sont fixés, ou quand il ne reste que des $\infty$ .
Lire la distance dans la case encadrée de la cible, et le chemin en remontant les prédécesseurs.

Rédaction type

« À distance égale, on fixe le sommet de plus petit numéro. La distance de $s$ à $t$ est la valeur fixée de $t$ , [13] ; en remontant les prédécesseurs, $t$ vient de [4], qui vient de [3], [...] : le plus court chemin est [ $0, 2, 1, 3, 4, 5$ ]. »

Exemple traité

Depuis la mosquée, sur les six quartiers :

étape	fixé	0	1	2	3	4	5
1	0	$\boxed{0}$	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$
2	2	·	$4_{0}$	$\boxed{1_{0}}$	$\infty$	$\infty$	$\infty$
3	1	·	$\boxed{3_{2}}$	·	$\infty$	$\infty$	$\infty$
4	3	·	·	·	$\boxed{8_{1}}$	$\infty$	$\infty$
5	4	·	·	·	·	$\boxed{11_{3}}$	$16_{3}$
6	5	·	·	·	·	·	$\boxed{13_{4}}$

À l'étape 3, le quartier 1 passe de 4 (ruelle directe) à $1 + 2 = 3$ par le quartier 2. À l'étape 6, le quartier 5 passe de 16 (par 3) à $11 + 2 = 13$ (par 4). Le quartier 5 est à 13 minutes, par $0, 2, 1, 3, 4, 5$ .

Erreurs fréquentes

Choisir le minimum parmi les voisins du sommet courant au lieu de tous les non fixés.
Remplacer une valeur à égalité, ou par une valeur plus grande.
Oublier d'encadrer, ou continuer à modifier un sommet déjà fixé.

Pour s’entraîner

Exercices 2, 3 et 5 ; problème 1.

Un exercice corrigé Extrait gratuit

Exercice Dijkstra au tableau sur un graphe orienté ★☆☆

Cinq dépôts, notés $s$ , $t$ , $x$ , $y$ et $z$ , sont reliés par des routes à sens unique. On numérote $s = 0$ , $t = 1$ , $x = 2$ , $y = 3$ et $z = 4$ ; les arcs pondérés sont les suivants.

A2 = [(0, 1, 10), (0, 3, 5), (1, 3, 2), (1, 2, 1),
      (2, 4, 4), (3, 1, 3), (3, 2, 9), (3, 4, 2),
      (4, 0, 7), (4, 2, 6)]

Les cinq dépôts et leurs dix routes à sens unique, avec leurs longueurs.

Dérouler l'algorithme de Dijkstra depuis $s$ dans le tableau des distances.
Donner la distance de $s$ à chaque dépôt et le prédécesseur de chacun.
Donner un plus court chemin de $s$ à $x$ .
Contrôler par programme.

Indications

Méthode 2 : à chaque étape, on encadre la plus petite distance provisoire des sommets non fixés, puis on relâche les arcs qui partent du sommet encadré.
Le graphe est orienté : on ne relâche que les arcs sortants.

Analyse : comment trouver l’idée

On tient le tableau ligne par ligne. Une ligne donne les distances provisoires au début d'une étape ; on encadre la plus petite parmi les sommets non fixés, puis, pour chaque arc $u \to v$ sortant du sommet fixé $u$ , on remplace la distance de $v$ par $d(u) + w(u, v)$ si c'est strictement plus petit, en notant $u$ en indice.

Correction détaillée

Question 1. On écrit les sommets par leurs lettres dans le tableau.

étape	fixé	s	t	x	y	z
1	s	$\boxed{0}$	$\infty$	$\infty$	$\infty$	$\infty$
2	y	·	$10_{s}$	$\infty$	$\boxed{5_{s}}$	$\infty$
3	z	·	$8_{y}$	$14_{y}$	·	$\boxed{7_{y}}$
4	t	·	$\boxed{8_{y}}$	$13_{z}$	·	·
5	x	·	·	$\boxed{9_{t}}$	·	·

Question 2. $d(s, s) = 0$ , $d(s, t) = 8$ , $d(s, x) = 9$ , $d(s, y) = 5$ , $d(s, z) = 7$ . Prédécesseurs : $t$ a $y$ , $x$ a $t$ , $y$ a $s$ , $z$ a $y$ .

Question 3. On remonte les prédécesseurs depuis $x$ : $x$ , $t$ , $y$ , $s$ , puis on retourne la liste : $s \to y \to t \to x$ , de longueur $5 + 3 + 1 = 9$ . La route directe $s \to t$ de 10 n'est pas la meilleure : passer par $y$ fait gagner 2 sur l'arrivée en $t$ .

Question 4.

G2 = listes_ponderees(5, A2, True)
dist, pred = dijkstra(G2, 0)
print(dist)
print(pred)
print(chemin_pred(pred, 0, 2))

Le programme affiche :

[0, 8, 9, 5, 7]
[-1, 3, 1, 0, 3]
[0, 3, 1, 2]

Le programme donne les mêmes distances, les prédécesseurs $3 = y$ pour $t$ , $1 = t$ pour $x$ , et le chemin $0, 3, 1, 2$ , c'est-à-dire $s, y, t, x$ .

Méthodes à retenir

Une ligne par étape, la plus petite valeur non fixée encadrée, les arcs sortants relâchés. Dans un graphe orienté, seuls les arcs qui partent du sommet fixé comptent. Voir les méthodes 2 et 4.

Dans le chapitre complet

Le cours détaillé, toute la fiche « L'essentiel », 17 méthodes, 23 pièges corrigés, la carte mentale, 35 exercices corrigés, 3 problèmes de concours, les fiches à mémoriser et l'assistant qui répond à tes questions. Les trois premiers chapitres de chaque matière sont offerts avec un compte d’essai gratuit.

Ouvrir l'essai gratuit Voir les offres

Plan du cours

1. Du moins de pistes au moins de kilomètres
- 1.1 L'itinéraire du chauffeur
- 1.2 Quatre questions
- 1.3 Le Python employé dans ce chapitre
2. Distances dans un graphe pondéré
- 2.1 Longueur d'un chemin
- 2.2 Distance
- 2.3 Sous-chemin d'un plus court chemin
- 2.4 Inégalité triangulaire
- 2.5 Le relâchement d'un arc
3. L'algorithme de Dijkstra : le principe
- 3.1 L'idée
- 3.2 L'exemple au tableau
- 3.3 L'arbre des plus courts chemins
- 3.4 Égalités et règle de choix
4. Dijkstra en Python
- 4.1 Le code naïf
- 4.2 Reconstruire un chemin
- 4.3 Sur une matrice des poids
- 4.4 Sommets inaccessibles et arrêt à la cible
- 4.5 Terminaison et correction
- 4.6 Complexité
5. Pourquoi des poids positifs
- 5.1 Un contre-exemple
- 5.2 Ajouter une constante ne répare rien
- 5.3 Ce que dit le programme
6. Dijkstra avec une file de priorité
- 6.1 Ce qui coûte
- 6.2 Le tas du chapitre 3
- 6.3 Pas de mise à jour de priorité : les entrées périmées
- 6.4 Le code
- 6.5 La trace du tas
- 6.6 Complexité et choix de la version
- 6.7 Le module heapq
7. L'algorithme A*
- 7.1 Une seule destination
- 7.2 Estimer ce qui reste
- 7.3 Admissible, consistante
- 7.4 Le code
- 7.5 Sur les pistes : la partie entière du vol d'oiseau
- 7.6 Sur une grille
- 7.7 Ce que l'on admet, ce qui peut tromper
8. Toutes les distances : Floyd-Warshall
- 8.1 Le problème
- 8.2 Le sous-problème et la récurrence
- 8.3 Le code
- 8.4 Une trace
- 8.5 Reconstruire un chemin
- 8.6 Une seule matrice, et le coût
- 8.7 L'entrepôt le mieux placé
- 8.8 Poids négatifs
9. Colorer un graphe
- 9.1 Le problème
- 9.2 Premiers exemples
- 9.3 Encadrer le nombre chromatique
- 9.4 Le glouton de la première couleur libre
- 9.5 L'ordre compte
- 9.6 Welsh-Powell
- 9.7 DSATUR
- 9.8 Aucune garantie
- 9.9 Applications
10. Bilan
- 10.1 Les complexités
- 10.2 Quel algorithme pour quelle question
- 10.3 Vers le chapitre 13

Les méthodes du chapitre

Chaque méthode est une fiche : quand l'utiliser, le rappel de cours, les étapes, la rédaction attendue sur la copie, un exemple traité, les erreurs à éviter.

Modéliser un problème de plus court chemin
Dérouler Dijkstra à la main dans le tableau des distances
Écrire Dijkstra naïf sur listes de couples ou sur matrice des poids
Reconstruire un plus court chemin par les prédécesseurs
Justifier Dijkstra : terminaison, invariant, rôle de la positivité
Écrire Dijkstra avec une file de priorité et dérouler le contenu du tas
Calculer la complexité d'un algorithme de plus court chemin et choisir la version
Réfuter un algorithme de chemin par un contre-exemple
Écrire A* à partir de Dijkstra et compter les sommets fixés
Choisir une heuristique et prouver qu'elle est admissible ou consistante
Dérouler Floyd-Warshall à la main
Écrire floyd_warshall, reconstruire un chemin et l'appliquer
Colorer par le glouton dans un ordre donné et vérifier une coloration
Améliorer l'ordre : Welsh-Powell, DSATUR
Encadrer le nombre chromatique et conclure à l'optimalité
Modéliser des conflits par une coloration
Choisir l'algorithme et lire un sujet de plus courts chemins ou de coloration

Les exercices corrigés

Chaque exercice a ses indications, sa correction rédigée et ce qu'il faut en retenir.

Application directe (13)

Longueur d'un chemin et distance
Dijkstra au tableau sur un graphe orienté
Gestion d'un réseau de serveurs
Remonter les prédécesseurs
Relâcher des arcs
Le contenu du tas
Heuristiques sur une grille
Floyd-Warshall à la main
Colorer dans deux ordres
Vérifier une coloration donnée par une matrice
L'étoile et le graphe complet
Trois questions de cours
Les examens blancs

Entraînement (16)

Listes ou matrice
S'arrêter à la cible
Dijkstra avec un tas-min
Un Dijkstra à corriger
Un poids négatif
Quand tous les poids valent 1
A* dans le labyrinthe
A* ou le meilleur d'abord
Le centre d'un réseau
Successeurs ou prédécesseurs
Welsh-Powell couleur par couleur
Des groupes de travail
Minorer par une clique
Les fréquences des relais
Naïf ou tas : mesurer
Floyd-Warshall, une programmation dynamique

Approfondissement (6)

Prouver Dijkstra
Admissible mais pas consistante
Un cycle de poids négatif
La couronne et DSATUR
Les pistes utiles
Dijkstra, un glouton exact

Les problèmes de concours

Des extraits de sujets réels, corrigés en entier, avec la durée conseillée et les méthodes mobilisées.

Organiser un trek
CCINP 2025, filières PC et PSI, épreuve d'informatique, problème « Gestion de randonnées », partie III « Organisation d'un Trek », sous-parties III.1 et III.2, questions 22 à 28, complétée
Des algorithmes pour colorer un graphe
CCINP 2024, filière TSI, épreuve d'informatique, problème « Colorer un graphe », partie I « Des algorithmes pour colorer un graphe », sous-parties I.2 à I.6, questions 6 à 27, complétée
Plus courts chemins et différences entre deux textes
X-ENS 2023, filières MP, PC et PSI, épreuve d'informatique B, partie III « Calcul de différentiels par calcul de plus courts chemins », questions 14 à 17, complétée

Questions fréquentes

Comment fonctionne l'algorithme de Dijkstra ?

Dijkstra calcule les distances d'une source $s$ à tous les sommets d'un graphe dont les poids sont positifs ou nuls. On garde pour chaque sommet une distance provisoire dist[v], 0 pour la source et INF = float('inf') ailleurs, et un prédécesseur pred[v]. À chaque étape, on fixe le sommet non fixé de plus petite distance provisoire, puis on relâche les arcs qui en partent : si dist[u] + w < dist[v], on remplace dist[v] par dist[u] + w et pred[v] par u. Ce choix est sûr parce que tout autre chemin vers ce sommet passe par un sommet non fixé au moins aussi éloigné, et que la suite du chemin a une longueur positive ou nulle. Avec une recherche du minimum parmi tous les sommets, le coût est $O(n^2)$ . Avec un tas, où l'on ajoute un couple à chaque amélioration et où l'on ignore à l'extraction un sommet déjà fixé, il descend à $O((n + p) \log n)$ , bien meilleur pour un graphe peu dense.

Pourquoi Dijkstra ne marche-t-il pas avec des poids négatifs ?

Dijkstra fixe un sommet dès qu'il est le plus proche des sommets non fixés, en supposant qu'aucun chemin plus long au départ ne pourra le rattraper. Un arc de poids négatif peut le rattraper. Avec les arcs $0 \to 1$ de poids 2, $0 \to 2$ de poids 3 et $2 \to 1$ de poids $-2$ , Dijkstra fixe le sommet 1 à la distance 2 avant d'examiner l'arc $2 \to 1$ ; or le chemin $0, 2, 1$ a une longueur $3 + (-2) = 1$ . Le programme rend 2 sans rien signaler. Ajouter la même constante à tous les poids ne répare rien : un chemin de $k$ arcs gagne $k$ fois la constante, et l'ordre des longueurs change. Sur cet exemple, en ajoutant 2, le chemin rendu devient l'arc direct. Le programme ne demande Dijkstra que pour des graphes pondérés positivement ; l'algorithme de Floyd-Warshall accepte des poids négatifs, pourvu qu'il n'y ait aucun cycle de poids total négatif.

Qu'est-ce que l'algorithme A* et une heuristique admissible ?

A* cherche un plus court chemin vers une seule cible $t$ . Il fait comme Dijkstra, mais fixe à chaque étape le sommet qui minimise $g(v) + h(v)$ , où $g(v)$ est la distance provisoire depuis la source et $h(v)$ une estimation de la distance qui reste jusqu'à $t$ , et il s'arrête quand $t$ est fixé. Avec $h = 0$ , c'est Dijkstra. L'heuristique est admissible si elle ne surestime jamais, $h(v) \le d(v, t)$ ; elle est consistante si $h(u) \le w(u, v) + h(v)$ pour tout arc, avec $h(t) = 0$ , ce qui entraîne l'admissibilité. Avec une heuristique consistante, A* rend la distance (résultat admis), en fixant souvent bien moins de sommets : sur le réseau de pistes du cours, 4 ksour au lieu de 9. Sur une grille à quatre directions de pas 1, la distance de Manhattan est consistante. Une heuristique qui surestime peut faire rendre un chemin trop long.

Comment fonctionne l'algorithme de Floyd-Warshall ?

Floyd-Warshall calcule les distances entre tous les couples de sommets, sur la matrice des poids, avec INF sans arc et 0 sur la diagonale. On note $d_k(i, j)$ la plus courte longueur d'un chemin de $i$ à $j$ dont les sommets intermédiaires sont parmi $0, \ldots, k - 1$ . Un plus court chemin qui a le droit de passer par $k$ n'y passe pas, ou y passe une fois, d'où la récurrence $d_{k+1}(i, j) = \min(d_k(i, j), d_k(i, k) + d_k(k, j))$ , valable sans cycle de poids négatif. On ne garde qu'une matrice, mise à jour sur place, et la boucle sur le sommet intermédiaire $k$ est la plus extérieure. Une matrice des successeurs, mise à jour par S[i][j] = S[i][k], permet de reconstruire les chemins. Le coût est $\Theta(n^3)$ en temps et $O(n^2)$ en mémoire. Une case négative sur la diagonale révèle un cycle de poids négatif. La matrice donne aussi l'excentricité de chaque sommet et le centre du graphe.

Comment colorer un graphe par un algorithme glouton ?

Une coloration donne à chaque sommet une couleur, de sorte que deux voisins aient des couleurs différentes ; le nombre chromatique $\chi(G)$ est le plus petit nombre de couleurs possible. Le glouton prend les sommets dans un ordre donné et donne à chacun la plus petite couleur qu'aucun de ses voisins déjà colorés n'utilise ; il coûte $O(n + p)$ et utilise au plus $\Delta + 1$ couleurs, où $\Delta$ est le plus grand degré. Le résultat dépend de l'ordre : sur la couronne à huit sommets, il utilise 4 couleurs dans l'ordre des numéros, alors que 2 suffisent. Welsh-Powell prend les sommets par degrés décroissants ; DSATUR choisit à chaque étape le sommet dont les voisins colorés portent le plus de couleurs différentes. Aucun ne garantit $\chi(G)$ . Une clique, ensemble de sommets deux à deux voisins, minore $\chi(G)$ : une coloration à $k$ couleurs et une clique de $k$ sommets prouvent que la coloration est optimale.

Dijkstra, A*, Floyd-Warshall : quel algorithme choisir ?

Tout dépend de la question et du signe des poids. Si tous les poids sont égaux, le parcours en largeur donne les distances en nombre d'arêtes en $O(n + p)$ . Pour les distances depuis une source avec des poids positifs ou nuls, on prend Dijkstra : la version naïve, en $O(n^2)$ , convient à un graphe dense ; la version avec un tas, en $O((n + p) \log n)$ , à un graphe peu dense comme un réseau de routes. Pour une seule cible et une bonne estimation de la distance restante, A* fixe en général bien moins de sommets. Pour les distances entre tous les couples, ou avec des poids négatifs sans cycle de poids négatif, on prend Floyd-Warshall, en $\Theta(n^3)$ , au code très court. Pour partager une ressource entre des sommets voisins, comme des jours de livraison, des créneaux d'examen ou des fréquences, on cherche une coloration, puis une clique pour savoir si l'on peut faire mieux. Sur la copie, on justifie ce choix en une phrase.

Comment y accéder

Ce chapitre fait partie de l'accès complet. Les trois premiers chapitres de chaque matière (deux par bloc en économie et droit, en management et gestion) sont offerts avec un compte d'essai gratuit. Créer un compte d'essai ou se connecter. Pour l'accès complet et les tarifs, vois les offres.