Алгоритм поиска маршрута?

Question

[Тамаз Харламов]

Учусь python и задался вопросом, а как искать самый быстрый путь через точки которые связаны друг с другом в хаотичном порядке. но порядок связей никогда не меняется. Связи на фото ниже.
Интересен сам алгоритм.
Необходимо из зеленой точки перебраться в красную. Линии это связи через которые можно перейти на следующую точку.

Answer 1

[Wataru]

В питоне есть библиотека для работы с графами NetworkX. И там есть уже реализованные алгоритмы кратчайших путей.

Это будет быстрее, чем самостаятельно реализовывать какой-нибудь алгоритм Дейкстры или обход в ширину, ибо питон - безбожно тормознутый язык. А в библиотеке вычисления обычно реализованы на более быстрых языках.

Comments

[Тамаз Харламов]

Спасибо!

Answer 2

[alexalexes]

Отложите питон в сторонку, откройте книжку по дискретной математике, на разделе теории графов. Изучите алгоритм Дейкстры, посидите пару часов с карандашом и листочком, промоделируйте на бумаге, как он работает.

Comments

[Тамаз Харламов]

Спасибо. буду пробовать.

Answer 3

[Alexandroppolus]

Если линии, связывающие точки, одинаковы по стоимости/весу/длине, то проще всего поиск в ширину