Dijsktrin algoritam: C++, Python Primjer koda
Sarah Chen
Koji je najkraći put ili najkraća udaljenost?
Put od izvornog vrha do odredišnog vrha koji košta najmanje je najkraći put ili najkraća udaljenost. U teoriji grafova, moguće je imati više ruta od izvora do odredišta. Između ovih ruta, ako postoji ruta koja košta minimalni iznos, možemo je nazvati algoritmom najkraće staze.
Ovdje "Cijena" znači broj čvorova u ruti ili zbroj troškova na svakoj stazi. Staza može imati jedan ili više rubova. Veza između dva vrha naziva se "rub". Postoje različite vrste algoritama najkraćeg puta, poput Dijkstrinog algoritma, Bellman-Fordovog algoritma itd.
Ovdje raspravljamo o Dijkstrinom algoritmu
Pogledajmo sljedeći ponderirani grafikon:
- Izraz "ponderirani" znači premještanje troškova s jednog čvora na drugi. Na primjer, prelaskom s čvora 1 na čvor 2, cijena ili težina je 1.
- Put između čvora 1 do čvora 2 naziva se rub.
- "Neusmjereno" znači da možete premjestiti jedan čvor na drugi i natrag na prethodni čvor. Dakle, ako pokušamo pronaći sve rute od čvora 1 do čvora 7, tada će biti:
| Ruta ili put | Trošak |
|---|---|
| 1-2-6-7 | (1+3+3) = 7 |
| 1-2-3-7 | (1+9+1) = 11 |
| 1-3-7 | (7+1) = 8 |
| 1-4-5-7 | (6+2+5) = 13 |
Između ove četiri rute, možemo vidjeti da će nas prva ruta koštati 7. Dakle, to je najkraći put u smislu troškova.
Kako radi Dijkstrin algoritam
Dijkstra algoritam može pronaći najkraću udaljenost u usmjerenim i neusmjerenim težinskim grafovima. Ovaj algoritam je pohlepan jer uvijek bira najkraći ili najbliži čvor od ishodišta. Izraz "pohlepan" znači da će algoritam među nizom ishoda ili rezultata odabrati najbolji od njih.
Ovdje pokušavamo pronaći najkraće staze među svim ostalim rutama. Dakle, Dijkstrin algoritam pronalazi sve najkraće staze od jednog odredišnog čvora. Kao rezultat toga, ponaša se kao a pohlepni algoritam.
U odjeljku "primjer" u nastavku vidjet ćete pristup korak po korak. Djeluje na sljedeći način:
Korak 1) Inicijalizirajte početni čvor s 0 troškova, a ostatak čvora kao Beskonačni trošak.
Korak 2) Održavajte niz ili popis za praćenje posjećenih čvorova
Korak 3) Ažurirajte trošak čvora s minimalnim troškom. To se može učiniti usporedbom trenutnog troška s troškom puta. (Demonstracija je prikazana u odjeljku primjera)
Korak 4) Nastavite s korakom 3 dok se ne posjete svi čvorovi.
Nakon dovršetka svih ovih koraka pronaći ćemo put koji košta minimalno od izvora do odredišta.
Razlika između Dijkstre i BFS, DFS
Glavna razlika između Dijkstre i BFS-DFS je u tome što je Dijkstra algoritam za pronalaženje najkraćeg puta, a BFS, DFS je algoritam za pronalaženje puta. U općim slučajevima, BFS i DFS ne uzimaju u obzir troškove dok pronalaze put. Dakle, ovi algoritmi ne mogu jamčiti najkraći put.
2D mrežna demonstracija rada BFS-a
Ova demonstracija pokazuje da BFS pronalazi samo put. Međutim, ne mari za težinu staze. BFS (Pretraživanje u širinu) pretpostavlja da će putovanje od jednog čvora do drugog koštati samo 1.
Ali pogledajmo primjer grafikona:
Ovdje pronalazi put na razini 2. BFS prelazi Graf redoslijedom na razini. Dakle, putuje se ovako:
Korak 1) Počnite od čvora “1” i posjetite sve susjedne čvorove 2,3,4
Korak 2) Označite čvorove 2,3,4 kao razinu 1 i posjetite njihove susjedne čvorove. Nastavit će istraživati sve susjedne čvorove dok ne dođe do odredišnog čvora.
Što se tiče DFS-a, proći će put od 1 do 7 na sljedeći način:
- 1→2→3→7 (Originalni trošak 10, DFS trošak 3)
- 1→2→6→7 (Originalni trošak 7, DFS trošak 3)
- 1→3→7 (Originalni trošak 8, DFS trošak 2)
- 1→4→5→7 (Originalni trošak 13, DFS trošak 3)
Kao što vidimo, DFS izračunava svoju cijenu puta s brojem dubine ili brojem rubova.
DFS radi sljedeće:
- DFS može pronaći put od izvora (početnog vrha) do odredišta.
- Ne može jamčiti je li put otkriven od izvornog čvora do odredišta najkraći put ili nije.
Međutim, u smislu Dijkstra algoritma, odabrat će rubove na temelju njihove cijene. Kao pohlepan algoritam, odabrat će putove s najboljim ili minimalnim troškovima.
Primjer Dijkstrinog algoritma
Dijkstrin algoritam koristi cijenu ili težinu za izračun ukupne cijene puta.
Cilj Dijkstrinog algoritma je minimizirati ovaj ukupni trošak ili težinu. U gore prikazanom primjeru pronalazimo najbolje putove od čvora 1 do čvora 7, zatim izračunavamo sve troškove.
U Dijkstrinom algoritmu će pronaći najkraće staze računajući težine. Neće tražiti sve moguće putove. Demonstrirajmo Dijkstrin algoritam na primjeru. Na primjer, od vas se traži da pronađete najkraći put od čvora 1 do 7.
U nastavku su navedeni koraci za ovaj postupak:
Korak 1) Inicijalizirajte početni trošak čvora na 0.
Ostatak čvora, dodijeli “Inf”. To znači da ne postoji put između početnog vrha (izvora) i čvora ili da put još nije posjećen.
Korak 2) Kada odaberete čvor 1, on će biti označen kao posjećen. Zatim ažurirajte sve susjedne čvorove čvora 1. 2,3,4 su susjedni čvorovi čvora 1.
Dok ažuriramo trošak, moramo slijediti postupak u nastavku:
Trošak svakog čvora možemo ažurirati pomoću gornje formule. Na primjer, bili smo na čvoru 1 i morali smo ažurirati cijenu susjednog čvora 2,3,4.
Nakon ažuriranja, cijena ili težina će izgledati ovako:
Korak 3) Za čvor “2”, susjedi su 6 i 3. Trošak ažuriramo na "6" uspoređujući beskonačnost (trenutna vrijednost). Trošak čvora 2 + put košta od 2 do 6. Jednostavno rečeno, čvor "6" će imati trošak 1+3 ili 4.
Čvor 3 je susjed čvora 2. Međutim, izračunali smo njegov trošak u prethodnom koraku, koji je bio 7. Sada, ako je naš put 1-2-3, čvor 3 će imati trošak 10. Put 1-2- 3 će koštati 10, dok će 1 do 3 koštati 7.
Korak 4) Za čvor 3, susjedni čvor je 7. Dakle, uspoređujući trenutnu vrijednost čvora 7 s cijenom puta (7+1) ili 8, ažurirat ćemo cijenu čvora 7. To je 8.
Dakle, nalazimo put od čvora 1 do čvora 7, a on je 1→ 3→ 7. Cijena je 8.
Korak 5) Za čvor 4, u skladu s tim ažurirat ćemo cijenu susjednog čvora. Dakle, čvor “5” će imati ažurirani trošak od 8. Nakon koraka 4,5, izgledat će ovako:
Sada, put 1-3-7 ima cijenu 8 (ranije). Čvor “7” nije označen kao posjećen jer možemo doći do čvora “7” iz čvora “6”. Staza "1-2-6" imala je cijenu 4. Dakle, staza 1-2-6-7 će imati cijenu 7.
Kako je 7 < 8, zato će najkraći put od izvornog vrha “1” do odredišnog vrha “7” biti 1-2-6-7, a trošak je 7. Prije je bio 1-3-7, a trošak bio 8.
Dakle, konačni grafikon će izgledati ovako:
Rub označen crnom crtom je naš najkraći put od 1 do 7, a koštat će nas 7.
Dijkstrin algoritam pseudo koda
Evo pseudo-koda za Dijkstrin algoritam
Dijkstra(G, S):
for each vertex V in G
distance[V] & lt; - Infinity
previous[V] & lt; - NULL
if V does not equal S, then,
(priority queue) Q.push(V)
distance[S] = 0
While Q is not empty
U & lt; - Extract the MIN from Q
For each unvisited adjacent V of U
TotalDistance & lt; - distance[U] + edge_cost(U, V)
if TotalDistance is less than distance[V], then
distance[V] & lt; - TotalDistance
previous[V] & lt; - u
return distance, previous
C++ implementacija Dijkstrinog algoritma
Za implementaciju Dijkstrinog algoritma pomoću C++, evo koda:
#include <bits/stdc++.h>
using namespace std;
#define size 7
int minimumDistance(int distance[], bool visited[]) {
int min = INT_MAX;
int min_index = INT_MAX;
for (int i = 0; i < size; i++) {
if (!visited[i] & amp; & distance[i] <= min) {
min = distance[i];
min_index = i;
}
}
return min_index;
}
void printParentPath(int parent[], int i) {
if (parent[i] == -1) {
return;
}
printParentPath(parent, parent[i]);
cout << i + 1 << " ";
}
void dijkstra(int graph[size][size], int source) {
int distance[size];
bool visited[size];
int parent[size];
for (int i = 0; i < size; i++) {
parent[0] = -1;
distance[i] = INT_MAX;
visited[i] = false;
}
distance[source] = 0;
for (int i = 0; i < size - 1; i++) {
int U = minimumDistance(distance, visited);
visited[U] = true;
for (int j = 0; j < size; j++) {
int curr_distance = distance[U] + graph[U][j];
if (!visited[j] & amp; & graph[U][j] & amp; &
curr_distance < distance[j]) {
parent[j] = U;
distance[j] = curr_distance;
}
}
}
cout << "Vertex\t\tDistance\tPath" << endl;
for (int i = 1; i < size; i++) {
cout << source + 1 << "->" << i + 1 << "\t\t" << distance[i] << "\t\t"
<< source + 1 << " ";
printParentPath(parent, i);
cout << endl;
}
}
int main() {
int graph[size][size] = {{0, 1, 7, 6, 0, 0, 0}, {1, 0, 9, 0, 0, 3, 0},
{7, 9, 0, 0, 0, 0, 1}, {6, 0, 0, 0, 2, 0, 0},
{0, 0, 0, 2, 0, 0, 0}, {0, 3, 0, 0, 0, 0, 3},
{0, 0, 0, 0, 5, 3, 0}};
dijkstra(graph, 0);
}
Izlaz:
Vertex Distance Path 1->2 1 1 2 1->3 7 1 3 1->4 6 1 4 1->5 8 1 4 5 1->6 4 1 2 6 1->7 7 1 2 6 7
Python implementacija Dijkstrinog algoritma
Za implementaciju Dijkstrinog algoritma pomoću piton, evo koda:
num_of_vertex = 7
def minimumDistance(distance, visited):
_min = 1e11
min_index = 1e11
for i in range(num_of_vertex):
if not visited[i] and distance[i] & lt; = _min:
_min = distance[i]
min_index = i
return min_index
def printParentNode(parent, i):
if parent[i] == -1:
return
printParentNode(parent, parent[i])
print("{} ".format(i + 1), end = "")
def dijkstra(graph, src):
distance = list()
visited = list()
parent = list()
for i in range(num_of_vertex):
parent.append(-1)
distance.append(1e11)
visited.append(False)
distance[src] = 0
for i in range(num_of_vertex - 1):
U = minimumDistance(distance, visited)
visited[U] = True
for j in range(num_of_vertex):
curr_distance = distance[U] + graph[U][j]
if not visited[j] and graph[U][j] and curr_distance & lt;
distance[j]: parent[j] = U
distance[j] = curr_distance
print("Vertex\t\tDistance\tPath")
for i in range(num_of_vertex):
print("{}->{}\t\t{}\t\t{}
".format(src + 1, i + 1, distance[i], src + 1), end = "")
printParentNode(parent, i)
print("")
graph = [
[0, 1, 7, 6, 0, 0, 0],
[1, 0, 9, 0, 0, 3, 0],
[7, 9, 0, 0, 0, 0, 1],
[6, 0, 0, 0, 2, 0, 0],
[0, 0, 0, 2, 0, 0, 0],
[0, 3, 0, 0, 0, 0, 3],
[0, 0, 0, 0, 5, 3, 0]
]
dijkstra(graph, 0)
Izlaz:
Vertex Distance Path 1->1 0 1 1->2 1 1 2 1->3 7 1 3 1->4 6 1 4 1->5 8 1 4 5 1->6 4 1 2 6 1->7 7 1 2 6 7
Vidimo da algoritam izračunava najkraću udaljenost od izvornog čvora.
Primjena Dijkstra algoritma
Dijkstra Algo ima veliki skup upotreba. Među njima, naširoko se koristi u području umrežavanja. Evo nekih primjera uporabe Dijkstrinog algoritma u stvarnom životu:
Dijkstra na Google karti: U osnovi, ovaj algoritam je okosnica za pronalaženje najkraćih puteva. Kao što možemo vidjeti iz gornjeg izlaza isječka koda.
Google ne koristi jednostavan Dijkstra algoritam. Umjesto toga, koristi modificiranu verziju. Kada odaberete odredište, ono vam prikazuje više staza na Google karti. Među tim stazama, neke su staze razvrstane za korisnika. Ovi odabrani putovi temelje se na "vremenu". Dakle, "vrijeme" je najveći trošak za najkraći put.
Dijkstra u IP usmjeravanju: IP usmjeravanje je mrežna terminologija. To znači kako se vaš podatkovni paket šalje do primatelja različitim putovima. Ti se putovi sastoje od usmjerivača, poslužitelja itd. U IP usmjeravanju postoje različite vrste protokola.
Ovi protokoli pomažu usmjerivaču pronaći najkraće putove za slanje podataka. Jedan od naziva protokola je “OSPF (Open Shortest Path First)”. OSPF koristi dijkstra algoritam. Usmjerivač održava tablicu ruta. Svaki usmjerivač dijeli svoju tablicu sa susjednim usmjerivačima. Nakon primitka ažurirane tablice moraju ponovno izračunati sve staze. U to vrijeme usmjerivač koristi Dijkstra algoritam.
Ograničenje Dijkstrinog algoritma
Dijkstra algoritam ne može jamčiti najkraći put u grafu s negativnim rubom. Dijkstra algoritam slijedi ove metodologije:
- Od jednog čvora do drugog ići će jedan najkraći put.
- Jednom kada se odabere najkraći put između dva čvora, neće se ponovno izračunati.
Ovdje primijetite dva primjera s negativnim rubovima.
U lijevom grafikonu, postoje tri vrha. Dijkstra će raditi na grafikonu na sljedeći način:
Korak 1) Početni vrh "1" bit će inicijaliziran na nulu. Ostali čvorovi će imati beskonačnost.
Korak 2) Označite čvor “1” kao posjećen i uključite ga u najkraći put.
Korak 3) Udaljenost izvornog čvora 1 do čvorova "2" i "3" postavljena je na beskonačnost, budući da se najkraći put tek treba izračunati. Dakle, svaki put koji će koštati manje od beskonačnosti bit će dodan najkraćem putu (pohlepni pristup).
Korak 4) Ažuriranje udaljenosti od izvornog vrha ili izvornog čvora “1” na “2”. Trenutna težina bit će 5 (5
Korak 5) Sada ako provjerimo najkraću udaljenost od čvora "1", nalazimo da je 5 najkraća udaljenost za rub 1–> 2. Dakle, čvor "2" bit će označen kao posjećen.
Slično tome, čvor "3" također će biti označen kao posjećen jer je najkraća udaljenost 3.
Međutim, ako promatramo, postoji put 1-3-2 koji će koštati samo 2. Ali Dijkstra pokazuje da je od čvora “1” do čvora “2,” najkraća udaljenost 5. Dakle, Dijkstra nije uspio izračunati najkraću udaljenost ispravno. Razlog zašto se to dogodilo je taj što je Dijkstra pohlepan algoritam. Dakle, jednom kada je čvor označen kao posjećen, neće se ponovno razmatrati, iako bi mogao biti dostupan kraći put. Ovaj se problem pojavljuje samo kada rubovi imaju negativne troškove ili rubove negativne težine
Dijkstra ne uspijeva izračunati najkraći put između dva čvora u ovom scenariju. Kao rezultat toga, ovaj algoritam ima neke nedostatke. Za rješavanje ovog problema s negativnim rubom koristi se drugi algoritam nazvan "Bellman-Ford algoritam". Taj algoritam može raditi s negativnim rubovima.
Složenost Dijkstrinog algoritma
Gornja implementacija koristila je dvije petlje "za". Ove se petlje pokreću za određeni broj vrhova. Dakle, vremenska složenost je O(V2). Ovdje pojam "0" označava oznaku koja daje pretpostavku za Dijkstra algoritam.
Graf možemo pohraniti pomoću "Prioritetnog reda". Prioritetni red je binarna struktura podataka hrpe. Bit će učinkovitiji od 2D matrice. Rub koji će imati minimalni trošak imat će visoki prioritet.
Tada će vremenska složenost biti O(E log(V)). Ovdje je E broj bridova, a V broj vrhova.
Složenost prostora je O(V2), budući da koristimo matricu susjedstva (2D niz). Složenost prostora može se optimizirati korištenjem popisa susjedstva ili strukture podataka reda čekanja.
