Comme je n'ai pas trouvé d'exemple qui implémente Dijkstra en php je me suis créé un petit programme en php. Je ne prétends pas qu'il soit tip-top, notamment la classe Noeud est trop dépendante de la classe Dijkstra mais bon elle répond à mes besoin. Si ça peut aider...
On crée un graphe et on précise le noeud de départ et d'arrivée. Le programme trouve la distance minimale ainsi que le chemin le plus court.
Source / Exemple :
Deux fichiers : dijkstra.php qui implémente l'algo et test_dijkstra2.php qui le teste...
dijkstra.php :
<?php
/*
Description de l'algorithme de Dijkstra
On suppose ici que le sommet de départ (qui sera la racine de l'arborescence) est le sommet 1.
Notons qu'on peut toujours renuméroter les sommets pour que ce soit le cas.
Initialisations
c(i,j) = 0 si i=j
c(i,j) = infini si i != j et (i,j) n'est pas un arc
c(i,j) = d(i,j) si i != j et (i,j) est un arc
l(j) = c(1,j) et p(j) = NIL, pour 1 <= j <= n
Pour 2 <= j <= n faire
Si c(1,j) < infini alors p(j) = 1.
S = {1} ; T = {2, 3, ..., n}.
Itérations
Tant que T n'est pas vide faire :
Choisir i dans T tel que l(i) est minimum
Retirer i de T et l'ajouter à S
Pour chaque successeur j de i, avec j dans T, faire
Si l(j) > l(i) + d(i,j) alors
l(j) = l(i) + d(i,j)
p(j) = i
function echoln($chaine) {
echo $chaine . "\n</br>";
}
// -------------------------------------------------------------
class Noeud {
const C_INFINI = '1000000000';
private $id;
private $nom = "";
private $numero = 0;
private $etat = "aucun";
private $valeur = self::C_INFINI;
private $noeud_precedent = null;
function __construct ($id, $nom = "") {
$this->id = $id;
$this->nom = $nom;
}
function __toString() {
return $this->nom;
}
function getId() {return $this->id;}
function getNom() {return $this->nom;}
function getNumero() {return $this->numero;}
function getEtat() {return $this->etat;}
function getValeur() {return $this->valeur;}
function getNoeud_precedent() {return $this->noeud_precedent;}
function setId($id) {$this->id = $id;}
function setNom($nom) {$this->nom = $nom;}
function setNumero($numero) {$this->numero = $numero;}
function setEtat($etat) {$this->etat = $etat;}
function setValeur($valeur) {$this->valeur = $valeur;}
function setNoeud_precedent(noeud $np) {$this->noeud_precedent = $np;}
function init() {
$this->etat = "aucun";
$this->valeur = self::C_INFINI;
$this->noeud_precedent = null;
}
}
class Arc {
private $noeud_depart;
private $noeud_arrivee;
private $valeur;
function __construct (Noeud $d, Noeud $a, $valeur) {
$this->noeud_depart = $d;
$this->noeud_arrivee = $a;
$this->valeur = $valeur;
}
function __toString() {
return $this->noeud_depart->getNom() . " -> " . $this->noeud_arrivee->getNom() . " (" . $this->valeur . ")";
}
function getNoeud_depart() {return $this->noeud_depart;}
function getNoeud_arrivee() {return $this->noeud_arrivee;}
function getValeur() {return $this->valeur;}
function setNoeud_depart(Noeud $n) {$this->noeud_depart = $n;}
function setNoeud_arrivee(Noeud $n) {$this->noeud_arrivee = $n;}
function setValeur($v) {$this->valeur = $v;}
}
class Graphe {
private $tab_noeud = array();
private $tab_arc = array();
function __construct(Array $n, array $a) {
$this->tab_noeud = $n;
$this->tab_arc = $a;
}
function getTab_noeud() {return $this->tab_noeud;}
function getTab_arc() {return $this->tab_arc;}
function setTab_noeud(Array $t) {$this->tab_noeud = $t;}
function setTab_arc(Array $t) {$this->tab_arc = $t;}
function get_nb_noeuds() { return count($this->tab_noeud);}
function get_nb_arcs() { return count($this->tab_arc);}
// retourne l'arc éventuel contenant les deux noeuds précisés
function get_arc(Noeud $d, Noeud $a) {
foreach($this->tab_arc as $arc) {
if ($arc->noeud_depart == $d and $arc->noeud_arrivee == $a) return $arc;
}
return null;
}
function print_arcs() {
$arcs = $this->getTab_arc();
foreach($arcs as $arc) echoln($arc);
}
// retourne un tableau de noeuds connectés au noeud spécifié par un arc du graphe, avec sa valeur
// dans toutes ces méthodes il faudrait vérifier que le noeud en paramètre est bien un noeud du graphe...
public function get_noeuds_suivants(Noeud $n) {
$liste_noeuds = array();
$liste_valeurs = array();
foreach($this->tab_arc as $arc) {
if ($arc->getNoeud_depart() == $n) {
$liste_noeuds[] = $arc->getNoeud_arrivee();
$liste_valeurs[] = $arc->getValeur();
}
}
return array($liste_noeuds, $liste_valeurs);
}
function get_noeuds_valeurs () {
$resultat = array();
foreach($this->tab_noeud as $noeud) {
$resultat[$noeud->getId()] = $noeud->getValeur();
}
return $resultat;
}
function get_noeuds_valeurs_par_nom () {
$resultat = array();
foreach($this->tab_noeud as $noeud) {
$resultat[$noeud->getNom()] = $noeud->getValeur();
}
return $resultat;
}
# retourne le noeud sélectionné. Il ne doit y en avoir qu'un, ce contrôle n'est pas fait.
function get_noeud_selectionne() {
foreach($this->tab_noeud as $noeud) {
if ($noeud->getEtat() == "sélectionné") return $noeud;
}
return null;
}
#retourne les noeuds non traités
function get_noeuds_non_traites() {
$tab_noeuds_non_traites = array();
$tab_valeur_noeuds_non_traites = array();
foreach($this->tab_noeud as $noeud) {
if ($noeud->getEtat() == "aucun") {
$tab_noeuds_non_traites[] = $noeud;
}
}
return $tab_noeuds_non_traites;
}
function set_noeud_selectionne(Noeud $n) {
$ancien_noeud_selection = $this->get_noeud_selectionne();
if ($ancien_noeud_selection != null) $ancien_noeud_selection->setEtat("traité");
$n->setEtat("sélectionné");
}
# retourne les noeuds non marqués qui suivent le noeud sélectionné.
# Pour chaque noeud, retourne aussi la valeur de l'arc entre le noeud sélectionné et ce noeud
function get_noeuds_suivants_non_marques_depuis_noeud_selectionne() {
$tab_noeud_non_marque = array();
$tab_valeur_arc = array();
$selection = $this->get_noeud_selectionne();
list($noeuds, $valeurs_arcs) = $this->get_noeuds_suivants($selection);
if ($noeuds !== null) {
foreach($noeuds as $cle => $n) {
if ($n->getEtat() == "aucun") {
$tab_noeud_non_marque[] = $n;
$tab_valeur_arc[] = $valeurs_arcs[$cle];
}
}
return array($tab_noeud_non_marque, $tab_valeur_arc);
}
else return array(null, null);
}
}
class Dijkstra {
private $graphe = null;
private $depart = null;
private $arrivee = null;
private $chemin_minimal = array();
private $distance_minimale = Noeud::C_INFINI;
function __construct (Graphe $g) {
$this->graphe = $g;
}
function getArrivee() {return $this->arrivee;}
function getGraphe() {return $this->graphe;}
function getDepart() {return $this->depart;}
function getChemin_minimal() {return $this->chemin_minimal;}
function getDistance_minimale() {return $this->distance_minimale;}
function setGraphe(Graphe $g) {$this->graphe = $g;}
function setArrivee(Noeud $d) {
if (!in_array($d, $this->graphe->getTab_noeud() )) {
return false;
}
$this->arrivee = $d;
if ($d != null) {
return true;
}
else return false;
}
function setDepart(Noeud $d) {
if (!in_array($d, $this->graphe->getTab_noeud() )) {
return false;
}
$this->depart = $d;
foreach($this->graphe->getTab_noeud() as $noeud) {
$noeud->init();
}
$chemin_minimal = array();
$distance_minimale = Noeud::C_INFINI;
if ($this->depart != null) {
$this->depart->setValeur(0);
$this->graphe->set_noeud_selectionne($this->depart);
$this->actualise_valeur_noeuds();
return true;
}
else return false;
}
function print_valeur_noeuds() {
$str = "";
$val = $this->graphe->get_noeuds_valeurs();
print_r($val);
echoln("");
}
function print_valeur_noeuds_par_nom() {
$str = "";
$val = $this->graphe->get_noeuds_valeurs_par_nom();
print_r($val);
echoln("");
}
# actualise la valeur des noeuds qui suivent celui qui est sélectionné
function actualise_valeur_noeuds() {
$rc = 0;
$selection = $this->graphe->get_noeud_selectionne();
if ($selection != null) {
list($tab_noeuds, $tab_valeur_arc) = $this->graphe->get_noeuds_suivants_non_marques_depuis_noeud_selectionne();
if ($tab_noeuds != null) {
foreach($tab_noeuds as $cle => $noeud) {
$nouvelle_valeur = $selection->getValeur() + $tab_valeur_arc[$cle];
if ($nouvelle_valeur < $noeud->getValeur()) {
$noeud->setValeur($nouvelle_valeur);
$noeud->setNoeud_precedent($selection);
}
}
}
else $rc = -1;
}
else $rc = -2;
return ($rc);
}
#fonction principale qui effectue la recherche
function recherche() {
if ($this->getDepart() === null) {echoln("le noeud de départ n'est pas précisé"); return false;}
if ($this->getArrivee() === null) {echoln("le noeud d'arrivé n'est pas précisé"); return false;}
$iteration = 0;
$noeud = $this->etape_recherche();
while ($noeud !== null) {
$iteration++;
#echoln("iteration $iteration");
//$this->print_valeur_noeuds_par_nom();
$noeud = $this->etape_recherche();
}
$distmin = $this->getArrivee()->getValeur();
$this->distance_minimale = $distmin;
if ($distmin == Noeud::C_INFINI) {
return false;
}
else {
$this->calcule_chemin();
return true;
}
}
# depuis le noeud sélectionné en paramètre on cherche l'arc de moindre valeur conduisant aux noeuds suivants
# le noeud pointé par l'arc minimal devient sélectionné tandis que l'ancien passe à 'traité'
# retourne la nouvelle sélection
private function etape_recherche() {
$rc = 0;
# 1/ recherche du noeud à valeur minimal non marqué
#1.1/ Recherche des noeuds non marqués
$noeuds = $this->graphe->get_noeuds_non_traites();
if ( ($noeuds == null) or (count($noeuds) == 0) ) {
echoln("tous les noeuds sont traités");
return null;
}
#1.2/ Parmi eux, recherche de celui qui a la valeur minimale
$valeur_min = Noeud::C_INFINI;
$cle_min = "";
foreach($noeuds as $cle=>$n) {
if ($n->getValeur() < $valeur_min) {
$valeur_min = $n->getValeur();
$cle_min = $cle;
}
}
#1.3/ Sivaleur_min est infinie, c'est que les noeuds non marqués ont tous une valeur infinie : soient il n'y a pas de chemin qui vont
# d'eux à l'arrivée, soit il n'y a pas de chemin qui vont du noeud départ à eux => le processus est alors arrêté
if ($valeur_min == Noeud::C_INFINI) {
return null;
}
# 2/ sélectionner ce noeud
$this->graphe->set_noeud_selectionne($noeuds[$cle_min]);
# 3/ pour tout successeur non traité du noeud sélectionné,
# la valeur du successeur est au plus égale à
# la valeur du noeud sélectionné + la valeur de l'arc qui relie le noeud sélectionné au successeur
$this->actualise_valeur_noeuds();
# 4/ marquage du noeud sélectionné
$selection = $this->graphe->get_noeud_selectionne();
$selection->setEtat("traité");
return $selection;
}
# calcule le chemin minimal du point de départ au point d'arrivée sous forme de tableau de noeuds.
# retourne le nombre d'étapes pour y parvenir
public function calcule_chemin() {
$chemin = array();
$noeud = $this->getArrivee();
while ($noeud !== null) {
$chemin[] = $noeud;
$noeud = $noeud->getNoeud_precedent();
}
$chemin = array_reverse($chemin);
$this->chemin_minimal = $chemin;
return count($chemin);
}
# retourne le chemin minimal sous forme de chaîne de caractères
public function get_string_chemin() {
$path = "";
foreach($this->chemin_minimal as $etape) {
$path .= ", " . $etape->getNom();
}
$path = substr($path, 2);
return $path;
}
}
?>
Fichier test_dijkstra2.php. Les arcs du graphe correspondent à des randonnées que j'ai faites en Ile de France, leur valeur est la distance entre les deux noeuds du graphe.
<?php
include_once("dijkstra.php");
$n = array();
$i = 0; $n[$i] = new Noeud($i, 'Combs');
$i = 1; $n[$i] = new Noeud($i, 'Veneux');
$i = 2; $n[$i] = new Noeud($i, 'Melun');
$i = 3; $n[$i] = new Noeud($i, 'Fontainebleau');
$i = 4; $n[$i] = new Noeud($i, 'Montereau');
$i = 5; $n[$i] = new Noeud($i, 'Sens');
$i = 6; $n[$i] = new Noeud($i, 'Souppes');
$i = 7; $n[$i] = new Noeud($i, 'Corbeil');
$i = 8; $n[$i] = new Noeud($i, 'Marles');
$i = 9; $n[$i] = new Noeud($i, 'Crécy');
$i = 10; $n[$i] = new Noeud($i, 'Meaux');
$i = 11; $n[$i] = new Noeud($i, 'La Ferté-Sous-Jouarre');
$i = 12; $n[$i] = new Noeud($i, 'Saâcy');
$i = 13; $n[$i] = new Noeud($i, 'Provins');
$i = 14; $n[$i] = new Noeud($i, 'La Ferté Gaucher');
$i = 15; $n[$i] = new Noeud($i, 'Crégy');
$i = 16; $n[$i] = new Noeud($i, 'Crouy');
$i = 17; $n[$i] = new Noeud($i, 'Lizy');
$i = 18; $n[$i] = new Noeud($i, 'Coulommiers');
$i = 19; $n[$i] = new Noeud($i, 'Nangis');
$i = 20; $n[$i] = new Noeud($i, 'Fontaine-le-Port');
$i = 21; $n[$i] = new Noeud($i, 'St Mard');
$i = 22; $n[$i] = new Noeud($i, 'Pommeuse');
$i = 23; $n[$i] = new Noeud($i, 'Fosses');
$i = 24; $n[$i] = new Noeud($i, 'Viarmes');
$i = 25; $n[$i] = new Noeud($i, 'Auvers-sur-Oise');
$i = 26; $n[$i] = new Noeud($i, 'Chars');
$i = 27; $n[$i] = new Noeud($i, 'Persan');
$i = 28; $n[$i] = new Noeud($i, 'Bonnières');
$i = 29; $n[$i] = new Noeud($i, 'Houdan');
$i = 30; $n[$i] = new Noeud($i, 'Rambouillet');
$i = 31; $n[$i] = new Noeud($i, 'St Arnoult');
$i = 32; $n[$i] = new Noeud($i, 'Angerville');
$i = 33; $n[$i] = new Noeud($i, 'Malesherbes');
$i = 34; $n[$i] = new Noeud($i, 'Etampes');
$i = 35; $n[$i] = new Noeud($i, 'Le Perray');
$i = 36; $n[$i] = new Noeud($i, 'Les Essarts-le-Roi');
$i = 37; $n[$i] = new Noeud($i, 'St Rémy lès Chevreuse');
$i = 38; $n[$i] = new Noeud($i, 'Massy');
$i = 39; $n[$i] = new Noeud($i, 'Châtenay-Malabry');
$i = 40; $n[$i] = new Noeud($i, 'Paris 15');
$i = 41; $n[$i] = new Noeud($i, 'Villeneuve St G.');
$i = 42; $n[$i] = new Noeud($i, 'Rungis');
$i = 43; $n[$i] = new Noeud($i, 'Jouy-en-Josas');
$i = 44; $n[$i] = new Noeud($i, 'Fontenay-le-Fleury');
$i = 45; $n[$i] = new Noeud($i, 'St Nom la B.');
$i = 46; $n[$i] = new Noeud($i, 'St Germain en Laye');
$i = 47; $n[$i] = new Noeud($i, 'Conflans Ste H.');
$i = 48; $n[$i] = new Noeud($i, 'Pontoise');
$i = 49; $n[$i] = new Noeud($i, 'La Défense');
$i = 50; $n[$i] = new Noeud($i, 'Rueil-Malmaison');
$i = 51; $n[$i] = new Noeud($i, 'St Cloud');
$i = 52; $n[$i] = new Noeud($i, 'Boulogne-Billancourt');
$i = 53; $n[$i] = new Noeud($i, 'Alfortville');
$i = 53; $n[$i] = new Noeud($i, 'Montgeron');
$i = 54; $n[$i] = new Noeud($i, 'Ballancourt');
$i = 55; $n[$i] = new Noeud($i, 'Paris Gare de Lyon');
$i = 56; $n[$i] = new Noeud($i, 'Paris République');
$i = 57; $n[$i] = new Noeud($i, 'Paris Etoile');
$i = 58; $n[$i] = new Noeud($i, 'Fontenay-sous-Bois');
$i = 59; $n[$i] = new Noeud($i, 'Maisons-Alfort');
$i = 60; $n[$i] = new Noeud($i, 'Chelles');
$i = 61; $n[$i] = new Noeud($i, 'Esbly');
$i = 62; $n[$i] = new Noeud($i, 'Pontault-Combault');
$i = 63; $n[$i] = new Noeud($i, 'Tournan');
$tab_arc = array(
new Arc($n[0], $n[1], 42),
new Arc($n[0], $n[2], 26),
new Arc($n[0], $n[8], 46),
new Arc($n[1], $n[0], 42),
new Arc($n[1], $n[3], 8),
new Arc($n[1], $n[4], 20),
new Arc($n[1], $n[6], 40),
new Arc($n[1], $n[20], 24),
new Arc($n[2], $n[1], 25),
new Arc($n[2], $n[3], 17),
new Arc($n[3], $n[1], 8),
new Arc($n[4], $n[1], 18),
new Arc($n[4], $n[13], 40),
new Arc($n[5], $n[4], 43),
new Arc($n[6], $n[1], 41),
new Arc($n[6], $n[4], 46),
new Arc($n[7], $n[0], 11),
new Arc($n[7], $n[3], 40),
new Arc($n[8], $n[9], 21),
new Arc($n[8], $n[22], 18),
new Arc($n[9], $n[10], 15),
new Arc($n[9], $n[22], 20),
new Arc($n[10], $n[11], 15),
new Arc($n[10], $n[15], 2),
new Arc($n[11], $n[12], 7),
new Arc($n[11], $n[18], 25),
new Arc($n[12], $n[16], 27),
new Arc($n[13], $n[14], 40),
new Arc($n[14], $n[12], 40),
new Arc($n[15], $n[16], 21),
new Arc($n[16], $n[17], 13),
new Arc($n[17], $n[11], 15),
new Arc($n[18], $n[19], 40),
new Arc($n[19], $n[20], 40),
new Arc($n[20], $n[1], 16),
new Arc($n[15], $n[21], 18),
new Arc($n[16], $n[21], 36),
new Arc($n[21], $n[23], 15),
new Arc($n[22], $n[18], 19),
new Arc($n[21], $n[23], 19),
new Arc($n[23], $n[24], 15),
new Arc($n[24], $n[25], 27),
new Arc($n[25], $n[26], 26),
new Arc($n[26], $n[27], 42),
new Arc($n[26], $n[28], 41),
new Arc($n[27], $n[29], 40),
new Arc($n[28], $n[30], 35),
new Arc($n[30], $n[31], 14),
new Arc($n[31], $n[32], 41),
new Arc($n[32], $n[33], 38),
new Arc($n[32], $n[34], 26),
new Arc($n[34], $n[33], 40),
new Arc($n[33], $n[1], 38),
new Arc($n[33], $n[6], 43),
new Arc($n[33], $n[54], 42),
new Arc($n[54], $n[7], 16),
new Arc($n[30], $n[35], 10),
new Arc($n[35], $n[36], 5),
new Arc($n[36], $n[37], 15),
new Arc($n[37], $n[38], 19),
new Arc($n[38], $n[39], 7),
new Arc($n[39], $n[40], 12),
new Arc($n[40], $n[55], 7),
new Arc($n[55], $n[56], 4),
new Arc($n[56], $n[57], 5),
new Arc($n[57], $n[49], 5),
new Arc($n[49], $n[50], 6),
new Arc($n[50], $n[51], 3),
new Arc($n[51], $n[52], 2),
new Arc($n[52], $n[40], 4),
new Arc($n[50], $n[46], 8),
new Arc($n[46], $n[47], 12),
new Arc($n[47], $n[48], 8),
new Arc($n[48], $n[26], 18),
new Arc($n[38], $n[43], 10),
new Arc($n[43], $n[44], 13),
new Arc($n[44], $n[45], 7),
new Arc($n[45], $n[46], 8),
new Arc($n[0], $n[41], 12),
new Arc($n[41], $n[42], 10),
new Arc($n[42], $n[38], 8),
new Arc($n[55], $n[53], 7),
new Arc($n[53], $n[41], 8),
new Arc($n[41], $n[53], 5),
new Arc($n[53], $n[0], 12),
new Arc($n[55], $n[58], 12),
new Arc($n[58], $n[60], 7),
new Arc($n[60], $n[61], 18),
new Arc($n[61], $n[10], 9),
new Arc($n[61], $n[9], 10),
new Arc($n[58], $n[62], 12),
new Arc($n[62], $n[63], 18),
new Arc($n[63], $n[8], 10)
);
$graphe = new Graphe($n, $tab_arc);
$dij = new Dijkstra($graphe);
// echoln("Liste des arcs du graphe :");
// $graphe->print_arcs();
/*
echoln("exemple 1 : distance minimale entre deux villes pour lesquelles il y a au moins un chemin");
$rc = $dij->setDepart($n[34]);
$rc = $dij->setArrivee($n[56]);
if ($rc === true) {
if ($dij->recherche()) {
$chemin_str = $dij->get_string_chemin();
echoln("chemin : $chemin_str");
echoln("la distance la plus courte entre le noeud " . $dij->getDepart() . " et le noeud " . $dij->getArrivee() . " est " . $dij->getDistance_minimale());
}
else echoln("Il n'y a pas de chemin entre " . $dij->getDepart() . " et " . $dij->getArrivee());
}
else {
echoln("Erreur d'initialisation");
}
echoln("");
echoln("exemple 2 : distance minimale entre deux villes pour lesquelles il n'y a pas de chemin");
$rc = $dij->setDepart($n[18]);
$rc = $dij->setArrivee($n[5]);
if ($rc === true) {
if ($dij->recherche()) {
$chemin_str = $dij->get_string_chemin();
echoln("chemin : $chemin_str");
echoln("la distance la plus courte entre le noeud " . $dij->getDepart() . " et le noeud " . $dij->getArrivee() . " est " . $dij->getDistance_minimale());
}
else echoln("Il n'y a pas de chemin entre " . $dij->getDepart() . " et " . $dij->getArrivee());
}
else {
echoln("Erreur d'initialisation");
}
# pour calculer tous le chemin le plus court pour toute les paires de noeuds du graphe
# prévoir d'allonger la durée maximale d'exécution du script php à 5 minutes en modifiant le fichier php.ini :
# max_execution_time = 300
foreach($graphe->getTab_noeud() as $noeud_depart) {
foreach($graphe->getTab_noeud() as $noeud_arrivee) {
$rc = $dij->setDepart($noeud_depart);
$rc = $dij->setArrivee($noeud_arrivee);
if ($dij->recherche()) {
$chemin_str = $dij->get_string_chemin();
echoln("chemin : $chemin_str");
echoln("la distance la plus courte entre le noeud " . $dij->getDepart() . " et le noeud " . $dij->getArrivee() . " est " . $dij->getDistance_minimale());
}
else echoln("Il n'y a pas de chemin entre " . $dij->getDepart() . " et " . $dij->getArrivee());
}
}
?>
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.