Графы., Нахождение кратчайшего пути с наименьшей пошлиной за дорогу Опции

[S!n]

Задача звучит так: В системе двусторонних дорог за проезд каждой дороги взимается некоторая пошлина. Найти путь из города А в город В с минимальной величиной S+P, где S - сумма длин дорог пути, а Р - сумма пошлин проезжающих дорог.

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

Type
        <Запись>=record
                         dlina:integer; {Длина дороги (км)}
                         poshlina:integer; {Пошлина за проезд по одной дороге}
         end;
        <Массив1>=array[dlina,poshlina] of <Запись>;
var
     <Масив2>:array[<Город А>,<Город В>,<Кол-во путей между городами>] of <Массив1>

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

program min_road;
uses wincrt;
const n=7;{кол-во вершин графа}
var
map:array [1..N,1..N] of integer;{Карта: map[i,j] не 0, если точки i и j соединены}
road:array [1..n] of integer;{маршрут-номера точек карты}
incl:array [1..n] of boolean;{incl[i]=true, если точка с номером i включена в road}
len:integer; {Длина последнего найденного маршрута}
c_len:integer;{длина текущего маршрута}
start,finish:integer;{Начальная и конечная точки}
i,j:integer;

procedure step(s,f,p:integer);
var c:integer; {номер точки в которую делаем очередной шаг}
begin
if s=f then
           begin
           len:=c_len; {сохраняем длинну найденного маршрута}
           write('путь: ');
           for i:=1 to p-1 do write(road[i],' ');
           writeln (' Длинна: ',len);
           end
       else
{выбираем очередную точку}
       for c:=1 to n do {проверяем все вершины}
       if (map[s,c]<>0) and (not incl[c]) and ((len=0) or (c_len+map[s,c]<len))
       {точка соединена с текущей и не включена в маршрут}
       then
           begin
           road[p]:=c; {добавим вершину в путь}
           incl[c]:=true;{пометим вершину, как включенную}
           c_len:=c_len+map[s,c];
           step(c,f,p+1);
           incl[c]:=false;
           road[p]:=0;
           c_len:=c_len-map[s,c];
           end;
end;

begin
{инициализация массивов}
for i:=1 to N do road[i]:=0;
for i:=1 to N do incl[i]:=false;
for i:=1 to n do
for j:=1 to n do map [i,j]:=0;
{ввод значений элементов карты}
map [1,2]:=1;map [2,1]:=1;
map [1,3]:=1;map [3,1]:=1;
map [1,4]:=1;map [4,1]:=1;
map [3,4]:=1;map [4,3]:=1;
map [3,7]:=1;map [7,3]:=1;
map [4,6]:=1;map [6,4]:=1;
map [5,6]:=1;map [6,5]:=1;
map [5,7]:=1;map [7,5]:=1;
map [6,7]:=1;map [7,6]:=1;

write ('Введите через пробел номера начальной и конечной точек -> ');
readln (start,finish);
road [1]:=start; {Внесем точку в маршрут}
incl [start]:=true;{пометим ее как включенную}
len:=0;
c_len:=0;
step (start,finish,2); {ищем вторую точку}
writeln ('Для завершения нажмите <Enter>');
readln;
end.

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

М

При публикации программного кода, пожалуйста, используй теги: выделить программу блоком и выбрать нужный пункт из меню CODE над окном ввода Lapp

[Lapp]

Что-то ты переусердствовал...
Зачем тебе это:

Type
        <Запись>=record
                         dlina:integer; {Длина дороги (км)}
                         poshlina:integer; {Пошлина за проезд по одной дороге}
         end;
        <Массив1>=array[dlina,poshlina] of <Запись>;

- ?
Сами по себе координаты элемента массива уже содержат информацию, которую ты собираешься хранить в нем. Какой смысл? Взать, например, элемент [2,3] и присвоить ему запись, в которой двойка и тройка?..

Похоже, что в твоем трехмерном массиве имеет смысл просто хранить эти самые записи. Но с ним тоже не вполне ясно. Как ты будешь эту инфу рассчитывать? И она неоднозначная..

Ты приведи сам алгоритм, которым ты собираешься пользоваться. Тот самый, теретический, который ты понимаешь. Это и есть больше половины задачи. А массивы - какая разница, скольки они мерные..

[S!n]

Хм... алгоритм... Алгоритм назвать не могу, так как впервые имею дело с графами.
Могу по пунктам расписать, что мне нужно сделать:
1) Создание файла в который будет заноситься информация о количестве дорог между городами, расстояние и пошлина за каждую дорогу.
2) Ввод данных
3) Сохранение данных в файл
4) Сравнение каждого из элементов файла и нахождение самого короткого пути с самой маленькой пошлиной.
5) Вывод на экран сообщения о найденном пути
6) Возможность изменения элементов файла, добавление новых дорог.

Сами по себе координаты элемента массива уже содержат информацию, которую ты собираешься хранить в нем. Какой смысл? Взать, например, элемент [2,3] и присвоить ему запись, в которой двойка и тройка?.. blink.gif

Видишь-ли, в чем дело. Последний элемент моего трехмерного массива:

<Масив2>:array[<Город А>,<Город В>,<КОЛ-ВО ПУТЕЙ МЕЖДУ ГОРОДАМИ>] of <Массив1>

Должен содержать инфу о длине дороги и стоимости. Я просто не знаю, каким образом мне это реализовать.

[Lapp]

2) Ввод данных

Вот эти два слова - это и есть та самая теория, которую, как я теперь вижу, ты, несмотря на твои слова, не представляешь. Создание, запись файлов - это пара операторов, да и не нужно это.. А вот КАК ты будешь сканить возможные пути - это как раз важно. У тебя об этом ни слова..
Советую тебе поискать по Форуму. Задачи подобного рода делались неоднократно. А лучше, если честно, возьми учебник по графам.. Будешь _действительно_ представлять себе теорию - программа приложится..

Видишь-ли, в чем дело. Последний элемент моего ...

Я вижу в чем дело: на вопрос отвечать не считаешь нужным.

Я просто не знаю, каким образом мне это реализовать.

Ты не только не знаешь КАК реализовать. Ты также не знаешь, ЧТО - и это важнее.

Читай теорию по графам.

[S!n]

Хорошо. Спасибо. Если возникнут вопросы, напишу ещё.

[S!n]

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

uses wincrt;
const n=10;
type
    rec=record
         dlina:integer;
         poshlina:integer;
    end;
var
   map:array[1..n,1..n,1..n] of rec;
   road,i,city1,city2:integer;
   roadfile:file of ?; 

begin
     assign(roadfile,'road.txt'); {Связывание файлововой переменной с самим файлом}
     reset(roadfile); {Т.к. файл скорее всего будет типизированным то процедурой reset открываю его для чтения и записи}
     write('Введите начальный и конечный города -> ');
     readln(city1,city2); {Эти переменные пока не используются}
     write('Введите количество дорог -> ');
     readln(road);
     for i:=1 to road do {Цикл, в ходе которого всем заданным дорогам присваивается длина и пошлина}
     begin
          with map[city1,city2,i] do {Открываю доступ к полям записи для их редактирования}
          begin
               write('Введите длину ',i,' дороги -> ');
               readln(dlina);
               Write('Введите пошлину ',i,' дороги -> ');
               readln(poshlina);
          end;
          write(roadfile,map); {Здесь туплю. Можно ли таким образом занести весь массив целиком в файл? 
И если да, то какого типа должен быть файл? Перепробовал уже всё, что знаю, но ничего не выходит.}
     end;
close(roadfile);
end.

Сообщение отредактировано: S!n - 3.12.2008 17:47

[S!n]

Изменил свою прогу таким образом (Изменение в разделе type и var):

uses wincrt;
const n=10;
type
    rec=record
         dlina:integer;
         poshlina:integer;
    end;
type_map=array[1..n,1..n,1..n] of rec;
var
   map:type_map;
   road,i,city1,city2:integer;
   roadfile:file of type_map;

begin
     assign(roadfile,'road.txt'); {Связывание файлововой переменной с самим файлом}
     reset(roadfile); {Файл типизированный, значит процедурой reset открываю его для чтения и записи}
     write('Введите начальный и конечный города -> ');
     readln(city1,city2); {Эти переменные пока не используются}
     write('Введите количество дорог -> ');
     readln(road);
     for i:=1 to road do {Цикл, в ходе которого всем заданным дорогам присваивается длина и пошлина}
     begin
          with map[city1,city2,i] do {Открываю доступ к полям записи для их редактирования}
          begin
               write('Введите длину ',i,' дороги -> ');
               readln(dlina);
               Write('Введите пошлину ',i,' дороги -> ');
               readln(poshlina);
          end;
          write(roadfile,map); {Ошибка здесь}
     end;
close(roadfile);
end.

Я не могу понять, как правильно занести инфу в файл. Если целиком массив не получится туда поместить, то тогда только по одному элементу массива? И ещё, туда ли я ставлю процедуру записи в файл?

Сообщение отредактировано: S!n - 5.12.2008 7:41