задача коммивояжера

[ritmix93]

Имеется N населённых пунктов, пронумерованных от 1 до N. Некоторые пары населенных пунктов соединены дорогами. Известны стоимости проездов по этим дорогам. Определить, можно ли попасть по этим дорогам из первого пункта в N-ный. Если да, то найти маршрут с минимальной стоимостью проезда.

program proezd;

const
Max = 5;

var
A: Array[1..Max, 1..Max] Of Integer;
{ *Матрица расстояний между городами. *}
f: text;
N: integer;
B: Array[1..Max, 1..Max] Of Byte;{^Вспомогательный
массив, элементы каждой строки матрицы
сортируются в порядке возрастания, но сами
элементы не переставляются, а изменяются
в матрице В номера столбцов матрицы А.*}
Way, BestWay: Array[1..Max] Of Byte;{*Хранится
текущее решение и лучшее решение. *}
Nnew: Array[1..Max] Of Boolean;{*3начение
элемента массива False говорит о том,
что в соответствующем городе коммивояжер
уже побывал. *}
BestCost: Integer;{*Стоимость лучшего решения. *}


procedure Solve(v, Count: Byte; Cost: Integer);
{*v - номер текущего города; Count - счетчик числа
пройденных городов; Cost - стоимость текущего
решения. *}
var
i: Integer;
begin
if Cost > BestCost Then Exit;{*Стоимость текущего
решения превышает стоимость лучшего из
ранее полученных. *}
if Count = N Then begin
Cost := Cost + A[v, 1];
Way[N] := v;{*Последний город
пути. Добавляем к решению стоимость
перемещения в первый город и сравниваем
его с лучшим из ранее полученных. *}
if Cost < BestCost Then begin
BestCost := Cost;
BestWay := Way; end;
Exit;{*Оператор нарушает структурный стиль
программирования ~ "любой фрагмент логики
должен иметь одну точку входа и одну точку
выхода. Следует убрать его" . *}
end;

Nnew[v] := False;
Way[Count] := v;{*Город с номером v
пройден, записываем его номер в путь
коммивояжера. *}
for i := 1 To N do
if Nnew[B[v, i]] Then Solve(B[v, i],
Count + 1, Cost + A[v, B[v, i]]); {*Поиск города, в который
коммивояжер может пойти из города,
с номером v.*}
Nnew[v] := True; {^Возвращаем город с номером v
в число непройденных. *}
end;

var
i, j: integer;

begin
assign(f, 'f:\1.txt');
reset(f);
i := 1;
j := 1;
while not eof(f) do
begin
while not eoln(f) do
begin
read(f, a[i, j]);
inc(j);
end;
readln(f);
inc(i);
end;
solve();
writeln('лучшая цена-', BestCost);
end.

Просьба исправить и доработать



___________
Код нужно оформлять по правилам:
тегом [CODE]..[/СODE]
(кнопочка на панели форматирования с решёточкой #)
Не забывайте об этом!

Модератор.

[s-andriano]

Для начала: та задачу, что Вы описали, к задаче коммивояжера не имеет ни малейшего отношения. Описана задача нахождения кратчайшего пути в графе.
Вы уж определитесь, что именно Вам нужно.
Задача коммивояжера решается перебором, а задача нахождения кратчайшего пути - алгоритмом Дейкстры.