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.