Algorithme pour trouver un chemin.. Particulier

L'auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

Bonjour, je suis à la recherche d'un algorithme pour trouver un chemin entre un point et un ensemble de points.

Je connais l'existence d'algorithmes de plus court chemin, mais premièrement je veux juste qu'un chemin existe, deuxièmement je dois tester sur un ensemble de point, ce qui pourrait peut être s'avérer couteux ?

Je me suis donc dis qu'un algorithme vérifiant la connexité serait peut être plus adapté. Est-ce le cas ? Est-ce du coup plus coûteux ?

Dans mon problème le nombre de sommet n'est pas très haut (81) et le nombre de lien (non-orienté et non valué) de maximum 300.

Merci

+0 -0

Salut,
si tu utilises l'algorithme de Floyd-Warshall tu auras le poids du plus court chemin entre chaque pairs de points de ton graphe. Tu dois pouvoir adapter cet algo pour qu'il ne te resorte que les plus courts chemins par rapport à un point.

Édité par SeeoX

+0 -0
Auteur du sujet

@Yoch

Le jeu s'appel Quoridor. Le principe c'est d'amener ton pion de l'autre côté sauf que l'adversaire peut poser des barrières pour bloquer ton chemin. Il n'y à qu'une seule règle : il doit toujours exister un chemin entre le pion et l'autre côté.

Donc un seul des points suffit. Sauf que l'ensemble des points que l'on doit pouvoir atteindre n'est pas necessairement connexe.

+0 -0

Vu le jeu en question, un simple parcours en largeur/profondeur depuis ta position suffit: si l'un des points est atteint en cours de parcours il existe donc un chemin, sinon il n'y en a pas.

+1 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte