Discussion :

[Sve@r]

Bonjour à tous

J'ai un soucis d'algorithmique avec la théorie des graphes.

Prenons par exemple un graphe où l'ensemble des arrêtes ne peut pas reboucler, comme illustré ici


Si on part du sommet "0" et qu'on compte "1" à chaque niveau, il faudra alors 4 itérations pour atteindre l'ensemble des sommets


Si maintenant on part du sommet "2", alors il ne faudra plus que 2 itérations


Mon problème est de trouver ce sommet "2" permettant à un fluide qui s'en écoulerait d'atteindre tous les autres en un minimum d'itération. J'ai écrit un algorithme récursif qui pour un sommet donné me donne la profondeur maximale du graphe mais c'est trop long de tout tester. Même en optimisant en fournissant à mon algorithme la profondeur minimale déjà trouvée pour un sommet "X" et en le faisant s'arrêter dès qu'il descend plus bas en testant le sommet "Y" c'est encore trop long.

Donc ma question: y a-t-il un autre moyen de trouver ce "sommet 2" sans tout tester ???

Merci de votre attention