Algorithmes sur les graphes en Prolog: Dijkstra, Prim, Kruskal

Date de publication : 17 Novembre 2006

Cet article présente quelques algorithmes sur les graphes, ainsi que leur implémentation en Prolog.

Page 1
À propos de cet article
A qui s'adresse cet article?
Pourquoi cet article?
1. Graphes: généralités
1.1. Qu'est-ce qu'un graphe?
1.2. Applications
1.3. Représentation choisie
1.3.1. Les arcs
1.3.2. Les noeuds
1.3.3. Prédicats
2. Parcours d'un graphe
Page 2
3. Algorithmes de recherche du plus court chemin
3.1. Algorithme de Dijkstra
3.1.1. Principe de l'algorithme
3.1.2. Implémentation
3.1.3. Discussion sur l'implémentation
3.2. Algorithme de Bellman-Ford
3.2.1. Différences avec Dijsktra
3.2.2. Implémentation
Page 3
4. Arbre de recouvrement minimal
4.1. Définition
4.2. Algorithme de Jarnik (ou Prim)
4.2.1. Principe de l'algorithme
4.2.2. Implémentation
4.3. Algorithme de Kruskal
4.3.1. Principe de l'algorithme
4.3.2. Implémentation
4.4. Différences entre Jarnik et Kruskal
Conclusion

Copyright © 2006 pcaboche. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à 3 ans de prison et jusqu'à 300 000 E de dommages et intérêts. Cette page est déposée à la SACD.