Классическая задача, помогите найти подходы к ней
Имеется N населенных пунктов , пронумерованных от 1 до N. Некоторые пары пунктов соединены дорогами. вывести самый короткий путь из L-го пункта в M-й. Информация о дорогах задается в виде последовательности пар чисел i и j (i < j), указывающих, что i-й и j-й пункты соединены дорогой, признак конца этой последовательности - пара нулей.
решите в лоб для начала
начните двигаться от L-го пункта во все возможные пункты
каждый шаг вычисляйте пройденное расстояние (в L-ом пункте оно будет 0)
запоминайте каждый вычисленный путь в массив (в виде пунктов которые прошли, например [7,5,11,6]
если в каком-то пункте вы ранее уже были и расстояние до него меньше, чем текущее, то текущую ветку не продолжайте - она гарантированно будет хуже
каждый рассмотренный пункт помечайте как пройденный (чтоб не закольцовывать маршруты)
в конечном итоге у вас останется оптимальный (кратчайший путь)
ну и еще это можно сделать рекурсивно, но лучше итерационно - это не так стек перегружает, а скорость работы схожая плюс-минус
Достаточно здравый подход к задаче(в рамках обучения) - алгоритм Дейкстры, он самый простой, как по мне(если исключить полный перебор). Я его весь в ответе расписывать не смогу и не буду, поэтому приложу материалы, по которым сам учился