z0DiuS
Newbie | Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
Всем привет  Я вообще первый раз на этом портале, правила почитал, вроде даже понял %)
Итак, у меня задача по Алгоритму Дейкстры на Delphi. А точнее - четыре штуки, но они в принципе похожи 
1.
Дан ориентированный взвешенный граф. Найти кратчайшее расстояние между заданными вершинами.
На входе - три числа: N, S, F, где N - количество вершин графа, S - начальная вершина, а F - конечная.
Затем в N строках по N чисел дана матрица смежности графа, где "-1" - отсутствие ребра между вершинами, а любое неотрицательное число - присутствие ребра данного веса. На главной диагонали - нули
Вывести нужно расстояние между вершинами, либо "-1", если пути не существует.
1<N=<2000; S - больше 1, а F=<N
2.
Дан неориентированный взвешенный граф. Найти вес минимального пути между вершинами.
На вход даны:
В первой строке: количество вершин(N) и ребер графа(число M), а также номера вершин, между которыми мы ищем вес пути(S - Start, F - Finish).
Далее идут M строк по три числа в каждой - номера концов n-ного ребра и его вес соответственно.
Должно выводиться:
В первой строке - вес минимального пути, а во второй - вершины на этом пути в порядке обхода
А если пути нет - вывести "-1".
M<100000, N<5000, 1<S,
Первую я решил, но она не укладывается в рамки времени, поэтому мне нужна помощь с оптимизацией. Вторая решена на основе первой, но у меня вершины, по которым мы проходим, выводятся в обратном порядке.
Первая:
Код:
Program Alg_dejkstr;
uses
SysUtils;
Const MaxSize=2000;
Infinity=10000;
Var D: array [1..MaxSize, 1..MaxSize] of integer;
A: array [1..MaxSize] of boolean;
B,C: array [1..MaxSize] of integer;
Start, Finish, n, k, i, temp: integer;
Procedure Init;
Var f: text;
i, j: integer;
Begin
Reset(Input, 'dijkstra.in');
Rewrite(Output, 'dijkstra.out');
read(n, start,finish);
For i:=1 to n do
For j:=1 to n do
begin
Read(temp);
if temp=-1 then D[i,j]:=Infinity else D[i,j]:=temp;
end;
{For i:=1 to n do
begin
For j:=1 to n do
write(D[i,j]);
writeln;
end;}
For i:=1 to n do
Begin
A[i]:=False;
B[i]:=D[Start,i];
//C[i]:=Start;
End;
//C[Start]:=0;
A[Start]:=True;
End;
Function Possible: Boolean;
Var i: integer;
Begin
Possible:=True;
For i:=1 to n do If not A[i] then Exit;
Possible:=False;
End;
Function Min: Integer;
Var i, minvalue, currentmin: integer;
Begin
Minvalue:=Infinity;
For i:=1 to n do
If not A[i] then
If B[i]<minvalue then
Begin
currentmin:=i;
minvalue:=B[i]
End;
min:=currentmin;
End;
Begin
Init;
While Possible do
Begin
k:=min;
A[k]:=True;
For i:=1 to n do
If B[i]>B[k]+D[k,i] then
Begin
B[i]:=B[k]+D[k,i];
// C[i]:=k;
End;
End;
write(B[Finish]);
// Write(Finish);
// Finish:=C[Finish];
// While Finish<>0 do
// Begin
// Write(Finish);
// Finish:=C[Finish];
// End;
CloseFile(Output);
End.
|
Вторая:
Код:
Program Alg_dejkstr;
uses
SysUtils;
Const MaxSize=2000;
Infinity=10000;
Var D: array [1..MaxSize, 1..MaxSize] of integer;
A: array [1..MaxSize] of boolean;
B,C: array [1..MaxSize] of integer;
Start, Finish, n, k, i, temp: integer;
Procedure Init;
Var f: text;
i, j: integer;
Begin
Reset(Input, 'dijkstra.in');
Rewrite(Output, 'dijkstra.out');
read(n, start,finish);
For i:=1 to n do
For j:=1 to n do
begin
Read(temp);
if temp=-1 then D[i,j]:=Infinity else D[i,j]:=temp;
end;
{For i:=1 to n do
begin
For j:=1 to n do
write(D[i,j]);
writeln;
end;}
For i:=1 to n do
Begin
A[i]:=False;
B[i]:=D[Start,i];
//C[i]:=Start;
End;
//C[Start]:=0;
A[Start]:=True;
End;
Function Possible: Boolean;
Var i: integer;
Begin
Possible:=True;
For i:=1 to n do If not A[i] then Exit;
Possible:=False;
End;
Function Min: Integer;
Var i, minvalue, currentmin: integer;
Begin
Minvalue:=Infinity;
For i:=1 to n do
If not A[i] then
If B[i]<minvalue then
Begin
currentmin:=i;
minvalue:=B[i]
End;
min:=currentmin;
End;
Begin
Init;
While Possible do
Begin
k:=min;
A[k]:=True;
For i:=1 to n do
If B[i]>B[k]+D[k,i] then
Begin
B[i]:=B[k]+D[k,i];
// C[i]:=k;
End;
End;
write(B[Finish]);
Write(Finish);
Finish:=C[Finish];
While Finish<>0 do
Begin
Write(Finish);
Finish:=C[Finish];
End;
CloseFile(Output);
End.
|
Вот как-то так. Буду благодарен за любую помощь
Добавлено:
Остальные две пока сам попробую порешать |
?...
