Поиск кратчайшего пути Опции

[AlexPS]

Вот такая у меня задача:

Задана матрица натуральных чисел А[1..n,1..m]. За каждый проход через клетку (i,j) взфмается штраф A[i,j]. Необходимо минимизировать штраф и пройти
из какой-либо клетки (i1,j1) в (i1,j1).

В FAQ я почитал про алгоритм дейкстры... А как бы мне перенести его на мою задачу? Сложность в том, что начальной и конечной точкой пути может быть абсолютно любая клетка матрицы..

[virt]

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

но если в нем есть проход по одной клетке 2 раза ,то это не будет самым дешевым путем ,если из пути удалить клетки пройденные между этими двумя вхождениями на одну клетку ,то и длина пути и стоимость сократятся.

самый эффективный метод -- алгоритм дейкстры. Или метод предложенный mlc. Перебор при n+m > 15 не пройдет по времени.

[Malice]

но если в нем есть проход по одной клетке 2 раза ,то это не будет самым дешевым путем...

Проход 2 раза имеется в виду в процессе поиску пути, а не в конечном варианте, конечно же Просто в волновом алгоритме (классическом) значение в куждую клетку пишется 1 раз, а здесь возможен повторный проход. Поэтому, кстати, рекурсия в итоге выльется в полный перебор.
А может и вру, ни кто не хочет попробовать?