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

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

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

Можно и волновым методом, только не 1-цу прибавлять а вес ячейки.

А можно поподробнее, что это за алгоритм... или где-нибудь пример можно посмотреть?

http://algolist.manual.ru/games/wavealg.php
или google.com

Алгоритм дейкстры, волновой метод... Зачем? Тут банальный перебор с некоторыми ограничениями. Следует использовать тот факт, что проходить через клетку повотрно - бессмысленно, так как в таком случае штраф явно будет НЕ минимальным. Попробуй рекурсию.

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

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

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

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

:no: Уже пробовал как-то, была подобная задача... Рекурсию делать не стоит, будет именно полный перебор, я все-таки остановился на алгоритме Дейкстры.

А если ограничить пребор прохождением по клетке 2-ой раз? Если клетка уже встречалась, берём следующий вариант. А алгоритм Дейкстры и волновой мне не понравились потому, что непреодолимых препятствий на карте нет и любой из этих алгоритмов в конечном счёте сведётся к тому же перебору. Завтра попробую написать, если получится, выложу.

Рекурсией попробуешь? Давай, буду ждать. Если на работе опять будет нечего делать, тоже попробую волну.