Graphe pondéré et plus court chemin
Bonjour à tous,
Je viens quérir votre aide car je me pose une question concernant la création d'un graphe en PHP.
Tout d'abord, comment devrais-je créer le graphe?
J'avais pensé à une liste du genre:
Liste maListe = [
[A,B,2],
[A,D,5],
[B,C,4],
[D,C, 3]
];
Avec "A" qui est relié à "B" avec comme poids d'arête 2, "A" qui est relié à "D" avec comme poids d'arête 5, etc...
Sachant que mon graphe est pondéré mais non-orienté et connexe.
Au final il aura 31 sommets et 49 arêtes pondérées.
Concernant la création du graphe, je suis tombé sur une bibliothèque de Pear "Structures_Graph" (lien) mais en parcourant la documentation présente, j'ai pas l'impression qu'elle permette de pondérer les arêtes.
Je souhaite trouver le plus court chemin menant d'un point A à un point X avec un affichage des sommets visités.
Pour cela j'ai pensé à l'algorithme de Dijkstra que j'avais déjà implémenté il y a quelques années en Mapple seulement son implémentation en PHP m'est quelque peu difficile.
Comment auriez-vous procéder pour la déclaration du graphe et pour l'implémentation de l'algorithme?
Merci de aide!
Répondre avec citation
Partager