Chemin le plus simple entre les points

Question

J'ai une liste de points (coordonnées x, y) et une liste de connexions entre eux. Exemples:

Points A B C D E

Connexions AB BC CE BD

D E 
    | | 
A-B-C 

Bien sûr, il y a beaucoup plus de points et de connexions que cela. ..

Ce dont j'ai besoin o est de trouver le chemin le plus simple entre certains de ces points. Par exemple, si je voulais aller à A, C et D, je voudrais utiliser les connexions AB, BC et BD.

Existe-t-il un moyen de calculer ceci pour n'importe quel ensemble de points que je veux connecter?

Answer 1

Étant donné que vous n'indiquez aucun coût associé aux arêtes, un Breadth First Search est probablement ce que vous recherchez. Il trouve le chemin le plus court d'un nœud donné à tous les autres nœuds (le cas échéant), je suppose que c'est ce que vous entendez par «plus simple».