GRY-Online.pl --> Archiwum Forum

Dijkstra

14.01.2003
13:49
[1]

ghost666 [ 666st Ghost of Doom ]

Dijkstra

jak w tytule!!! po tzrebuje algorytm Dijkstry jak ktos ma to pisac i wysyłac pozniej, to nie tylko ode mnie :D

14.01.2003
14:05
smile
[2]

.kNOT [ Progresor ]

Bardzo proszę...

14.01.2003
14:30
smile
[3]

MateyToB [ Aleksander Newski ]

A w jakiejś zjadliwszej formie w Turbo Pascalu ??

14.01.2003
14:37
smile
[4]

.kNOT [ Progresor ]

Bardzo proszę...

14.01.2003
14:44
smile
[5]

MateyToB [ Aleksander Newski ]

.kNOT : nie wiem czy wiesz, ale na taki pomysł jesteśmy z ghostem sami wpaść... jak ktoś ma problem nietrudno mu do goolga dać linka z tekstem www.google.com/search<tytułwątku bleble>. Jeśli jesteś taki świetny z tymi linkami, to podaj do konkretnej strony zawierającej algorytm Dijkstry w Pascalu, strukturalny, bez zmiennych globalnych. Wtedy będę mógł powiedzieć, że Twoja pomoc była cokolwiek warta. Albowiem ze stron wyszukanych przez google za dużo zassać nie można.

14.01.2003
14:45
[6]

MateyToB [ Aleksander Newski ]

miało być: jesteśmy w stanie z ghostem sami wpaść

14.01.2003
14:59
smile
[7]

.kNOT [ Progresor ]

(* INPUT : The associated datafile for Dijkstra's algorithm is called

"datafile".

The FIRST NUMBER in "datafile" is the # of nodes in a network.

The representation of a network for this algorithm is the

WEIGHT MATRIX. The WEIGHT MATRIX of an n-node network is an

n X n matrix W=[wij] in which the (i,j)th entry wij is the

weight of (i,j), the edge from node i to node j.

ALGORITHM : The Dijkstra algorithm computes the shortest distance from

a given SOURCE (S) node which is denoted by node 1 to

another destinatin node (T) which is denoted by the Nth node

in an N-nonde network.

Maximum # of nodes in a netwrok is set to be max=50.

If N > 50. One can change the setting of max to an even

larger number that is > N.

Similarly, infinity(no edge between two given nodes) INF is

set to be 200.

This algorithm only takes non-negative weight edges


OUTPUT : Given "datafile", The Dijkstra outputs

1. LABEL = TRUE if each node is permanently labeled.

2. Shortest distance from node S to node T

3. Traced the nodes which shortest path take on from

S to T. This is given in array PRED[1..N].

Time : The running time of this algorithm is O(N^2)

NOTE : If the network is small and dense, this Dijkstra algorithm

is faster and preferred.

If the network is large and sparse, and if shortest path

from source node S to all other nodes is needed,

Then PDM algorithm is preferred. *)







(*************************************************************************)

program dijk (input, output, datafile, DijkstraOutfile);

const max = 50;

INF = 200;

type CHARFILE = file of char;

ARRNN = array[1..max,1..max] of integer;

ARRN = array[1..max] of integer;

BOOLARRN = array[1..max] of boolean;

var datafile : CHARFILE;

DijkstraOutfile : CHARFILE;

N, Nextint : integer;

S, T : integer;

W : ARRNN;

PATH : boolean;

FINAL : BOOLARRN;

DIST,PRED:ARRN;





procedure Infile(var W : ARRNN;

var N : integer;

var Nextint : integer);

var row, column : integer;

begin

reset(datafile);

readln (datafile, Nextint);

N := Nextint;

for row := 1 to N do

begin

for column := 1 to N do

begin

read(datafile, Nextint);

W[row,column] := Nextint;

end;

readln(datafile);

end;

end;



procedure DIJKSTRA(

N,INF,S,T:integer;

var W :ARRNN;

var PATH :boolean;

var FINAL :BOOLARRN;

var DIST,PRED:ARRN);

var U,V,Y,RECENT,NEWLABEL,TEMP:integer;

begin

for V:=1 to N do begin

DIST[V]:=INF; FINAL[V]:=false; PRED[V]:=-1

end; (* INF = WEIGHT OF A NONEXISTENT EDGE *)

DIST[S]:=0; FINAL[S]:=true;

PATH:=true; RECENT:=S; (* INITIALIZATION OVER *)

while not FINAL[T] do begin

for V:=1 to N do (* FIND NEW LABEL *)

if (W[RECENT,V] < INF) and (not FINAL[V]) then begin

NEWLABEL:=DIST[RECENT]+W[RECENT,V];

if NEWLABEL < DIST[V] then begin

DIST[V]:=NEWLABEL; PRED[V]:=RECENT

end

end;

TEMP:=INF;

for U:=1 to N do (* FIND SMALLEST LABELED VERTEX *)

if (not FINAL) and (DIST < TEMP) then begin

Y:=U; TEMP:=DIST

end;

if TEMP < INF then begin (* THERE IS A PATH *)

FINAL[Y]:=true; RECENT:=Y

end

else begin (* THERE IS NO PATH FROM S TO T *)

PATH:=false; FINAL[T]:=true

end

end (* WHILE NOT FINAL[T] *)

end; (* DIJKSTRA *)



procedure Outfile(

N : integer;

FINAL : BOOLARRN;

DIST : ARRN;

PRED : ARRN);

var counter : integer;

begin

rewrite(DijkstraOutfile);

writeln(DijkstraOutfile,' Node Distance Label Predecessor');

for counter := 1 to N do

begin

write (DijkstraOutfile,counter);

write (DijkstraOutfile,DIST[counter]);

write (DijkstraOutfile,' ',FINAL[counter]);

writeln(DijkstraOutfile,PRED[counter]);

end;

writeln(DijkstraOutfile);

end;

begin (* main *)

S := 1;

T := N;

Infile(W,N,Nextint);

DIJKSTRA(N,INF,S,T,W,PATH,FINAL,DIST,PRED);

Outfile(N,FINAL,DIST,PRED);

end.

14.01.2003
16:27
[8]

ghost666 [ 666st Ghost of Doom ]

argh... po jakiego cepa na plikach? dlaczego bez procedur?

Napisz jeszcze raz, i jeszcze lepiej wyslij mi na maila : [email protected]

14.01.2003
16:30
[9]

Szaman [ Legend ]

ghost666: Czy moglbys przestac narzekac? Zamiast samemu ruszyc tylek i poszukac, to zaprzegasz do tego forumowiczow i jeszcze prostego "Dziekuje" nie potrafisz z siebie wydobyc?
Naprawde tak trudno napisac jedno proste slowo?

14.01.2003
16:33
smile
[10]

.kNOT [ Progresor ]

> po jakiego cepa na plikach?
Bardzo lubię pliki, szczególnie te niewielkie...

> dlaczego bez procedur?
procedure Infile
procedure DIJKSTRA
procedure Outfile
Trzy procedury to dla Ciebie za mało???

>Napisz jeszcze raz
Bardzo proszę...

14.01.2003
16:45
[11]

ghost666 [ 666st Ghost of Doom ]

Szaman ---> nie dziękuje bo nie mam za co...
kNOT ---> czy to wazne co lubisz ? :P jak by zawsze było wazne to co lubimy to bym nie pisał tego fuckin' programu ale mniejsza z tym, tyle co zrobiłęs to kazdy głupi potrafi...

Wiec apeluje jeszcze raz do wszystkich informatyków znających sie na rzeczy o algorytm dijkstry bez zmiennych globalnych, z procedurami, wraz z modułem podawania i wypisywania danych (a nie na plikach)

z góry dziękuje

14.01.2003
16:55
smile
[12]

.kNOT [ Progresor ]

ghost666 -> No właśnie! A Ty nie potrafisz...

14.01.2003
17:01
[13]

ghost666 [ 666st Ghost of Doom ]

droki knocie, nie zrobiłem tego? skad wiesz ze nie? siedzisz tutaj obok mnie? chyba nie wiec nie mow mi co robiełm a co nie, a poza tym nie pytałbym was o takie głupoty jakbym znalazł to w necie...

14.01.2003
17:28
[14]

ghost666 [ 666st Ghost of Doom ]

up

14.01.2003
18:04
smile
[15]

ciemek [ Senator ]

ty wiesz co, chcialem Ci pomoc, ale skoro masz mnie tak czy siak zjechac, to po kiego grzyba się męczyć...
PS: Tak, wiem ze gówno Cię to interesuje co ja o tym myślę.

.kNOT - daj kolesiowi spokój, niech sam kombinuje ;)

14.01.2003
18:28
[16]

ghost666 [ 666st Ghost of Doom ]

ciemek ---> jak byś zrobił coś godnego zjechania to Cie zjade :P masz racje, ale jeśli mi pomożesz to czemu miałbym cie zjeżdzać ? szukam kogoś kto sie na tym zna, a nie kogos kto ma w pełni opanowane szukanie w necie i ctrl+c ctrl+v tyle potrafie sam i jak juz pisałem, jak bym znalazl to czego szukam to bym nie marudził
jak nie chcesz pomagac to nie łaski bez, znajde kogos innego, kto bedzie sie chciał podzielic swa wiedza i umiejetnosciami :D

14.01.2003
18:39
smile
[17]

boYek [ Konsul ]

Eeee, programowanie, a ja myslalem ze tu cos o Sapkowskim i wiedzminach bedzie. ;)

14.01.2003
18:47
smile
[18]

.kNOT [ Progresor ]

I jak tu Ci dogodzić?
Swój brak wiedzy próbujesz ukryć za brakiem ogłady...
Ale ja jakoś lubię takich młodych gniewnych ;-)
Bez Was świat byłby straszliwie nudny ;-)))
Polecam książkę
Maciej M. Syslo, Narsingh Deo, Janusz S. Kowalik 'Discrete Optimization Algorithms with Pascal Programs'
albo po naszemu
Maciej M. Sysło, Narsingh Deo, Janusz S. Kowalik 'Algorytmy optymalizacji dyskretnej z programami w języku Pascal'
Znajdziesz w niej (wydanie PWN 1993) na stronie 187 opis algorytmu a na stronie 447 gotowy program w aż 35 liniach.
Może, gdy liźniesz trochę wiedzy, nabędziesz i kultury...
Czego Ci z całego serca życzę ;-)))

14.01.2003
19:14
[19]

ghost666 [ 666st Ghost of Doom ]

dziekuje za pomoc, postaram sie w najblizszym czasie dotrzec do tych xiazek :D

14.01.2003
19:19
smile
[20]

.kNOT [ Progresor ]

Powodzenia!

14.01.2003
21:35
smile
[21]

.kNOT [ Progresor ]

Dla wszystkich, którym nazwisko Dijkstra kojarzy się nie z tym, z czym powinno...

Edsger Wybe Dijkstra is one of the computer pioneers and has developed the framework for proper programming.
(...)
In these years between 1952 and 1956, programming saw an evolution, partly because the ever growing complexity of the systems ordered a more structured operating system, and partly because the scientific, mathematical approach of programming produced an ever clearer insight in how the job could be done efficiently. Remarkable in this process was Dijkstra’s discovery of the Shortest Path Algorithm.
(...)
Edsger Wybe Dijkstra died of cancer on August 6 2002 in Nuenen, The Netherlands.

14.01.2003
21:41
[22]

Lewy Krawiec(łoś) [ I can change ]

Dijkstra? ten koleś z sagi Sapcia Chmiela o wieśmnie?

14.01.2003
21:45
smile
[23]

.kNOT [ Progresor ]

<- Lewy Krawiec(łoś)

14.01.2003
21:55
[24]

maczu [ Konsul ]

siema :)
ciemek, chcialem powiedziec cos takiego co ty, ale po doczytaniu do konca powiem tak:
.knot - podziwiam cie. ja bym nie mial tyle cieprliwosci... :) moje gratulaacjie :)
lewy łoś >> UAHAHAHAHAHAHA:)))))) WIEDZMIN, HUEHUEHUE, DOBRE... :))))))))

© 2000-2021 GRY-OnLine S.A.