par
Sékiltoyai » 29 juil. 2008, 02:33
le problème que je vois est que je ne connais pas par avance le nombre de sommets desquels A est le prédécesseur...
En effet, le graphe que j'ai mis est très simplifié et je pourrais avoir par exemple à chercher, sur un ensemble de 100 sommets et en prenant le 25ème comme origine et le 85ème comme arrivée le chemin le plus court entre les deux. Or, dans ce cas, je ne saurai jamais quels sont (en volume et en quantitatif) le nombre de prédecesseurs du 85ème...
Ma solution demande à ce que tu aies récupéré l'ensemble de la table. Dans la mesure où cela pourraît être important en transit de données, je te suggère d'utiliser des procédures stockées et de faire exécuter le travail directement par le serveur SQL…
D'autre part, il y a une notion très importante qu'il faut prendre en compte, c'est les SENS des flèches. Je mettais dans mon 1er post que le graphe est orienté mais l'exemple que je donne n'est peut-être pas bon car on ne voit pas un "retour en arrière".
Aussi, il se peut qu'on ait à un moment ou un autre un groupe de sommets qui fasse un boucle... et là, il faudra sortir de la boucle...
Ne t'en fait pas, j'y ai pensé, mon algorithme s'arrête automatiquement d'explorer un chemin s'il est dans une boucle, puisque s'il revient à un sommet déjà défini, il l'ignore. Si une boucle part de E, une fois que l'analyse reviendra en E, elle s'arrêtera d'explorer ce chemin puisque E est déjà dans le tableau des résultats.
PS : dans la mesure où c'est un graphe non pondéré, je ne veux pas récupérer la valeur (je ne peux pas); pour moi tous les arcs valent "1". Le chemin le plus court entre deux points que je pourrai choisir, devra être celui qui utilise le moins d'arcs possibles.
Disons que je ne partais pas du principe d'un graphe pondéré, c'est vrai qu'en y réfléchissant, vu que la valeur n'est pas utilisée, tu peux la remplacer par un tableau définissant le chemin. Par exemple :
array(
'B' => array('A', 'B'), // On a un chemin direct entre A et B
'C' => array('A', 'C'),
'D' => array('A', 'B', 'D'),
'E' => array('A', 'B', 'D', 'E') // Le chemin A->E passe par B et D
);
L'implémentation est assez immédiate, il faudra juste, en fonction de tes obligations, optimiser la communication php <-> mysql soit en faisant tout faire par mysql, soit en faisant tout faire par php, soit en rusant avec une solution qui récupérerait le minimum de données mais en un minimum de fois…
[quote="Hervé21"]
le problème que je vois est que je ne connais pas par avance le nombre de sommets desquels A est le prédécesseur...
En effet, le graphe que j'ai mis est très simplifié et je pourrais avoir par exemple à chercher, sur un ensemble de 100 sommets et en prenant le 25ème comme origine et le 85ème comme arrivée le chemin le plus court entre les deux. Or, dans ce cas, je ne saurai jamais quels sont (en volume et en quantitatif) le nombre de prédecesseurs du 85ème... :? [/quote]
Ma solution demande à ce que tu aies récupéré l'ensemble de la table. Dans la mesure où cela pourraît être important en transit de données, je te suggère d'utiliser des procédures stockées et de faire exécuter le travail directement par le serveur SQL…
[quote="Hervé21"]
D'autre part, il y a une notion très importante qu'il faut prendre en compte, c'est les SENS des flèches. Je mettais dans mon 1er post que le graphe est orienté mais l'exemple que je donne n'est peut-être pas bon car on ne voit pas un "retour en arrière".
Aussi, il se peut qu'on ait à un moment ou un autre un groupe de sommets qui fasse un boucle... et là, il faudra sortir de la boucle... :wink: [/quote]
Ne t'en fait pas, j'y ai pensé, mon algorithme s'arrête automatiquement d'explorer un chemin s'il est dans une boucle, puisque s'il revient à un sommet déjà défini, il l'ignore. Si une boucle part de E, une fois que l'analyse reviendra en E, elle s'arrêtera d'explorer ce chemin puisque E est déjà dans le tableau des résultats.
[quote="Hervé21"]
PS : dans la mesure où c'est un graphe non pondéré, je ne veux pas récupérer la valeur (je ne peux pas); pour moi tous les arcs valent "1". Le chemin le plus court entre deux points que je pourrai choisir, devra être celui qui utilise le moins d'arcs possibles.[/quote]
Disons que je ne partais pas du principe d'un graphe pondéré, c'est vrai qu'en y réfléchissant, vu que la valeur n'est pas utilisée, tu peux la remplacer par un tableau définissant le chemin. Par exemple :
[php]array(
'B' => array('A', 'B'), // On a un chemin direct entre A et B
'C' => array('A', 'C'),
'D' => array('A', 'B', 'D'),
'E' => array('A', 'B', 'D', 'E') // Le chemin A->E passe par B et D
);[/php]
L'implémentation est assez immédiate, il faudra juste, en fonction de tes obligations, optimiser la communication php <-> mysql soit en faisant tout faire par mysql, soit en faisant tout faire par php, soit en rusant avec une solution qui récupérerait le minimum de données mais en un minimum de fois…
