Diskrētās struktūras datorzinātnēs. Bināras attieksmes un ceļu meklēšana grafā

Īsako ceļu meklēsanai grafā plaši pielieto Deikstras algoritmu. Deikstra algoritma uzdēvums ir orientetā, neorientetā vai jauktā grafā V atrst īsako ceļu no uzdotas vīrsotnes parejās virsotnēs.
Deikstra risinājums.(1959.g)
Algoritms lieto 3 masīvus no N (=grafu virsotņu skaitu) skaitļu katrs. Pirmais masīvs A satūr iezīmes ar divām vērtībam: 0(virsotne vel nav apskatīta) un 1(virsotne jau apskatīta); otrs masīvs B satūr attalumus – tekošo īsako attalumu no līdz blakus vīrsotnei; trešais masīvs satūr vīrsotņu numurus – k-tais elements l[k] ir priekšpedejas vīrsotnes numurs uz tēkoso visīsāko ceļuno Vi uz Vk. Attālumu matrica w[i,k] uzdod loku garumu w[i,k]; ja tādu loku nav, tad w[i,k] tiek piešķīrts lielais skaitlis B, kas vienads ar “tehnisko bezgalību”.
Lai izpildītu algoritmu vajag N reizes apskatīt masīvs B no N elementiem, tātād Deikstra algoritmam ir taisnstūra saražģitības pakāpe: O(n2). Piekām Deikstra algoritms ir efektīvs tikai pie pizitīviem svāriem w[i,k]0;
Sākotnējo iezīmju piešķiršana
1.solis l(a)=0 un tā ir konstante
l(k)=
via
p=a
Iezīmju maiņa
2.1solis Vi   (i)
l(k)=min
[l(k), l(i)+w[i,k]] (Visām virsotnēm kuras pieder i attēlam ar maināmām iezīmēm maina iezīmi saskaņā ar šo rindiņu)
Iezīmju pārvēršana konstantē
3.solis. Starp virsotnēm ar maināmam iezīmem atrast tāduvirsotni v* ,kurai spēkā ir nosacījums: l(v*)=min l(k) , uzskatot šo iezīmi par minimālo p=v*
4.solis. Pāriet uz 2 soli, ja vēl ir virsotnes ar maināmām iezīmēm. …