Riješite problem traženja najkraćeg puta pomoću Dijkstrinog algoritma.
Pronađite najkraći put od X0 do X7. Graf je definiran elementima matrice troškova
Izgradimo ovaj grafikon 
Počnimo s elementom X0 i dodijelimo mu oznaku 0, razmotrimo sve njegove susjede, jer Tamo još nema oznaka, pa im dodijelimo odgovarajuće duljine: 
Svi susjedi X0 su razmatrani, označite ga i prijeđite na vrh X1. Njegovi susjedi su X0, X2, X4, ali X0 je označen, pa ga ne uzimamo u obzir. Za X2: 
, ostaviti trag.
Za X4: 
, zamijenite naljepnicu. Razmotreni su svi susjedi vrha X1, označite ga 
idi na vrh X2. NJEGOVI susjedi X0, X1, X3, X4, X5, X6, ali X0, X1 su označeni, ne razmatramo ih.
Za X3: 
, ostaviti trag.
Za X5: 
, zamijenite naljepnicu.
Za X4: 
, ostaviti trag.
Za X6: 
, zamijenite naljepnicu.
Svi susjedi vrha X2 su uzeti u obzir, pa ga označavamo. 
prelazimo na vrh X3. NJEGOVI susjedi X0, X2, X6, ali X0, X2 su označeni, ne razmatramo ih.
Za X6: 
, ostaviti trag.
Svi susjedi vrha X3 su uzeti u obzir, pa ga označavamo. 
prelazimo na vrh X4. NJEGOVI susjedi X1, X2, X5, X7, ali X1, X2 su označeni, ne uzimamo ih u obzir.
Za X5: 
, zamijenite naljepnicu.
Za X7: 
, zamijenite naljepnicu.
Svi susjedi vrha X4 su uzeti u obzir, pa ga označavamo. 
prelazimo na vrh X5. NJEGOVI susjedi X2, X4, X6, X7, ali X2, X4 su označeni, ne uzimamo ih u obzir.
Za X6: 
, ostaviti trag.
Za X7: 
, ostaviti trag.
Svi susjedi vrha X5 su uzeti u obzir, označavamo ga. 
idi na vrh X6. NJEGOVI susjedi X2, X3, X5, X7, ali X2, X3, X5 su označeni, ne uzimamo ih u obzir.
Za X7: 
, ostaviti trag.
Svi susjedi vrha X6 su uzeti u obzir, pa ga označavamo. I označavamo preostali X7, svi vrhovi su uzeti u obzir. 
Zaključak: Najkraći put njihovog X0 do X7 ima duljinu 101, ovaj put: X7-X4-X1-X0.
Pogledajmo primjer pronalaženja najkraćeg puta. Dana je mreža autocesta koje povezuju područja grada. Neke su ceste jednosmjerne. Pronađite najkraće rute od centra grada do svakog grada u regiji.
Za rješavanje ovog problema možete koristiti Dijkstrin algoritam je graf algoritam koji je izumio nizozemski znanstvenik E. Dijkstra 1959. godine. Pronalazi najkraću udaljenost od jednog od vrhova grafa do svih ostalih. Radi samo za grafove bez rubova negativne težine.
Pretpostavimo da trebate pronaći najkraće udaljenosti od 1. vrha do svih ostalih.
Krugovi označavaju vrhove, linije označavaju putove između njih (rubovi grafa). Brojevi vrhova označeni su u krugovima, njihova težina je naznačena iznad rubova - duljina staze. Pored svakog vrha nalazi se crvena oznaka - duljina najkraćeg puta do tog vrha od vrha 1.
Oznaka samog vrha 1 postavljena je na 0, oznake ostalih vrhova postavljene su na nedostižno veliki broj(idealno beskonačno). Ovo odražava da udaljenosti od vrha 1 do drugih vrhova još nisu poznate. Svi vrhovi grafa označeni su kao neposjećeni. 
Prvi korak
Najnižu oznaku ima vrh 1. Njegovi susjedi su vrhovi 2, 3 i 6. Redom obilazimo susjede vrha.
Prvi susjed vrha 1 je vrh 2, jer je duljina puta do njega minimalna. Duljina puta do njega kroz vrh 1 jednaka je zbroju najkraće udaljenosti do vrha 1, vrijednosti njegove oznake i duljine brida koji ide od 1. do 2., odnosno 0 + 7 = 7. Ovo je manje od trenutne oznake vrha 2 (10000), tako da je nova oznaka 2. vrha 7. 
Slično, nalazimo duljine staza za sve ostale susjede (vrhovi 3 i 6).
Provjeravaju se svi susjedi vrha 1. Trenutna minimalna udaljenost do vrha 1 smatra se konačnom i ne može se mijenjati. Vertex 1 je označen kao posjećen.
Drugi korak
Korak 1 algoritma se ponavlja. Opet nalazimo "najbliži" od neposjećenih vrhova. Ovo je vrh 2 s oznakom 7.
Opet pokušavamo smanjiti oznake susjeda odabranog vrha, pokušavajući proći kroz 2. vrh u njih. Susjedi vrha 2 su vrhovi 1, 3 i 4.
Vertex 1 je već posjećen. Sljedeći susjed vrha 2 je vrh 3, budući da ima minimalnu oznaku vrhova označenih kao neposjećeni. Ako idete do njega kroz 2, tada će duljina takvog puta biti jednaka 17 (7 + 10 = 17). Ali trenutna oznaka trećeg vrha je 9 i 9< 17, поэтому метка не меняется.
Još jedan susjed vrha 2 je vrh 4. Ako idete do njega kroz 2., tada će duljina takvog puta biti jednaka 22 (7 + 15 = 22). Od 22<10000, устанавливаем метку вершины 4 равной 22.
Svi susjedi vrha 2 su pregledani, označite ga kao posjećeno.
Treći korak
Ponavljamo korak algoritma odabirom vrha 3. Nakon njegove “obrade” dobivamo sljedeće rezultate. 
Četvrti korak
Peti korak
Šesti korak
Dakle, najkraći put od vrha 1 do vrha 5 je put kroz vrhove 1 — 3 — 6 — 5
, budući da se na taj način udebljamo minimalno 20.
Počnimo izvoditi najkraći put. Znamo duljinu puta za svaki vrh, a sada ćemo razmotriti vrhove s kraja. Razmatramo konačni vrh (u ovom slučaju, vrh 5
), a za sve vrhove s kojima je povezan, nalazimo duljinu puta oduzimanjem težine odgovarajućeg brida od duljine puta konačnog vrha.
Da, vrh 5
ima duljinu puta 20
. Povezan je s vrhovima 6
I 4
.
Za vrh 6
dobivamo težinu 20 - 9 = 11 (podudarno).
Za vrh 4
dobivamo težinu 20 - 6 = 14 (nije odgovaralo).
Ako kao rezultat dobijemo vrijednost koja odgovara duljini staze dotičnog vrha (u ovom slučaju, vrha 6
), tada je iz njega napravljen prijelaz na konačni vrh. Ovaj vrh označavamo na željenoj stazi.
Zatim određujemo rub kroz koji smo došli do vrha 6
. I tako dok ne dođemo na početak.
Ako, kao rezultat takvog obilaska, na nekom koraku imamo iste vrijednosti za nekoliko vrhova, tada možemo uzeti bilo koji od njih - nekoliko puta će imati istu duljinu.
Implementacija Dijkstrinog algoritma
Kvadratna matrica se koristi za pohranjivanje težina grafa. Zaglavlja redaka i stupaca sadrže vrhove grafa. A težine lukova grafova smještene su u unutarnje ćelije tablice. Graf ne sadrži petlje, tako da glavna dijagonala matrice sadrži nulte vrijednosti.
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 1 | 0 | 7 | 9 | 0 | 0 | 14 |
| 2 | 7 | 0 | 10 | 15 | 0 | 0 |
| 3 | 9 | 10 | 0 | 11 | 0 | 2 |
| 4 | 0 | 15 | 11 | 0 | 6 | 0 |
| 5 | 0 | 0 | 0 | 6 | 0 | 9 |
| 6 | 14 | 0 | 2 | 0 | 9 | 0 |
Implementacija u C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#define _CRT_SECURE_NO_WARNINGS
#uključi
#uključi
#definiraj VELIČINU 6
int main()
{
int a; // matrica veze
int d; // minimalna udaljenost
int v; // posjećeni vrhovi
int temp, minindex, min;
int početni_indeks = 0;
sustav("chcp 1251");
sustav("cls");
// Inicijaliziraj matricu veze
za (int i = 0; i
a[i][i] = 0;
za (int j = i + 1; j
scanf("%d" , &temp);
a[i][j] = temp;
a[j][i] = temp;
}
}
// Izlaz matrice veze
za (int i = 0; i
za (int j = 0; j
printf("\n" );
}
//Inicijalizacija vrhova i udaljenosti
za (int i = 0; i
d[i] = 10000;
v[i] = 1;
}
d = 0;
// Korak algoritma
čini(
mini indeks = 10000;
min = 10000;
za (int i = 0; i
if ((v[i] == 1) && (d[i]
min = d[i];
miniindeks = i;
}
}
// Dodajte pronađenu minimalnu težinu
// na trenutnu težinu vrha
// i usporedite s trenutnom minimalnom težinom vrha
ako (minindex != 10000)
{
za (int i = 0; i
ako (a[i] > 0)
{
temp = min + a[i];
ako (temp< d[i])
{
d[i] = temp;
}
}
}
v = 0;
}
) dok (minindex< 10000);
// Ispis najkraćih udaljenosti do vrhova
printf( "\nNajkraće udaljenosti do vrhova:\n");
za (int i = 0; i
// Vrati put
int ver; // niz posjećenih vrhova
int kraj = 4; // krajnji indeks vrha = 5 - 1
ver = kraj + 1; // početni element - završni vrh
int k = 1; // indeks prethodnog vrha
int težina = d; // težina konačnog vrha
dok (kraj != početni_indeks) // dok ne dođemo do početnog vrha
{
za (int i = 0; i
if (a[i] != 0) // ako postoji veza
{
int temp = težina - a[i]; // odredimo težinu puta od prethodnog vrha
ako (temp == d[i]) // ako težina odgovara izračunatoj
{ // to znači da je došlo do prijelaza iz ovog vrha
težina = temp; // spremite novu težinu
kraj = i; // spremanje prethodnog vrha
ver[k] = i + 1; // i zapišite ga u niz
k++;
}
}
}
// Ispis staze (početni vrh je završio na kraju niza od k elemenata)
printf( "\nIzbaci najkraći put\n");
za (int i = k - 1; i >= 0; i--)
printf("%3d ", ver[i]);
getchar(); getchar();
povratak 0;
}
Rezultat izvršenja
Leđa:
Dijkstrin algoritam dizajniran je za pronalaženje najkraćeg puta između vrhova u neusmjerenom grafu.
Ideja algoritma je sljedeća: prvo izaberemo put do početnog vrha jednak nuli i dodamo ovaj vrh u skup već odabranih, od kojih se određuje udaljenost do preostalih neodabranih vrhova. U svakoj sljedećoj fazi nalazimo sljedeći odabrani vrh čija je udaljenost najmanja, a povezan bridom s nekim vrhom iz skupa neodabranih (ta će udaljenost biti jednaka udaljenosti do odabranog vrha plus duljina ruba).
Primjer 1. Pronađite najkraći put na grafu od vrha L do vrha D(Slika 10.7).
Riža. 10.7.
Napišimo algoritam kao niz koraka (tablica 10.1). Korak 1. Odredite udaljenosti od početnog vrha L prije svih ostalih.
Tablica 10.1
Dijkstrina metoda (prvi korak)
|
Odabran |
Put do odabranog vrha |
Neodabrani vrh |
|||||||
Korak 2. Odaberite najkraću udaljenost od L prije U; pronađeni vrh U prihvaćen kao novoizabrani. Pronađena najmanja udaljenost pribraja se duljinama bridova iz novog vrha U prije svih ostalih. Odaberite minimalnu udaljenost od U prije N. Novi vrh N prihvaćen kao odabran (Tablica 10.2).
Tablica 10.2
Dijkstrina metoda (drugi korak)
|
Odabran |
Put do odabranog vrha |
Neodabrani vrh |
|||||||
Radi jasnoće, ubuduće ćemo umjesto znaka oo stavljati znak “-”.
Korak 3. Odredite udaljenosti od vrha N l o svim ostalima (osim L I U), kako je prikazano u tablici. 10.3.
Tablica 10.3
Dijkstrina metoda (treći korak)
|
Odabran |
Put do odabranog vrha |
Neodabrani vrh |
|||||||
Udaljenost od vrha L kroz vrh N do vrhovi G jednako 18 konvencionalnih jedinica. Ova udaljenost je veća od udaljenosti LB+BG= 16 konvencionalnih jedinica, zbog čega se dalje ne uzima u obzir. Nastavljajući slične konstrukcije, sastavljamo tablicu. 10.4. Tako je nađena duljina najkraćeg puta između vrhova L I D(44 konvencionalne jedinice).
Putanja se određuje na sljedeći način. Izvodimo obrnuto skeniranje od konačnog vrha do početnog. Gledamo kroz stupac koji odgovara vrhu odozdo prema gore i bilježimo prvo pojavljivanje minimalne vrijednosti. U stupcu koji odgovara vrhu D, prvi put se minimalna duljina od 44 konvencionalne jedinice pojavila na dnu u četvrtom retku. Ova linija označava vrh S, na koje ići, tj. Zatim trebamo razmotriti stupac koji odgovara vrhu S.
Tablica 10.4
|
Odabrani vrh |
Put do odabranog vrha |
Neodabrani vrh |
|||||||
U ovom stupcu minimalna duljina jednaka 27 konvencionalnih jedinica označava sljedeći vrh G, na koje treba ići itd. Dakle, dobivamo trajektoriju puta: (L, B, G, S, D).
Primjer 8. Pronađite najkraći put na grafu između 1. i 7. vrha (slika 10.8).
Određujemo (tablica 10.5) sljedeći odabrani vrh čija je udaljenost najmanja i povezana rubom s jednim od vrhova koji pripadaju skupu neodabranih (ta će udaljenost biti jednaka udaljenosti do odabranog vrha plus duljina ruba).
Riža. 10.8. Grafikon (A) i njemu odgovarajuću matricu susjedstva (b)
Tablična implementacija Dijkstrine metode
Tablica 10.5
|
Odabran |
Put do odabranog vrha |
Neodabrani vrh |
||||||
|
u 6 |
||||||||
Izvodimo obrnuto skeniranje od konačnog vrha do početnog.
Gledamo kroz stupac koji odgovara vrhu odozdo prema gore i bilježimo prvo pojavljivanje minimalne vrijednosti. Najkraći put će biti jednak (V 7 - V 5 - V 2 - U ().
I KONTROLNA PITANJA
- 1. Koja je teorijska složenost algoritama: konstrukcija stabla odlučivanja, dinamičko programiranje i Dijkstra?
- 2. Koja je osobitost korištenja stabla odlučivanja za usmjereni i neusmjereni graf?
- 3. U rješavanju kojih primijenjenih problema se koriste algoritmi za određivanje najkraćih udaljenosti između zadanih vrhova u grafu?
- 4. Može li se Dijkstrin algoritam koji se raspravlja u ovom radu primijeniti na određivanje najkraće udaljenosti u usmjerenom grafu?
- 5. Kako radi Dijkstrin algoritam?
- 6. Kako algoritam dinamičkog programiranja radi u odnosu na problem određivanja najkraćih udaljenosti između vrhova u grafu?
Dijkstrin algoritam je algoritam za graf koji pronalazi najkraći put između dva zadana vrha u grafu s nenegativnim duljinama luka. Često se postavlja i zadatak izračunavanja najkraćeg puta od danog vrha do svih ostalih. Algoritam se široko koristi u programiranju, na primjer, koristi se u protokolima za usmjeravanje.
Opis
Ulaz algoritma je težinski usmjereni graf s lukovima nenegativne težine. Izlaz je skup najkraćih putova od danog vrha do drugih.
Na početku se pretpostavi da je udaljenost početnog vrha jednaka nuli, a da su udaljenosti do svih ostalih beskonačne. Niz zastavica koje pokazuju da li je vrh prijeđen ispunjen je nulama. Zatim se u svakom koraku ciklusa traži vrh s minimalnom udaljenošću od izvornog i zastavom jednakom nuli. Za njega se postavlja zastavica i provjeravaju se svi susjedni vrhovi. Ako je prethodno izračunata udaljenost od izvornog vrha do onog koji se provjerava veća od zbroja udaljenosti do trenutnog vrha i duljine brida od njega do vrha koji se provjerava, tada se udaljenost do vrha koji se provjerava izjednačava s na udaljenost do struje + rub od struje do one koja se provjerava. Ciklus završava kada zastavice svih vrhova postanu jednake 1, ili kada je udaljenost do svih vrhova sa zastavicom 0 beskonačna. Zadnji slučaj je moguć ako i samo ako je graf nepovezan.
Dijkstrin algoritam u pseudokodu
Ulaz: S: niz realnih – matrica duljina luka grafa; s je vrh od kojeg se traži najkraći put i t je vrh do kojeg se traži.
Izlaz: vektori T: niz realnih; i N: niz od 0..r. Ako vrh v leži na najkraćem putu od s Do t, Da Televizor]- duljina najkraćeg puta od s Do y; Dobro] - vrhunac koji neposredno prethodi na na najkraćem putu.
N – niz u kojem vrh n odgovara vrhu m, prethodnom na putu do n iz s.
T je niz u kojem vrh n odgovara udaljenosti od njega do s.
X je niz u kojem vrh n odgovara 1 ako je put do njega poznat, odnosno 0 ako nije.
inicijaliziranje nizova:
za v od 1 do Rčini
T[v]: = ∞ (najkraći put nepoznat)
X[v]: = 0 (svi vrhovi su neoznačeni)
H[s]: = 0 ( s ništa ne prethodi)
T[s]: = 0 (najkraći put ima duljinu 0...)
X[s]: = 1 (...i poznat je) v : = s (trenutni vrh)
M: (napomene o ažuriranju)
za i ∈ G( I) čini
ako X[i] = 0 & T[i]> Televizor] + C zatim
T[i]: = Televizor] + C(nađen je kraći put od s V I kroz v }
H[u]:= v(sjeti se)
m: = ∞
v : = 0
(traženje kraja najkraćeg puta)
za I od 1 do str čini
ako X[u] = 0 &T[u]< t zatim
v:= u;
m:= T[u](vrh v završava najkraći put od s
ako v = 0 onda
zaustaviti (nema puta od s V t) završi ako
ako v= t zatim
stop (pronađen najkraći put od s V t) završi ako
X[v]: = 1 (pronađen najkraći put od s V v ) ići M
Obrazloženje
Da bismo dokazali ispravnost Dijkstrinog algoritma, dovoljno je uočiti da svaki put kada se izvrši tijelo petlje koje počinje s oznakom M, v koristi se vrh za koji je poznat najkraći put od vrha s. Drugim riječima, ako je X[v] = 1, tada je T[v] = d(s,v) , a svi vrhovi na putu (s,v) definiranom vektorom H imaju isto svojstvo, tj
Vu T[u] = 1 => T[u] = d(s,u)&T] = 1.
Doista (indukcijom), prvi put kao v koristi se vrh s čiji je najkraći put prazan i ima duljinu 0 (neprazni putovi ne mogu biti kraći jer su duljine lukova nenegativne). Neka je T[u] = d(s,u) za sve prethodno označene vrhove I. Razmotrimo novooznačeni vrh v, koji se bira iz uvjeta T[v] = min T[i]. Imajte na umu da ako je poznat put koji prolazi kroz označene vrhove, tada je poznat i najkraći put. Pretpostavimo (kontradiktivno) da je T[v]> d(s, v), odnosno pronađeni put koji vodi od s V v, nije najkraći. Tada na ovoj stazi moraju postojati neoznačeni vrhovi. Razmotrimo prvi vrh w na ovom putu, tako da je T[w] = 0. Imamo: T[w] = d(s,w)⩽d(s>v)< Т[v],что противоречит выбору вершины u.
Vremenska složenost
Složenost Dijkstrinog algoritma ovisi o metodi pronalaženja neposjećenog vrha s minimalnom udaljenošću od originalnog, načinu pohranjivanja skupa neposjećenih vrhova i načinu ažuriranja oznaka. Neka je n broj vrhova, a neka je m broj bridova u grafu. Zatim, u najjednostavnijem slučaju, kada se za traženje vrha s minimalnom udaljenošću od izvornog vrha skenira cijeli skup vrhova, a niz se koristi za pohranjivanje udaljenosti, vrijeme rada algoritma je O(n 2 ). Glavna petlja se izvodi oko n puta, u svakoj od njih oko n operacija se troši na pronalaženje minimuma. Ciklusi kroz susjede svakog posjećenog vrha zahtijevaju broj operacija proporcionalan broju bridova m (budući da se svaki brid pojavljuje točno dva puta u tim ciklusima i zahtijeva konstantan broj operacija). Dakle, ukupno vrijeme rada algoritma je O(n 2 +m), ali budući da je m mnogo manje od n(n-1), konačni rezultat je O(n 2).
Za rijetke grafove (to jest, one za koje je m mnogo manji od n²), neposjećeni vrhovi mogu se pohraniti u binarnu gomilu, a vrijednosti udaljenosti mogu se koristiti kao ključ. Budući da se petlja izvodi oko n puta, a broj opuštanja (promjena oznake) nije veći od m, vrijeme izvođenja takve implementacije je O(nlogn+mlogn)
Primjer
Izračun udaljenosti od vrha 1 na temelju prohodnih vrhova:
Najkraći put se smatra pomoću nekog matematičkog objekta koji se zove graf. traži najkraći put provodi se između dva zadana vrha u grafu. Rezultat je staza, odnosno slijed vrhova i bridova incidentnih na dva susjedna vrha, i njegova duljina.
Pogledajmo tri najčešća učinkovit algoritam nalaz najkraći put:
- Dijkstrin algoritam;
- Floydov algoritam;
- algoritmi pretraživanja.
Ovi se algoritmi lako izvode s malim brojem vrhova u grafu. Kako se njihov broj povećava, zadatak pretraživanja najkraći put postaje kompliciranije.
Dijkstrin algoritam
Ovaj algoritam je graf algoritam, koji je izumio nizozemski znanstvenik E. Dijkstra 1959. godine. Algoritam pronalazi najkraću udaljenost od jednog od vrhova grafa do svih ostalih i radi samo za grafove bez bridova negativne težine.
Svakom vrhu je dodijeljena težina - to je težina puta od početnog vrha do ovog. Također, svaki vrh se može odabrati. Ako je vrh odabran, onda je put od njega do početnog vrha najkraći, ako nije, onda je privremen. Prelazeći graf, algoritam izračunava rutu za svaki vrh, te, ako se pokaže da je najkraći, odabire vrh. Težina ovog vrha postaje težina staze. Za sve susjede zadanog vrha, algoritam također izračunava težinu, ali ih ni pod kojim uvjetima ne odabire. Algoritam završava svoj rad dolaskom do konačnog vrha i težine najkraći put postaje težina konačnog vrha.
Dijkstrin algoritam
Korak 1. Svim vrhovima, osim prvom, dodjeljuje se težina jednaka beskonačnosti, a prvom vrhu se dodjeljuje težina jednaka 0.
Korak 2. Nisu odabrani svi vrhovi.
Korak 3. Prvi vrh se proglašava trenutnim.
Korak 4. Težina svih neodabranih vrhova ponovno se izračunava pomoću formule: težina neodabranog vrha je minimalni broj stare težine ovog vrha, zbroj težine trenutnog vrha i težine brida koji povezuje trenutni vrh u neodabrani.
Korak 5. Među neodabranim vrhovima traži se vrh s minimalnom težinom. Ako niti jedan nije pronađen, odnosno težina svih vrhova je beskonačno jednaka, tada ruta ne postoji. Stoga je izlaz . U suprotnom, pronađeni vrh postaje trenutni. Ona se ističe.
Korak 6. Ako je trenutni vrh konačni, tada je put pronađen, a njegova težina je težina konačnog vrha.
Korak 7. Idite na korak 4.
U programskoj implementaciji Dijkstrin algoritam Konstruirajmo skup S vrhova za koje su već poznati najkraći putovi od početnog vrha. U svakom koraku skupu S dodaje se jedan od preostalih vrhova čija je udaljenost od početnog vrha manja nego kod ostalih preostalih vrhova. U ovom slučaju koristit ćemo niz D u kojem su zapisane duljine najkraći putevi za svaki vrh. Kada skup S sadrži sve vrhove grafa, tada će niz D sadržavati duljine najkraći putevi od početnog vrha do svakog vrha.
Osim navedenih nizova, koristit ćemo matricu duljina C, gdje je element C duljina brida (i,j), ako brida nema, tada se pretpostavlja da je njegova duljina jednaka beskonačnosti, tj. , veća od bilo koje stvarne duljine rubova. Zapravo, matrica C je matrica susjedstva, u kojem su svi nulti elementi zamijenjeni beskonačnim.
Za određivanje