Найти минимальный путь между элементами матрицы

[Sanek-MU]

Помогите разобраться с решением задачи
Дана целочисленная матрица MxN (максимальный размер - 8х8). В ней указывают 2 элемента, и между ними нужно найти путь, по которому сумма элементов будет минимальна.
Каким образом получить все пути (понятно, что из каждой клетки можно пойти по 3 путям, потом из каждой ещё по трём и т.п., но я с рекурсией не очень дружу) или как сюда прикрутить алгоритм Дейкстры?

[ololo-schoolboy]

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

[Smitt&Wesson]

Дался Вам этот Дейкстра. Вот нормальный алгоритм:

[Sanek-MU]

ОК, я попозже поразбираюсь ещё с этим, но то, что на кратинке, вроде не совсем подходит к моей задаче... Потому что там из угла в угол, и там путь в целом может быть направлен вверх/влево/по диагонали, а у меня - во все 4 стороны, и тот метод вроде не подходит в таком случае.

[Smitt&Wesson]

Это то, что нужно. Дело в том, что если заданы два элемента внутри матрицы, мы усекаем матрицу до m, n и ищем путь в этом подпространстве.
Этот путь всегда будет лежать внутри этой подматрицы, не верите? Проверьте.

[Sanek-MU]

100  1   1   1 
100  9  100  1 
100 100 100  9 
100 100 100 100

Путь между девятками разве лежит в усечённой матрице?

[Smitt&Wesson]

В этом случае согласен. Алгоритм работает с реальной стоимостью проезда по дорогам. Т.е. с реальными затратами. А в произвольной матрице, сдесь надо с гра'фами работать.
Скорее всего нахождение максимального потока в гра'фе.
Но и в этом случае, матрицу придёться перестраивать. Графы (направленные) имеют вход и выход.
Внутри графа, путь найти невозможно (по крайней мере, я такого не встречал.).

[Sanek-MU]

Ну вот в этом вся и беда, какие-либо частные случаи этой задачи я бы осилил без проблем, но вот такую не получается уже недели две Кроме как получать все возможные пути, не вижу решения, а с этим у меня проблема.

[Utkin]

Алгоритм Дейкстры описан в журнале ПРОграммист, исходники на Дельфи. Но там немного по-другому задается маршрут...