Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[3.91.106.157] |
|
Сообщ.
#1
,
|
|
|
Делал классическую задачку на Алгоритм Дейкстры:
Реализовал не оптимизированую стандартную Дейстру O(N^2) точно по приведеному описанию алгоритма: Проверял задачу на большом количестве различных тестов. Всё чудесно работает, Но при проверке задачи получаю Неправильный ответ. Не могу понять в чем я ошибаюсь. var found:boolean; i,j,n,k,point,min_i,temp,old_temp,sum,finish:integer; min:int64; used:array[1..100]of boolean; best_ways,indexes:array[1..100]of longint; w:array[1..100,1..100]of longint; begin assign(input,'input.txt'); reset(input); readln(n,point,finish); for i:=1 to n do begin for j:=1 to n do begin read(w[i,j]); if(w[i,j]=-1) then w[i,j] := 100000; end; readln; end; close(input); used[point] := true; for i:=1 to n do begin indexes[i] := point; best_ways[i] := w[point,i]; end; indexes[point] := 0; found := true; while found do begin min := high(min); found := false; for i:=1 to n do if(not used[i]) and (best_ways[i]<min) then begin found := true; min := best_ways[i]; min_i := i; end; if not found then break; used[min_i] := true; for i:=1 to n do if(best_ways[min_i]+w[min_i,i]<best_ways[i]) then begin best_ways[i] := best_ways[min_i]+w[min_i,i]; indexes[i] := min_i; end; end; assign(output,'OUTPUT.TXT'); rewrite(output); writeln(best_ways[finish]); close(output); end. Ах да: не надо сюда, пожалуйста, отписывать алгоритмом Дейсткстры скачаным из интернет, так как такой у меня имееться, но увы не удаеться понять то, что сам не писал. |
Сообщ.
#2
,
|
|
|
Вот моя программа на паскале, работающая)
Орграф представлен списками инцидентности. Pred[v] - указатель на список вершин, предыдущих для v, Sled[v] - следующих Ввод с клавиатуры. Вначале через пробел колво вершин и колво дуг. Затем через пробел начало - конец дуги. затем её вес. program deikstra; CONST nmax=100; inf=1000; TYPE PT=^ZT;{указатель на запись} ZT=RECORD uzl:integer;{вершина } next:PT {указатель на следующую запись} END; VAR n,m:integer; {колво вершин и дуг} PRED,SLED:array[1..nmax] of PT; {списки инцидентности} A:array[1..nmax,1..nmax] of real; {матрица весов} D:array[1..nmax] of real; {вектор расстояний от источника до всех вершин} s,t:integer; {источник, сток} v,u,k: integer; TT: array[1..nmax] of boolean; {массив рабочих вершин} min:real; PROCEDURE PUSH(var p:PT; k:integer); { вталкивание в стек } VAR p1:PT; begin { push } NEW(p1); p1^.uzl:=k; p1^.next:=p; p:=p1; end; {push} FUNCTION POP(var p:PT):integer; { выталкивание из стека } var p1:PT; begin { pop } pop:=p^.UZL; p1:=p; p:=p^.next; dispose(p1); end; { pop } PROCEDURE ORSPISKI; {формирование списков инцидентности и матрицы весов} VAR i,j,u,v:integer; begin write('n, m? '); readln(n,m); for i:=1 to n do begin PRED[i]:=NIL; SLED[i]:=NIL; end; for i:=1 to n do for j:=1 to n do A[i,j]:=inf; for i:=1 to m do begin write('u,v? '); readln(u,v); push(PRED[v],u); push(SLED[u],v); write('A[u,v]? '); readln(A[u,v]); end; end; {orspiski} PROCEDURE PRINT(s,t:integer); {печать пути от s до t } var p,stec:PT; u,v:integer; begin stec:=nil; push(stec,t); v:=t; while v<>s do begin p:=PRED[v]; u:=p^.uzl; while (D[v]<>D[u]+A[u,v]) do begin p:=p^.next; u:=p^.uzl; end; push(stec,u); v:=u; end; while stec<>nil do write('<',pop(stec),'>'); end; {print} begin {main} orspiski; write('s= '); readln(s); write('t= '); readln(t); for v:=1 to n do begin D[v]:=A[s,v]; TT[v]:=true; end; D[s]:=0; TT[s]:=false; for k:=1 to n-1 do begin min:=inf; u:=0; for v:=1 to n do if TT[v] then if min>D[v] then begin min:=D[v]; u:=v end; TT[u]:=false; for v:=1 to n do if TT[v] then if D[v]>D[u]+A[u,v] then D[v]:=D[u]+A[u,v] ; end; for v:=1 to n do write(D[v]:5:2,' '); writeln; print(s,t); writeln; readln; end. Добавлено Описание алгоритма находится в ФАКе раздела, в файле Лекции по структурам данных |
Сообщ.
#3
,
|
|
|
Спасибо, но уже нашол у себя ошибку. И еще:
1. Слишал что дейкстра может работать и с отрицательными весами ребр, если нет цыклов отрицательного веса. Так ли ето? 2. Помогите найти описание оптимизированой Дейкстры O(M log N) желательно с примером для паскаля. |
Сообщ.
#4
,
|
|
|
Цитата 1. Слишал что дейкстра может работать и с отрицательными весами ребр, если нет цыклов отрицательного веса. Так ли ето? НЕТ, только с неотрицательными. Если в орграфе есть отрицательные веса, но нет контуров отрицательного веса, то это алгоритм Форда-Беллмана. Если для такого графа нужна матрица расстояний (расстояния между любой парой вершин), то это алгоритм Флойда. |