Sujet Précédent Sujet Suivant

Recherche d'un chemin dans une table

diafwl1 Messages postés 52 Date d'inscription mercredi 27 avril 2005 Statut Membre Dernière intervention 5 août 2008 - 13 janv. 2006 à 15:55
diafwl1 Messages postés 52 Date d'inscription mercredi 27 avril 2005 Statut Membre Dernière intervention 5 août 2008 - 31 janv. 2006 à 11:10
Bonjour, j'ai un problème pour réaliser une fonction qui me permette de rechercher un chemin dans ma base de données.

Par exemple prennons une table qui contient 3 champs (par exemple), dans le 1er champs se trouve un ID, dans le 2nd un nom,de ville par exemple, et dans le 3éme un autre nom de ville, une ligne correspond à ville 1 est relier à ville2.



ex du contennu de la table :



| ID | nom 1 | nom 2 |

| 1 | AAA | BBB |

| 2 | CCC | AAA |

| 3 | BBB | DDD |

| 4 | AAA | YYY |

| 5 | EEE | YYY |

| 6 | DDD | EEE |



Si l'utilisateur demande par exemple les chemins pour relier AAA à YYY, le progrmme devra donner comme reponse :

1 - AAA | BBB

1 - BBB | DDD

1 - DDD | EEE

1 - EEE | YYY

2 - AAA | YYY



Je n'ai aucun pb pour afficher ce genre de réponse.

Pour engendrer cette réponse je parcours la table à la recherche de
la ville de depart, ensuite si je la trouve je mets le nom dans un
tableau à 2 dimensions(chaque ligne correspond à un chemin possible
entre 2 villes), et je reparts de la 2éme ville(devient la nouvelle
ville de depart), ainsi de suite jusqu'à temps de trouver le nom de la
ville finale.

Mon problème est que le programme s'arrète si jamais il rentre (dans l'exemple) dans la 2éme ligne, il affichera :

1 - AAA | CCC

Je ne trouve pas comment faire pour revenir en arrière et repartir par un autre chemin (je pense qu'il faut utiliser un arbre n-aire mais je ne sais pas comment l'écrire!)

6 réponses

Réponse 1 / 6
obcstaff Messages postés 147 Date d'inscription mardi 15 novembre 2005 Statut Membre Dernière intervention 28 janvier 2008
18 janv. 2006 à 09:47
Ah oui, c'est quand meme tendu comme probleme, c'est exactement comme
les matrices en maths, je suis dessus j'essaierais de te proposer une
solution dans la journée...



++
0
Réponse 2 / 6
diafwl1 Messages postés 52 Date d'inscription mercredi 27 avril 2005 Statut Membre Dernière intervention 5 août 2008
18 janv. 2006 à 10:21
Voici une partie de mon programme si sa aide :

echo"\";
$new_result = mysql_query(\"SELECT * FROM rech\");
$nb_new_row = mysql_num_rows($new_result);
// on affiche la table (pour veriffie le resultat)
for($i=0;$i<$nb_new_row;$i++)
{
mysql_data_seek($new_result,$i);
$champs=mysql_fetch_array($new_result);
echo \"----
\";
echo''.$champs[0].', '.$champs[1].', '.$champs[2].', ';
echo\"\";
}
echo"
";

$chemin=array(); // tableau qui ne contiendra qu'un chemin
$result_chemin=array(); // tableau qui contiendra tous les chemins possible
$prohib=array(); // on entrera l'ID pour ne plus repasser par ce chemin
$x=$y=$nb_chemin=$nb_passage=0;
$trouve=false;
$continue=true;
$new_depart=$recu_depart; // on ne modifira que new_depart
$new_arrive=$recu_arrive;
//while(!$fin)
$new_result = mysql_query("SELECT * FROM rech");
$nb_new_row = mysql_num_rows($new_result);
for($i=0;($i<$nb_new_row);$i++)
{
mysql_data_seek($new_result,$i);
$champs=mysql_fetch_array($new_result);
if(($champs[1]==$new_depart)&&(!in_array($champs[0],$prohib)))
{
if($champs[2]==$recu_arrive)
{
array_push($chemin,$champs[1],$champs[2]); // on ajoute a la fin de chemin les champs 1 et 2
array_push($result_chemin,$chemin); // comme le chemin est complet on le rentre dans result_chemin
$prohib[$x++]=$champs[0];
$chemin=array(); // on reinitialise chemin
}
else
{
if(rech_suite($champs[2])) // on verrifie si on est n'est pas dans un cue-de-sac
{
array_push($chemin,$champs[1]);
$new_depart=$champs[2];
$prohib[$x++]=$champs[0];
}
else
{
if(!rech_suite($champs[1])) // dans le cas ou on est dans un cue-de-sac,
// et qu'il n'y a pas d'autre chemin en partant de la valeur dans le champs 1
{
$new_depart=$chemin[count($chemin)-1]; // on reprend la valeur de depart precedente
unset($chemin[count($chemin)-1]); // on supprime la dernière valeur
$prohib[$x++]=$champs[0];
}
}
$i=-1;
}
}
else
if(($champs[2]==$new_depart)&&(!in_array($champs[0],$prohib)))
{
if($champs[1]==$recu_arrive)
{
array_push($chemin,$champs[2],$champs[1]);
array_push($result_chemin,$chemin);
$prohib[$x++]=$champs[0];
$chemin=array();
}
else
{
if(rech_suite($champs[1]))
{
array_push($chemin,$champs[2]);
$new_depart=$champs[1];
$prohib[$x++]=$champs[0];
}
else
{
if(!rech_suite($champs[2]))
{
$new_depart=$chemin[count($chemin)-1];
unset($chemin[count($chemin)-1]);
$prohib[$x++]=$champs[0];
}
}
$i=-1;
}
}
}

// fonction permettant de verrifier si on peut continuer dans cette voie, verrifie si on est pas dans un cue de sac
function rech_suite($a)
{
global $new_result;
global $nb_new_row;
global $prohib;
$trouve=false;
for($j=0;(($j<$nb_new_row)&& !$trouve);$j++)
{
mysql_data_seek($new_result,$j);
$ch=mysql_fetch_array($new_result);
if((($a==$ch[1])||($a==$ch[2]))&&(!in_array($ch[0],$prohib)))
$trouve=true;
}
return $trouve;
}

echo "";
print_r($chemin);
echo "

";
echo "";
print_r($result_chemin);
echo "

";
echo "";
print_r($prohib);
echo "

";

à la fin on doit pouvoir afficher plusieurs chemins dans result_chemin et aucun dans chemin, or je n'obtient qu'un seul chemin (lorsque plusieurs existent) dans result_chemin, deplus il bloque toujours lorsqu'il se trouve dans un cue-de-sac !!
0
Réponse 3 / 6
diafwl1 Messages postés 52 Date d'inscription mercredi 27 avril 2005 Statut Membre Dernière intervention 5 août 2008
18 janv. 2006 à 10:33
A la place de :
if(!rech_suite($champs[1])) // dans le cas ou on est dans un cue-de-sac,
// et qu'il n'y a pas d'autre chemin en partant de la valeur dans le champs 1
{
$new_depart=$chemin[count($chemin)-1]; // on reprend la valeur de depart precedente
unset($chemin[count($chemin)-1]); // on supprime la dernière valeur
$prohib[$x++]=$champs[0];
}

j'ai rajouté :
if(!rech_suite($champs[1]))

{
if (count($chemin)!=0) // dans le cas ou le chemin est vide
{
$new_depart=$chemin[count($chemin)-1];
unset($chemin[count($chemin)-1]);
}
else
break;
}

(idem pour champs[2])
0
Réponse 4 / 6
diafwl1 Messages postés 52 Date d'inscription mercredi 27 avril 2005 Statut Membre Dernière intervention 5 août 2008
18 janv. 2006 à 12:29
En fait j'ai separé le programme en 2 fonction :

function chemin_direct($dep,$arr)
{
global $nb_new_row;
global $new_result;
global $result_chemin;
global $prohib;
global $x;
$direct=false;
$chemin=array();
for($i=0;(($i<$nb_new_row)&&!$direct);$i++)
{
mysql_data_seek($new_result,$i);
$ch=mysql_fetch_array($new_result);
if(($ch[1]==$dep)&&(!in_array($ch[0],$prohib)))
{
if($ch[2]==$arr)
{
array_push($chemin,$ch[1],$ch[2]);
array_push($result_chemin,$chemin);
$prohib[$x++]=$ch[0];
$chemin=array();
$direct=true;
}
}
else
if(($ch[2]==$dep)&&(!in_array($ch[0],$prohib)))
{
if($ch[1]==$arr)
{
array_push($chemin,$ch[2],$ch[1]);
array_push($result_chemin,$chemin);
$prohib[$x++]=$ch[0];
$chemin=array();
$direct=true;
}
}
}
return $direct;
}

function chemin_indirect($dep,$arr)
{
global $new_result;
global $nb_new_row;
global $prohib;
global $x;
global $result_chemin;
$new_depart=$dep;
$new_arrive=$arr;
$chemin=array();
$indirect=false;
for($i=0;(($i<$nb_new_row)&&!$indirect);$i++)
{
mysql_data_seek($new_result,$i);
$champs=mysql_fetch_array($new_result);
if(($champs[1]==$new_depart)&&(!in_array($champs[0],$prohib)))
{
if($champs[2]==$new_arrive)
{
array_push($chemin,$champs[1],$champs[2]);
array_push($result_chemin,$chemin);
$prohib[$x++]=$champs[0];
$indirect=true;
}
else
{
if(rech_suite($champs[2]))
{
array_push($chemin,$champs[1]);
$new_depart=$champs[2];
//$prohib[$x++]=$champs[0];
}
else
{
if(!rech_suite($champs[1]))
{
if (count($chemin)!=0)
{
$new_depart=$chemin[count($chemin)-1];
unset($chemin[count($chemin)-1]);
}
else
break;
$prohib[$x++]=$champs[0];
}
}
$i=-1;
}
}
else
if(($champs[2]==$new_depart)&&(!in_array($champs[0],$prohib)))
{
if($champs[1]==$new_arrive)
{
array_push($chemin,$champs[2],$champs[1]);
array_push($result_chemin,$chemin);
$prohib[$x++]=$champs[0];
$indirect=true;
}
else
{
if(rech_suite($champs[1]))
{
array_push($chemin,$champs[2]);
$new_depart=$champs[1];
$prohib[$x++]=$champs[0];
}
else
{
if(!rech_suite($champs[2]))
{
if (count($chemin)!=0)
{
$new_depart=$chemin[count($chemin)-1];
unset($chemin[count($chemin)-1]);
}
else
break;
$prohib[$x++]=$champs[0];
}
}
$i=-1;
}
}
}
return $indirect;
}
0

Vous n’avez pas trouvé la réponse que vous recherchez ?

Posez votre question
Réponse 5 / 6
diafwl1 Messages postés 52 Date d'inscription mercredi 27 avril 2005 Statut Membre Dernière intervention 5 août 2008
18 janv. 2006 à 20:52
Mais je ne vois tjs pas pourquoi sa ne marche pas pour la recherche indirect
0
Réponse 6 / 6
diafwl1 Messages postés 52 Date d'inscription mercredi 27 avril 2005 Statut Membre Dernière intervention 5 août 2008
31 janv. 2006 à 11:10
et vous?
0

Discussions similaires

Barre de recherche web
martial30061999 -
HitTshite19 -

1 réponse
ISBN recherche web
cs_etniqs -
digger23 -

2 réponses
Comment Ajouter et supprimer une ligne dans une JTable
cs_redbar -
redbar -

2 réponses
requete SQL pour ajouter un champ dans une table
bakchlada -
bakchlada -

5 réponses
recherche dans base mysql
karlito911 -
kohntark -

119 réponses
Rejoignez-nous