Exercices.
Algorithme de Djikstra.
L'algorithme est un classique, il permet de déterminer le chemin le plus court.
Algorithme
On affecte tous les sommets accessible par le sommet de départ une couleur (rouge dans l'animation).
On affecte à tous les sommets une distance égale à -1 (si la pondération est négative il faut prendre -inf).
On affecte au sommet de départ la distance 0 et on le colorie en vert.
Tant qu'il existe des sommet vert :
On cherche dans les sommets verts, celui (ou un) qui a la distance la plus courte. Soit d sa distance.
Pour tous les voisins du sommets précédents :
On compare sa distance avec (d + poids de l’arête entre le sommet et l'arête), si la distance est plus grand on la remplace par d + poids de l’arête.
On colorie le sommet en bleu.
Exercice
Pour une version non orientée voir ici .
Exemple
Les Graphes étaient au programme de Maths des Terminales EZ spécialisé en maths, ci dessous quelques sujets de bac (vous pouvez en trouver plus sur le site de l'A.P.M.E.P.
A quelle famille d'algorithme appartient algorithme de Dijkstra.
Implémenter l'algorithme de Dijkstra, a la fin la fonction doit retourner un dictionnaire qui va associer à chaque sommet la distance avec le sommet du début. Pour ceux qui ont besoin d'aide vous pouvez utilisez l'aide ci dessous :
Algorithme de coloration de sommets
On veut colorier chaque sommet de telle sorte que deux sommets voisins sont de couleur différente. Chercher le nombre minimale de couleurs (ce nombre est appelé nombre chromatique du graphe) est NP-difficile (c'est à dire que trouver une solution en temps polynomial permettrai de résoudre le coyageur de commerce et le sac à dos en temps polynomial.
Exercice
Trouver les nombres chromatiques des graphes suivant :
Exercice
Pour le problème on va associer à chaque sommet un indice 0, 1, 2 ... qui sera sa "couleur" deux sommets voisins ne peuvent avoir le même indice. à la fin il faut retourner un dictionnaire qui associe à chaque sommet son indice et le nombre de couleurs utilisés.
Avant de passer au code on utilisera les algorithmes à la "main" sur les exemples ci-dessus.
Utiliser un algorithme glouton pour résoudre le problème : on parcours les sommets les uns après les autres et on associe l'indice le plus faible possible (il faut donc vérifier les sommets voisins pour l'attribuer).
Utiliser l'algorithme de Welsh Powell :
On ordonne les sommets par ordre de degré décroissant que l'on place dans une liste L.
On fixe i = 0
Tant qu'il reste des sommets dans L non "colorié".
Dans l'ordre pour chaque sommet de L :
Si le sommet n'a pas d'indice et n'est pas voisin d'un sommet d'indice i alors on lui donne l'indice i.
On augmente i de 1.
On retourne un dictionnaire qui a chaque sommet asscoie l'indice.
phpMyVisites | Open source web analytics