Diskrētās struktūras datorzinātnēs

Programmas rakstītas divos failos. Pirmajā daļā iespējams apskatīs šādas grafa pieraksta formas:

Otrajā daļā – Dejkstras algoritma realizācija (īsākā ceļa meklēšana starp grafa virsotnēm).

Blakus virsotņu matrica A ir tāda matrica, kura elementi var pieņemt divas vērtības.

Neorientētā grafā matrica vienmēr ir simetriska attiecībā pret galveno diogonāli.

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.

Š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.

1. solis l (a)=0; l (Vi)= ; Vi a; p=a

5. solis Pāriet uz 2.soli, ja ir virsotnes ar maināmām iezīmem. Pretējā gadijumā algoritms tiek beigts.

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ņš.

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ņš.