IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Алгоритмы Дискретной математики, Нужна реализация
сообщение
Сообщение #1


Пионер
**

Группа: Пользователи
Сообщений: 86
Пол: Мужской

Репутация: -  0  +


Я может уже повторяюсь, но мне нужна реализация алгоритма Дейкстры на pascal.
Какую-нибудь простенькую задачку (нужно разобраться).
Мне нужна именно реализация алгоритма, а не сам алгоритм (я его хорошо знаю).
Почти все известные алгоритмы уже разобрал, а вот Дейкстры никак не найду, а сам чё-то никак.
Помогите кто чем может unsure.gif smile.gif

P.S На форуме нашел задачу, но там считывается из файла, а файл представляет из себя комбинацию цифр. Ни чё не понял

Сообщение отредактировано: striker -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


просто человек
******

Группа: Пользователи
Сообщений: 3 641
Пол: Женский
Реальное имя: Юлия

Репутация: -  55  +


речь про этот алгоритм?
а в чем проблема с реализацией? вроде как все подробно описано...


--------------------
Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Пионер
**

Группа: Пользователи
Сообщений: 86
Пол: Мужской

Репутация: -  0  +


Вот исходник взял в FAQ:

UNIT Dijkstra;
Interface
Const
NN=30;
Type
graph=array [1..nn,1..nn] of integer;

procedure Deikstr(n:integer; W:graph; u1,u2:integer;
var length:integer; var Weight:real; var Path: array of integer);
Implementation
procedure Deikstr(n:integer; W:graph; u1,u2:integer;
var length:integer; var Weight:real; var Path: array of integer);
var
i,k,j:integer;
GM:real;
d,m:array[1..nn] of real;
p:array[1..nn] of integer;
t:integer;
dd,min:real;
begin
GM:=10000;{бесконечность}
length:=0;
if u1<>u2 then
begin
i:=1;
repeat
d[i]:=GM; p[i]:=0; m[i]:=0; i:=i+1
until not(i<=n);
d[u1]:=0; t:=u1;
while length=0 do
begin
i:=1;
repeat
if w[t,i]<GM then
begin
dd:=d[t]+w[t,i];
if d[i]>dd then begin d[i]:=dd; p[i]:=t end;
end;
i:=i+1
until not(i<=n);
Min:=GM; i:=1; k:=0;
repeat
if m[i]=0 then
begin
if d[i]<min then begin min:=d[i]; k:=i end;
end;
i:=i+1
until not(i<=n);
if k<>0 then begin
m[k]:=1; t:=k;
if t=u2 then begin length:=1; end;
end else begin length:=-1 end;
end;
if length=1 then
begin
Path[1]:=u2; length:=2; j:=u2;
repeat
Path[length]:=P[j]; j:=P[j]; length:=length+1
until not(j<>u1);
i:=1; k:=trunc(length/2);
repeat
t:=Path[i]; Path[i]:=Path[length-i]; Path[length-i]:=t; i:=i+1
until not(i<=k);
length:=length-1
end;
Weight:=d[u2]
end;
end;
end.


uses wincrt,dijkstra;
var
i,u1,u2,n,l:integer;
G:Graph;
w:real;
path:array[0..100] of integer;

procedure ReadFileGraph(var a:graph);
var
i,j:integer; filename:string; f:text;
begin
Write('Enter file name:'); readln(filename);
Assign (f,filename); reset(f);
Readln(f,N);
For i:=1 to n do for j:=1 to n do read(f,a[i,j]); close(f);
end;

begin
readfilegraph(G); {читаем из файла граф.}
write('u1 = '); readln(u1); {вводим первую вершину}
write('u2 = '); readln(u2); {...и конечную..}
Deikstr(n,G,u1,u2, L,w,path);
writeln('w=',w:1:2); {выводим минимальный путь (вес)}
writeln('path'); {выводим путь ....}
for i:=1 to l do write(path[i],' - ');
readkey;
end.



А это содержимое файла, из которого считывается граф.

20
0 3 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000
3 0 10000 10000 10000 3 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000
10000 10000 0 2 10000 5 1 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000
10000 10000 2 0 3 10000 10000 5 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000
10000 10000 10000 3 0 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000
10000 3 5 10000 10000 0 10000 10000 3 10000 10000 4 10000 10000 10000 10000 10000 10000 10000 10000
10000 10000 1 10000 10000 10000 0 10000 2 2 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000
10000 10000 10000 5 10000 10000 10000 0 10000 10000 4 10000 10000 10000 10000 10000 10000 10000 10000 10000
10000 10000 10000 10000 10000 3 2 10000 0 2 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000
10000 10000 10000 10000 10000 10000 2 10000 2 0 3 10000 10000 10000 10000 10000 10000 10000 10000 10000
10000 10000 10000 10000 10000 10000 10000 4 10000 3 0 10000 4 10000 10000 5 10000 10000 10000 10000
10000 10000 10000 10000 10000 4 10000 10000 10000 10000 10000 0 4 10000 10000 10000 10000 10000 10000 10000
10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 4 4 0 4 3 10000 10000 10000 10000 10000
10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 4 0 10000 10000 3 10000 10000 10000
10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 3 10000 0 10000 10000 3 10000 10000
10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 5 10000 10000 10000 10000 0 10000 4 7 10000
10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 3 10000 10000 0 10000 10000 10000
10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 3 4 10000 0 10000 6
10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 7 10000 10000 0 10000
10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 6 10000 0


Разобрался почти во всём.
Вопрос вот в чём:
Как описывается в файле граф? Что это за числа(понимаю, что , но не знаю именно как перечисляются)
И что происходит здесь:
Код
while length=0 do
    begin
      i:=1;
      repeat
        if w[t,i]<GM then
        begin
          dd:=d[t]+w[t,i];
          if d[i]>dd then begin d[i]:=dd; p[i]:=t  end;
        end;
        i:=i+1
      until not(i<=n);
      Min:=GM; i:=1; k:=0;


И здесь:
Код

begin
      Path[1]:=u2;  length:=2; j:=u2;
      repeat
        Path[length]:=P[j]; j:=P[j]; length:=length+1
      until not(j<>u1);
      i:=1;  k:=trunc(length/2);
      repeat
        t:=Path[i]; Path[i]:=Path[length-i]; Path[length-i]:=t; i:=i+1
      until not(i<=k);
      length:=length-1
    end;
    Weight:=d[u2]
  end;

Понятно, что путь ищется, но как?

Вот граф


Сообщение отредактировано: striker -


Эскизы прикрепленных изображений
Прикрепленное изображение
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Гость






Цитата
Понятно, что путь ищется, но как?
А, прости, тебе для чего ссылку на описание алгоритма привели? Чтобы опять теперь "пережевывать" то, что должно быть понятно из теоретического описания? Будь добр прочесть то, что написано в описании алгоритма (и не только на АлгЛибе, AlgoList насколько я помню, тоже содержит описание алгоритма: Алгоритм Дейкстры, да описание есть практически на любом сайте), разобраться, как оно ДОЛЖНО работать, а потом уже задавать вопросы как оно РАБОТАЕТ в какой-то определенной реализации...
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 8:38
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name