Discussion :

[lordfiren]

Bonjour,

Je souhaiterais connaitre le chemin le plus long dans un graphe (avec un point de départ et d'arrivé quelconque), et j'ai pensé à utiliser un DFS. Est-ce la solution la plus simple et optimisée, selon vous?
A vrai dire, je ne suis même pas sûr que cette solution soit fonctionnelle ; après avoir vu la vidéo suivante (www.youtube.com/watch?v=zLZhSSXAwxI), les chemin empruntés ne contiennent pas la solution.ul

[ternel]

Que veux-tu précisément.
Trouver le plus long chemin entre deux noeuds donnés? trouver la paire de noeud ayant la plus grande distance entre eux?

Dans tous les cas, il faut choisir une représentation d'un chemin (avec sa longueur). Ca peut être une liste chainée de noeud.
Commence peut-être par là?

[lordfiren]

Je cherche à trouver la paire ayant la plus grande distance entre elle, de plus, les noeuds n'ont pas de poids (tous à 1).

Pour l'instant, je stock mes noeuds de la façon suivante:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
typedef struct s_node
{
	int id;
	struct s_node *neighbor;
} t_node;

J'ai donc un tableau de nodes (je connais le nombre d'elements a l'avance), ayant chacun a l'intérieur une ID, et une liste chainée de node représentant leurs voisins (je ne connais pas le nombre de voisins a l'avance).

en gros:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
t_node *node;
node[0] = id:0, neighbor:2->3
node[1] = id:1, neighbor:1->3
node[2] = id:2, neighbor:0
node[3] = id:3, neighbor:0->1

par exemple.

Voila, désolé pour les quelques imprécisions de mon premier message,
merci d'avance pour vos conseils.

[Invité]

BFS et DFS sont deux manières de parcourir un arbre/graphe. Mais il faudra malgré tout parcourir toute la structure pour connaitre le chemin (la branche) le plus long.

[dinobogan]

Quelle est la volumétrie de noeuds et d'arêtes ? Quel est le temps approximatif qu'il ne faudrait pas dépasser ? De quelles ressources disposes-tu sur la machine (nombre de CPU, taille de RAM) ?

[lordfiren]

Quelle est la volumétrie de noeuds et d'arêtes ?
Un nombre quelconque, mais en moyenne quelques dizaines.

Quel est le temps approximatif qu'il ne faudrait pas dépasser ?
Il n'y a pas réellement de temps, mais moins de trente secondes serait bien.

De quelles ressources disposes-tu sur la machine (nombre de CPU, taille de RAM) ?
3 Ghz et 8 Go.

[dinobogan]

Tu peux faire une recherche systématique en profondeur, comme tu l'as dit.
Par exemple, tu peux ajouter un booléen dans chaque noeud, initialisé à faux au départ. Une liste chaînée résultat est mise à vide.
Une fonction récursive va parcourir les noeuds jusqu'à l'arrivée. A chaque passage dans un noeud non marqué, tu ajoutes le noeud dans une liste chainée et tu marques le noeud à vrai. Lorsque la fonction récursive arrive au noeud final, si la liste chaînée est plus longue que la liste chaînée résultat, alors tu écrases la liste chaînée résultat par cette nouvelle chaîne. Dans la récursion, après avoir parcouru un noeud, tu le remets à faux.
Tu es certain de trouvé le chemin le plus long, par contre c'est la méthode naïve qui va parcourir toutes les combinaisons possibles. Si le temps de traitement te suffit, alors tu peux t'arrêter là.

[lordfiren]

Merci,
J'ai réussi à faire cette solution qui semble fonctionner , mais n'y a t'il pas une solution plus propre/rapide ?

[dinobogan]

C'est une solution que je trouve très propre. Mais tout dépend de tes critères de propreté
Pour ce qui est de la rapidité d'exécution, qu'as-tu constaté avec ton programme ? As-tu fais quelques tests de temps d'exécution en fonction de la complexité du graphe en entrée ?

[lordfiren]

Nn mais je pensais qu'il existait une solution, avec un algo fait pour ça, car là les temps sont exponentiels, plus je rajoute de noeuds plus cela prend du temps.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
time ./a.out "5-4 9-4 4-6 1-9 4-8 2-6 2-8 4-8 4-9 3-8 1-8"
7
0.003 total
 
time ./a.out "5-4 9-4 4-6 1-9 4-8 2-6 2-8 4-8 4-9 3-8 1-8 5-8 4-9 2-8 3-9 4-9 4-6 5-9 2-8 4-7 2-2 1-1 8-8 7-7 7-7 7-7 7-7 7-7"
9
0.047 total
 
time ./a.out "5-4 9-4 4-6 1-9 4-8 2-6 2-8 4-8 4-9 3-8 1-8 5-8 4-9 2-8 3-9 4-9 4-6 5-9 2-8 4-7 2-2 1-1 8-8 7-7 7-7 7-7 7-7 7-7 5-7 5-2 5-6 5-8 4-8 4-8 6-9 4-7 2-4 1-5 4-8"
10
1.627 total

[ternel]

C'est plus un problème de mathématiques que de code.
Alors c'est pas forcément ici qu'il faut chercher, mais dans un cours de théorie des graphes, ou dans le forum algorithmes.

Tu dois trouver le meilleur élément de l'ensemble des chemins du graphe.
Cet ensemble est a peu près de la taille de l'ensemble des permutations des aretes, c'est à dire factorielle(nombre aretes).

L'astuce est de te débrouiller pour classer les chemins rapidement, puis de prendre le premier.

Supposons que tu aies un graphe orienté.
Alors s'il n'a pas de cycle, il y a un ordre partiel entre les noeuds.

Ca peut être une piste.