Algorithme pour trouver un chemin.. Particulier

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

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

Que veux-tu dire exactement ?

Imagine un echequier avec des obstacles. J'aimerais savoir s'il existe en chemin entre une case et un côté

et bin plus court chemin et des que ça touche une seul case du groupe c'est bon. Ca a la meme complexité que pour d'un point à un autre.

Oui mais ce groupe pourrait être divisé en plusieurs, c'est de la que vient mon problème. Mais si c'est aussi simple cool !

Il suffit qu'un seul de l'ensemble des points soit atteint, ou bien tous doivent pouvoir l'être ?

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.

@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.

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.

Ou un algorithme de propagation (ça sera plus simple à coder, et pas plus long à exécuter)