Autors: KONSTANTĪNS GUSEVS
Programmas rakstīta valodā
Borland Pascal 7.01 un domāta DOS operētājsistēmām. Apraksts rakstīts
Word 97. Kursa darbā ietilpst programmas apraksts, darba teorētiskais
pamatojums, paskaidrojumi tās lietotājiem, kontrolpiemērs, secinājumi un
semestra laikā veiktie laboratorijas darbi. Kursa darba apraksts satur 9
lapaspuses.
Programmas rakstītas divos
failos. Pirmajā daļā iespējams apskatīs šādas grafa pieraksta formas:
·
blakusvirsotņu matricu;
·
sarakstu struktūra (ar attslēgmasīvu) ieejošiem lokiem.
Otrajā daļā – Dejkstras algoritma realizācija (īsākā
ceļa meklēšana starp grafa virsotnēm).
SATURA RĀDĪTĀJS.
1. Titullapa 1
2. Anotācija 2
3. Satura rādītājs 3
4. Uzdevuma nostādne 4
5. Darba teorētiskais
pamatojums 4
6. Paskaidrojumi programmas
lietotājiem 5
7. Kontrolpiemērs 6
8. Secinājumi 8
9. Literatūras saraksts 9
UZDEVUMA
NOSTĀDNE.
1. Parādīt šādas grafa pieraksta formas:
- blakusvirsotņu matricu;
- sarakstu struktūra (ar
attslēgmasīvu) izejošiem lokiem.
2.Īsākā ceļa atrašana ar Dejkstras algoritmu.
DARBA
TEORĒTISKAIS PAMATOJUMS.
Blakus virsotņu matrica.
Blakus
virsotņu matrica A ir tāda matrica, kura elementi var pieņemt divas vērtības.

Matrica ir kvadrātiska. Izmērs ir kopas |V|x|V|. Orientētiem
grafiem ir divas lokālās pakāpes:
A=
![]() |
·
Ieejošā - 

·
Izejošā - 

Neorientētā grafā matrica
vienmēr ir simetriska attiecībā pret galveno diogonāli.
![]() |
A=
![]() |
Ja A ir blakus virsotņu matrica
grafam G, tad elements (i,j) matricā Ak ir vienāds ar dažādu ceļu
skaitu, kas ved no i-tās virsotnes uz j-to virsotni.
Loku saraksts ir kopa, kurā katrs
loks ir aprakstīts ar virsotnes pāri.
Dejkstras algoritms.
Šis algoritms
izmanto maināmo iezīmju piešķiršanas tehniku. Algoritma izpildes gaitā katrai
virsotnei tiek piešķirta iezīme. Iezīme norāda īsāko ceļu no fiksētās sākuma
virsotnes uz apskatāmo virsotni – augošo robežu, un algoritms ir iteratīvs.
Katrā iterācijā tikai viena iezīme kļūst konstanta un šī iezīme norāda īsākā
ceļa garumu.
Slēgts grafs, kur lokiem ir uzlikti svari (piešķirtas
skaitliskās vērtības). Svari – var būt kilometri, izmaksas, laiks u.t.t.
Svariem ir jābut pozitīviem, nedrīkst būt loki ar negatīvo svaru: Wij>=0.
Algoritmiska forma.
Dots: l (Vi), Wij>=0
1. solis l (a)=0; l (Vi)=
; Vi
a; p=a


2. solis Vi
T (p)

Visām
Vi, kurām mainās iezīmes, maina tās.
l
(Vi)=min[l (Vi), l (p)+ W (p,Vi)]
3. solis l (V*)=min[l (Vi)]
Izvēlas
no visām iezīmēm vismazāko, un to pārvērš par konstanti.
4. solis l (V*), p=V* (uzskata par konstanti)
5. solis Pāriet uz
2.soli, ja ir virsotnes ar maināmām iezīmem. Pretējā gadijumā algoritms tiek
beigts.
l (Vi’) + W (Vi ’,Vi) = l (Vi)
Īsākā ceļa atrašana, kāpjoties pa vienai virsotnei atpakaļ.
PASKAIDROJUMI
PROGRAMMAS LIETOTĀJIEM
SVBVM.EXE (izveidot blakusvirsotņu matricu un noteikt
lokālās pakāpes):
No sākuma jāievada virsotņu skaits no 8 līdz 12 un
loku skaits no 10 līdz 15. Tālāk tiek ievadīti dati, aiz katra ievaddata
spiežot . Kad ievadīti visi dati, automatiski parādās vēlamais
gala rezultāts. Lai turpināt darbu, jānospiež jebkurš taustiņš.
DEJEXTRA.EXE (īsākā ceļu meklēšana)
No sākuma
jāievada virsotņu skaits no 8 līdz 12 un loku skaits no 10 līdz 15. Tālāk tiek
ievadīti dati, aiz katra ievaddata spiežot . Kad ievadīti visi
dati, automatiski parādās vēlamais gala rezultāts. Lai turpinātu darbu,
jānospiež jebkurš taustiņš.
KONTROLPIEMĒRS
Lai varētu
izpildīt pirmo uzdevumu jāpalaiž fails ‘svbvm.exe’.
No sākuma jāievada virsotņu skaits [8-12] un loku skaits [10-15]. Un tad jāsāk
ievadīt ievaddati no kuras virsotnes, uz kuru.
Virsotņu skaits? [8..12]: 8
Loku skaits? [10..15]: 10
Uz: 1 2 3 4 5 6 7 1 4 2
No: 2 3 4
5 6 7 8 5
8 5
Pēc pēdējā
ievaddata automātiski parādās gala rezultāts.
Blakusvirotņu matrīca:
0 1
0 0 1 0 0 0
0 0
1 0 1 0 0 0
0 0
0 1 0 0 0 0
0 0
0 0 1 0 0 1
0 0
0 0 0 1 0 0
0 0
0 0 0 0 1 0
0 0
0 0 0 0 0 1
0 0
0 0 0 0 0 0
Srakstu struktūra ar
atslёgmasīvu ieejošiem lokiem:
AM: 2 4
5 7 8 9 10
10
M: 2
5 3 5 4 5
8 6 7 8
Lai pabeigt darbu, jānospiež jebkurš taustiņš.
Lai
varētu izpildīt otro uzdevumu jāpalaiž fails ‘dejexstra.exe’ Sākumā ievada virsotņu un loku skaitu, un tad sāk
ievadīt ievaddatus (izejošās, ieejošās virsotnes un svaru). Beigās parādās
īsākais ceļš un šā ceļa garums.
Ievadīt virsotņu
skaitu [8..15]: 8
Ievadīt loku skaitu
[10..15]: 10
Sākuma virsotne Beigu virsotne Svars
1.
1 2 3
2.
2 3 4
3.
3 4 5
4.
4 5 6
5.
5 6 7
6.
6 7 7
7.
7 8 4
8.
8 3 2
9.
4 7 1
10. 8 3 10
Īsākais ceļš: 1 - 2 -
3 - 8
Ceļa garums: 17
SECINĀJUMI.
SECINĀJUMI.
Abas
programmas pilda uzdevuma prasības, protams, pie korektiem ieejas datiem. Tās
ir diezgan ērtas lietošanā. Programmu “Svbvm.exe” var izmantot grafa pieraksta
formas apskatīšanai. Programmu “Dejextra.exe” var izmantot īsāko ceļu noteikšanai
starp virsotnem grafā.
LITERATŪRAS SRAKSTS.
Prof. Grundspeņķa lekcijas
pieraksti – ’97.
Nav komentāru:
Ierakstīt komentāru