Народ хелп по сабжу. Есть у кого исходники программы по сей задаче? Уже с месяц с ней дерусь.

На бумажке устно решить могу, а вот как запрограммировать...

С рекурсиями с детства не дружу ей богу =(

Или давайте объясню в чём сложность - может подсобить в написании...

Всё ещё актуально  

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

Кстати, рекурсия здесь не обязательна.


Решения динамическим программированием удобно описывать, как заполнение некой таблицы: таблица, в которой есть N строк (от 1 до N) и 2^N столбцов (от 0 до 2^N-1). Каждая клетка таблицы - обозначает некий ответ, если мы посетили некоторый набор вершин, и сейчас стоим в некоторой вершине.

А именно, клетка таблицы с координатами (i,j) содержит кратчайший путь, который заканчивается в вершине i. Число j обозначает, какие вершины этот путь посетил. Обычно это делается таким образом: число j рассматривается в двоичной системе счисления, и k-ый его бит обозначает, проходил путь через вершину k или нет.

Например, клетка таблицы в строке 3 и столбце 13 обозначает путь, проходивший через вершины 1,3,4 (потому что у числа 13 включены первый, третий и четвёртый биты) и заканчивающийся в вершине 3.


Изначально вся таблица заполнена плюс бесконечностью (бесконечность обозначает "нет пути, или мы пока его не нашли"). Только в ячейку (1,0) таблицы мы записываем 0 - это обозначает, что путь, состоящий только из стартовой вершины 1, имеет длину 0.

Теперь начинается сам алгоритм. Мы идём по таблице слева направо, сверху вниз. Пусть текущая ячейка таблицы - это ячейка (i,j). Это обозначает, что в этой ячейке записан кратчайший путь до вершины i, при условии, что он проходит через заданные вершины. Тогда мы можем попробовать добавить к этому пути ещё одну вершину.

Здесь проще описать алгоритмически: стоя на ячейке (i,j), мы перебираем число k=1..N (обязательно такое, что в числе j бит под номером k нулевой), и пытаемся улучшить значение в ячейке (k, j + 2^k): для этого мы к ячейке (i,j) прибавляем длину ребра (i,k) и, если получившееся число оказалось меньше ячейки (k, j + 2^k), - записываем туда это число.

В конце концов, после того, как мы сделаем так все возможные улучшения, у нас получится заполненная таблица. Ответом на задачу будет минимум среди таких чисел: ячейка (i,2^N-1) плюс длина ребра из вершины i в вершину 1.