Как посчитать кратчайший путь между двумя точками, используя матрицу чисел?

Question

[Arti-Jack]

Всех приветствую.

Пишу так называемый Алгоритм Ли (он же унарный/волновой поиск).
Если вкратце, то суть состоит в следующем:
Мы заполняем матрицу числами, перемещаясь волной от точки А до точки В.

Пример:


В общем, написать функцию, которая смогла так заполнить матрицу, мне удалось. Я использовал рекурсивные вызовы для левой/правой/верхней/нижней позиции и заполнял сам массив. Но вопоос в следующем: как мне теперь посчитать кратчайший путь?

P.S: Писал я код на Java, но это не имеет весомого значения. Так что можете привести пример на любом языке (но желательно си-подобном или на питоне).

Comments

[Max Payne]

Это задание, а не вопрос.

[Arti-Jack]

Arti Markelov, заданием это было бы, если я попросил бы полностью написать волновой поиск. Я лишь спросил как мне посчитать кратчайший путь, хотя бы идею

[Max Payne]

Arti-Jack, отредактируйте ответ прикрепив саму функцию. Так будет лучше.

[Arti-Jack]

Arti Markelov, но ведь эта функция никак не повлияет на сам вопрос. Мне нужно по матрице чисел найти кратчайший путь. Какая разница, каким образом я получил саму матрицу чисел. Это никакой роли не играет в данном вопросе :/

Answer 1

[Денис Загаевский]

Начиная из конечной точки просто идёшь всегда в сторону наименьшего числа.

Comments

[Arti-Jack]

Т.е мне по сути надо пустить волну от конечной точки, которая всегда "идёт на меньшее число"?

[Денис Загаевский]

Arti-Jack, В смысле волну? есть заполненный массив. В конечной точке ищешь вокруг минимум, идешь в него. Повторяешь до тех пор, пока не дойдёшт до начальной точки.