Задача с олимпиады

[Xardas]

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

Сама задача длинная (там про зараженную местность, уровень радиации и т.д.), я ее немного перефразирую: Допустим есть массив N на M, необходимо найти путь из точки [1,1] в [N,M] чтобы сумма элементов была минимальной. (немного, конечно, неудачно выразился)

Например: 1 100 0 50 100
1 100 0 0 0
2 0 0 3 1
0 0 100 2 1

Массив 4 на 5 - минимальная сумма 6
Путь: 1 -> 1 -> 2 -> 0 -> 0 -> 0 -> 0 -> 0 -> 1

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

Я думаю смысл понятен. Я пытался рекурсивно перебрать все возможные варианты, только как то не получилось.

Обращаюсь к вам товарищи программисты, помогите, пожалуйста, решить вот такую вот задачку.

PS: Delphi or Pascal

[Kriziun]

Это так называемая задача комивояжора. Существует несколько алгоритмов, например: Алгоритм Дэйкстры (частный случай)

Поищи в нете, например http://ru.wikipedia.org/wiki/Алгоритм_Дейкстры

[SNUPY]

Чуть-чуть не правильно: это не задача коммивояжера, т.к. в коммивояжор должен по всем пробежаться. Это задача если не изменяет память на поиск картчайшего пути

[Kriziun]

Сообщение от SNUPY

Чуть-чуть не правильно: это не задача коммивояжера, т.к. в коммивояжор должен по всем пробежаться. Это задача если не изменяет память на поиск картчайшего пути

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

[Xardas]

Просьба не постить сюда!!!

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

Еще раз прошу прощения!!!