Простейший путь между точками

Question

У меня есть список точек (координаты x, y) и список связей между ними. Примеры:

Очки В С D E

Соединение AB До нашей эры CE BD

  D E
  | |
A-B-C

Конечно, есть гораздо больше точек и связей, чем эта ...

Что мне нужно сделать, так это найти простейший путь между некоторыми из этих точек. Например, если бы я хотел перейти к A, C и D, я бы хотел использовать соединения AB, BC и BD.

Есть ли способ вычислить это для любого набора точек, которые я хочу подключить?

Answer 1

Поскольку вы не указываете, что с ребрами связаны какие-либо затраты, Поиск в ширину , вероятно, то, что вы ищете. Он находит кратчайший путь от данного узла ко всем остальным узлам (если таковые существуют), я предполагаю, что это то, что вы подразумеваете под «самым простым».