Deikstros algoritmas

IF 7/12 Paulius Grigaitis 1. Užduotis : Realizuoti “Deikstros” algoritmą ir sudaryti programą trumpiausio kelio nuo “P” (pradžia) iki “G” (galas) radimui. 2. Užduoties analizė: Pradiniai duomenys turi būti surašyti tekstiniame faile. Failo eilutės formatas: briauna pradžia,briaunos pabaiga, briaunos svoris Duotame grafe reikia rasti trumpiausi kelią nuo įvestos iš klaviatūros pradines ir galinės viršūnės.Naudojant Deikstros algoritmą.Atsakymas išvedamas į ekraną. Tarkim ,kad žinom trumpiausią kelią tarp s ir k (Fk)ų Tada Fj skaičiuojamas Fj=min(Fj, Fk+Ckj). Fs=0. Fj= . Fk=min(Fj) kur j nedažytos. 3. Pradinių duomenų ir rezultatų pavyzdžiai: Pradiniai duomenys: Gr1.dat 1 2 10 1 7 2 1 8 6 2 1 10 2 3 10 2 5 4 2 7 4 3 2 10 3 4 3 4 3 3 4 5 2 4 6 1 5 2 4 5 4 2 5 6 6 5 7 8 5 8 14 6 4 1 6 5 6 6 8 8 7 1 2 7 2 4 7 5 8 8 1 6 8 5 8 8 6 8 “P” – 1. “G” – 6. Rezultatai: 64571 4. Duomenų struktūros aprašymas: Funkcijos ir Procedūros. 4.1 Procedūra Data (var l, lst, d : mas; var n : integer; f : string); Nuskaito duomenis is failo. Failo eilutės formatas: briauna pradžia,briaunos pabaiga, briaunos svoris parametrai: l, lst - l ir lst masyvai, d - briaunos svorių masyvas. f - duomenų failo vardas P.S. jei failas neegzistuoja programa baigia darbą. procedure Data(var l, lst, d : mas; var n : integer; f : string); var i, a, b, c : integer; t : text; begin Write(' failas '); HighVideo; WriteLn(f); LowVideo;n := 0; {$I-} Assign(t, f); Reset(t); {$I+} if IOResult 0 then begin WriteLn('neatidarau failo'); halt end; i:=0; while not Eof(t) do begin ReadLn(t, a, b, c); { nuskaitome briauna ir jos svori } Inc (i); if a>n then n := a; if b>n then n := b; lst[a] := i; l[i] := b; d[i] := c end; Close(t) end; 4.2 Funkcija Min(var f, c : mas; n : integer):integer; funkcija suranda minimuma tarp dar nenudazytu virsuniu parametrai: f - nuotolių masyvas, ieškoma minimalaus elemento c - kurios virsunės nedažytos n - masyvu ilgis funkcija grazina minimalaus masyvo f nuo c elemento numerį function Min(var f, c : mas; n : integer):integer; var m, i : integer; begin m := 1; while c[m]=1 do Inc(m); for i:= m to n do if (c[i]=0)and(f[i]

Daugiau informacijos...

★ Klientai rekomenduoja

Šį rašto darbą rekomenduoja mūsų klientai. Ką tai reiškia?

Mūsų svetainėje pateikiama dešimtys tūkstančių skirtingų rašto darbų, kuriuos įkėlė daugybė moksleivių ir studentų su skirtingais gabumais. Būtent šis rašto darbas yra patikrintas specialistų ir rekomenduojamas kitų klientų, kurie po atsisiuntimo įvertino šį mokslo darbą teigiamai. Todėl galite būti tikri, kad šis pasirinkimas geriausias!