Минимальный путь в матрицу

[stefan0202]

Помогите , пожалуйста, двухмерная таблица, каждая ячейка, имеeт одну цифру, необходимо найти путь, который формирует минимальную сумму добраться из точки один, один в точке n,n, последней. Только отображать эту суму ...

[Shift_sk]

ты имеешь в виду граф?

[stefan0202]

динамическое программирование

[Shift_sk]

возьми алгоритм флоида!
конечно медлене дейкстры но тебе понятней будет!

[Shift_sk]

for k = 1 to n
  for i = 1 to n
    for j = 1 to n
      W[i,j] = min(W[i,j], W[i,k] + W[k,j])//минимальный из двух!

вот алгоритм флоида! w это твой массив!

[stefan0202]

спасибо , сейчас попробую

[Shift_sk]

ты скажи если помогло...а если нет чтонить другое придумаем!

[Serge_Bliznykov]

1) подобные задачи на форуме неоднократно решались.

2) это классическая задачка на динамическое программирование.
и выбор одного из двух ближайших минимальных значений не решает эту задачку! (почему - подробнее в поиск).
Решается эта задача с помощью дополнительного массива.
Двигаясь от точки (N,N) этот массив заполняется МИНИМАЛЬНОЙ СУММОЙ элементов тех клеточек,
которую можно получить двигаясь от данной клеточки к конечной.
После заполнения данного массива задача сводится к выбору оптимального пути.

[stefan0202]

я ещё изучяю Алгоритм Флоида и как он работает

[stefan0202]

я думаю что кротчяйщий путь не всегда будет совпадать с минимальную сумму б но может быть это я не понел как он работает