Vzhľadom na vážený graf a zdrojový vrchol v grafe nájdite najkratšie cesty od zdroja po všetky ostatné vrcholy v danom grafe.
Poznámka: Daný graf neobsahuje žiadnu zápornú hranu.
Príklady:
Odporúčaný postup implementácie algoritmu Dijkstra Vyskúšajte to!Vstup: src = 0, graf je uvedený nižšie.
Výkon: 0 4 12 19 21 11 9 8 14
Vysvetlenie: Vzdialenosť od 0 do 1 = 4.
Minimálna vzdialenosť od 0 do 2 = 12. 0->1->2
Minimálna vzdialenosť od 0 do 3 = 19. 0->1->2->3
Minimálna vzdialenosť od 0 do 4 = 21. 0->7->6->5->4
Minimálna vzdialenosť od 0 do 5 = 11. 0->7->6->5
Minimálna vzdialenosť od 0 do 6 = 9. 0->7->6
Minimálna vzdialenosť od 0 do 7 = 8. 0->7
Minimálna vzdialenosť od 0 do 8 = 14. 0->1->2->8
Použitie Dijkstrovho algoritmu Matica susedstva :
Cieľom je vytvoriť a SPT (strom najkratšej cesty) s daným zdrojom ako koreňom. Udržujte maticu susedstva s dvoma sadami,
- jedna množina obsahuje vrcholy zahrnuté v strome najkratšej cesty,
- iná množina obsahuje vrcholy, ktoré ešte nie sú zahrnuté v strome najkratšej cesty.
V každom kroku algoritmu nájdite vrchol, ktorý je v druhej množine (množina ešte nie je zahrnutá) a má minimálnu vzdialenosť od zdroja.
Algoritmus :
načítanie javascriptu
- Vytvorte súpravu sptSet (súprava stromu najkratšej cesty), ktorá sleduje vrcholy zahrnuté v strome najkratších ciest, t. j. ktorých minimálna vzdialenosť od zdroja sa vypočíta a finalizuje. Na začiatku je táto sada prázdna.
- Priraďte hodnotu vzdialenosti všetkým vrcholom vo vstupnom grafe. Inicializujte všetky hodnoty vzdialenosti ako NEKONEČNÝ . Priraďte hodnotu vzdialenosti ako 0 pre zdrojový vrchol, aby bol vybratý ako prvý.
- Zatiaľ čo sptSet nezahŕňa všetky vrcholy
- Vyberte vrchol v to tam nie je sptSet a má hodnotu minimálnej vzdialenosti.
- Zahrňte vás do sptSet .
- Potom aktualizujte hodnotu vzdialenosti všetkých susedných vrcholov v .
- Ak chcete aktualizovať hodnoty vzdialenosti, iterujte cez všetky susedné vrcholy.
- Pre každý susedný vrchol v, ak súčet hodnoty vzdialenosti o v (zo zdroja) a hmotnosť hrany u-v , je menšia ako hodnota vzdialenosti v , potom aktualizujte hodnotu vzdialenosti v .
Poznámka: Používame boolovské pole sptSet[] reprezentovať množinu zahrnutých vrcholov SPT . Ak hodnota sptSet[v] je pravda, potom je zahrnutý vrchol v SPT , inak nie. Pole dist[] sa používa na uloženie hodnôt najkratšej vzdialenosti zo všetkých vrcholov.
Ilustrácia Dijkstrovho algoritmu :
Aby sme pochopili Dijkstrov algoritmus, urobme si graf a nájdime najkratšiu cestu od zdroja ku všetkým uzlom.
Zvážte nižšie uvedený graf a src = 0
Krok 1:
- Sada sptSet je na začiatku prázdny a vzdialenosti priradené k vrcholom sú {0, INF, INF, INF, INF, INF, INF, INF} kde INF označuje nekonečno.
- Teraz vyberte vrchol s hodnotou minimálnej vzdialenosti. Vyberie sa vrchol 0, zahrňte ho sptSet . Takže sptSet sa zmení na {0}. Po zahrnutí 0 až sptSet , aktualizujte hodnoty vzdialenosti jeho susedných vrcholov.
- Susedné vrcholy 0 sú 1 a 7. Hodnoty vzdialenosti 1 a 7 sa aktualizujú ako 4 a 8.
Nasledujúci podgraf zobrazuje vrcholy a ich hodnoty vzdialeností, zobrazené sú len vrcholy s hodnotami konečnej vzdialenosti. Vrcholy zahrnuté v SPT sú zobrazené v zelená farba.
Krok 2:
- Vyberte vrchol s hodnotou minimálnej vzdialenosti a ešte nie je zahrnutý SPT (nie v sptSET ). Vrchol 1 sa vyberie a pridá sptSet .
- Takže sptSet teraz sa zmení na {0, 1}. Aktualizujte hodnoty vzdialenosti susedných vrcholov 1.
- Hodnota vzdialenosti vrcholu 2 sa stane 12 .
Krok 3:
- Vyberte vrchol s hodnotou minimálnej vzdialenosti a ešte nie je zahrnutý SPT (nie v sptSET ). Vertex 7 je vybraný. Takže sptSet teraz sa stáva {0, 1, 7}.
- Aktualizujte hodnoty vzdialenosti susedných vrcholov 7. Hodnota vzdialenosti vrcholov 6 a 8 sa stáva konečnou ( 15 a 9 v uvedenom poradí).
Krok 4:algoritmus binárneho vyhľadávania
- Vyberte vrchol s hodnotou minimálnej vzdialenosti a ešte nie je zahrnutý SPT (nie v sptSET ). Vertex 6 je vybraný. Takže sptSet teraz sa stáva {0, 1, 7, 6} .
- Aktualizujte hodnoty vzdialenosti susedných vrcholov 6. Hodnoty vzdialenosti vrcholov 5 a 8 sa aktualizujú.
Vyššie uvedené kroky opakujeme, kým sptSet zahŕňa všetky vrcholy daného grafu. Nakoniec dostaneme nasledujúce S hortest Path Tree (SPT).
Nižšie je uvedená implementácia vyššie uvedeného prístupu:
C++ // C++ program for Dijkstra's single source shortest path // algorithm. The program is for adjacency matrix // representation of the graph #include using namespace std; #include // Number of vertices in the graph #define V 9 // A utility function to find the vertex with minimum // distance value, from the set of vertices not yet included // in shortest path tree int minDistance(int dist[], bool sptSet[]) { // Initialize min value int min = INT_MAX, min_index; for (int v = 0; v < V; v++) if (sptSet[v] == false && dist[v] <= min) min = dist[v], min_index = v; return min_index; } // A utility function to print the constructed distance // array void printSolution(int dist[]) { cout << 'Vertex Distance from Source' << endl; for (int i = 0; i < V; i++) cout << i << ' ' << dist[i] << endl; } // Function that implements Dijkstra's single source // shortest path algorithm for a graph represented using // adjacency matrix representation void dijkstra(int graph[V][V], int src) { int dist[V]; // The output array. dist[i] will hold the // shortest // distance from src to i bool sptSet[V]; // sptSet[i] will be true if vertex i is // included in shortest // path tree or shortest distance from src to i is // finalized // Initialize all distances as INFINITE and stpSet[] as // false for (int i = 0; i < V; i++) dist[i] = INT_MAX, sptSet[i] = false; // Distance of source vertex from itself is always 0 dist[src] = 0; // Find shortest path for all vertices for (int count = 0; count < V - 1; count++) { // Pick the minimum distance vertex from the set of // vertices not yet processed. u is always equal to // src in the first iteration. int u = minDistance(dist, sptSet); // Mark the picked vertex as processed sptSet[u] = true; // Update dist value of the adjacent vertices of the // picked vertex. for (int v = 0; v < V; v++) // Update dist[v] only if is not in sptSet, // there is an edge from u to v, and total // weight of path from src to v through u is // smaller than current value of dist[v] if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) dist[v] = dist[u] + graph[u][v]; } // print the constructed distance array printSolution(dist); } // driver's code int main() { /* Let us create the example graph discussed above */ int graph[V][V] = { { 0, 4, 0, 0, 0, 0, 0, 8, 0 }, { 4, 0, 8, 0, 0, 0, 0, 11, 0 }, { 0, 8, 0, 7, 0, 4, 0, 0, 2 }, { 0, 0, 7, 0, 9, 14, 0, 0, 0 }, { 0, 0, 0, 9, 0, 10, 0, 0, 0 }, { 0, 0, 4, 14, 10, 0, 2, 0, 0 }, { 0, 0, 0, 0, 0, 2, 0, 1, 6 }, { 8, 11, 0, 0, 0, 0, 1, 0, 7 }, { 0, 0, 2, 0, 0, 0, 6, 7, 0 } }; // Function call dijkstra(graph, 0); return 0; } // This code is contributed by shivanisinghss2110>
C // C program for Dijkstra's single source shortest path // algorithm. The program is for adjacency matrix // representation of the graph #include #include #include // Number of vertices in the graph #define V 9 // A utility function to find the vertex with minimum // distance value, from the set of vertices not yet included // in shortest path tree int minDistance(int dist[], bool sptSet[]) { // Initialize min value int min = INT_MAX, min_index; for (int v = 0; v < V; v++) if (sptSet[v] == false && dist[v] <= min) min = dist[v], min_index = v; return min_index; } // A utility function to print the constructed distance // array void printSolution(int dist[]) { printf('Vertex Distance from Source
'); for (int i = 0; i < V; i++) printf('%d %d
', i, dist[i]); } // Function that implements Dijkstra's single source // shortest path algorithm for a graph represented using // adjacency matrix representation void dijkstra(int graph[V][V], int src) { int dist[V]; // The output array. dist[i] will hold the // shortest // distance from src to i bool sptSet[V]; // sptSet[i] will be true if vertex i is // included in shortest // path tree or shortest distance from src to i is // finalized // Initialize all distances as INFINITE and stpSet[] as // false for (int i = 0; i < V; i++) dist[i] = INT_MAX, sptSet[i] = false; // Distance of source vertex from itself is always 0 dist[src] = 0; // Find shortest path for all vertices for (int count = 0; count < V - 1; count++) { // Pick the minimum distance vertex from the set of // vertices not yet processed. u is always equal to // src in the first iteration. int u = minDistance(dist, sptSet); // Mark the picked vertex as processed sptSet[u] = true; // Update dist value of the adjacent vertices of the // picked vertex. for (int v = 0; v < V; v++) // Update dist[v] only if is not in sptSet, // there is an edge from u to v, and total // weight of path from src to v through u is // smaller than current value of dist[v] if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) dist[v] = dist[u] + graph[u][v]; } // print the constructed distance array printSolution(dist); } // driver's code int main() { /* Let us create the example graph discussed above */ int graph[V][V] = { { 0, 4, 0, 0, 0, 0, 0, 8, 0 }, { 4, 0, 8, 0, 0, 0, 0, 11, 0 }, { 0, 8, 0, 7, 0, 4, 0, 0, 2 }, { 0, 0, 7, 0, 9, 14, 0, 0, 0 }, { 0, 0, 0, 9, 0, 10, 0, 0, 0 }, { 0, 0, 4, 14, 10, 0, 2, 0, 0 }, { 0, 0, 0, 0, 0, 2, 0, 1, 6 }, { 8, 11, 0, 0, 0, 0, 1, 0, 7 }, { 0, 0, 2, 0, 0, 0, 6, 7, 0 } }; // Function call dijkstra(graph, 0); return 0; }>
Java // A Java program for Dijkstra's single source shortest path // algorithm. The program is for adjacency matrix // representation of the graph import java.io.*; import java.lang.*; import java.util.*; class ShortestPath { // A utility function to find the vertex with minimum // distance value, from the set of vertices not yet // included in shortest path tree static final int V = 9; int minDistance(int dist[], Boolean sptSet[]) { // Initialize min value int min = Integer.MAX_VALUE, min_index = -1; for (int v = 0; v < V; v++) if (sptSet[v] == false && dist[v] <= min) { min = dist[v]; min_index = v; } return min_index; } // A utility function to print the constructed distance // array void printSolution(int dist[]) { System.out.println( 'Vertex Distance from Source'); for (int i = 0; i < V; i++) System.out.println(i + ' ' + dist[i]); } // Function that implements Dijkstra's single source // shortest path algorithm for a graph represented using // adjacency matrix representation void dijkstra(int graph[][], int src) { int dist[] = new int[V]; // The output array. // dist[i] will hold // the shortest distance from src to i // sptSet[i] will true if vertex i is included in // shortest path tree or shortest distance from src // to i is finalized Boolean sptSet[] = new Boolean[V]; // Initialize all distances as INFINITE and stpSet[] // as false for (int i = 0; i < V; i++) { dist[i] = Integer.MAX_VALUE; sptSet[i] = false; } // Distance of source vertex from itself is always 0 dist[src] = 0; // Find shortest path for all vertices for (int count = 0; count < V - 1; count++) { // Pick the minimum distance vertex from the set // of vertices not yet processed. u is always // equal to src in first iteration. int u = minDistance(dist, sptSet); // Mark the picked vertex as processed sptSet[u] = true; // Update dist value of the adjacent vertices of // the picked vertex. for (int v = 0; v < V; v++) // Update dist[v] only if is not in sptSet, // there is an edge from u to v, and total // weight of path from src to v through u is // smaller than current value of dist[v] if (!sptSet[v] && graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE && dist[u] + graph[u][v] < dist[v]) dist[v] = dist[u] + graph[u][v]; } // print the constructed distance array printSolution(dist); } // Driver's code public static void main(String[] args) { /* Let us create the example graph discussed above */ int graph[][] = new int[][] { { 0, 4, 0, 0, 0, 0, 0, 8, 0 }, { 4, 0, 8, 0, 0, 0, 0, 11, 0 }, { 0, 8, 0, 7, 0, 4, 0, 0, 2 }, { 0, 0, 7, 0, 9, 14, 0, 0, 0 }, { 0, 0, 0, 9, 0, 10, 0, 0, 0 }, { 0, 0, 4, 14, 10, 0, 2, 0, 0 }, { 0, 0, 0, 0, 0, 2, 0, 1, 6 }, { 8, 11, 0, 0, 0, 0, 1, 0, 7 }, { 0, 0, 2, 0, 0, 0, 6, 7, 0 } }; ShortestPath t = new ShortestPath(); // Function call t.dijkstra(graph, 0); } } // This code is contributed by Aakash Hasija>
Python # Python program for Dijkstra's single # source shortest path algorithm. The program is # for adjacency matrix representation of the graph # Library for INT_MAX import sys class Graph(): def __init__(self, vertices): self.V = vertices self.graph = [[0 for column in range(vertices)] for row in range(vertices)] def printSolution(self, dist): print('Vertex Distance from Source') for node in range(self.V): print(node, ' ', dist[node]) # A utility function to find the vertex with # minimum distance value, from the set of vertices # not yet included in shortest path tree def minDistance(self, dist, sptSet): # Initialize minimum distance for next node min = sys.maxsize # Search not nearest vertex not in the # shortest path tree for u in range(self.V): if dist[u] < min and sptSet[u] == False: min = dist[u] min_index = u return min_index # Function that implements Dijkstra's single source # shortest path algorithm for a graph represented # using adjacency matrix representation def dijkstra(self, src): dist = [sys.maxsize] * self.V dist[src] = 0 sptSet = [False] * self.V for cout in range(self.V): # Pick the minimum distance vertex from # the set of vertices not yet processed. # x is always equal to src in first iteration x = self.minDistance(dist, sptSet) # Put the minimum distance vertex in the # shortest path tree sptSet[x] = True # Update dist value of the adjacent vertices # of the picked vertex only if the current # distance is greater than new distance and # the vertex in not in the shortest path tree for y in range(self.V): if self.graph[x][y]>0 a sptSet[y] == False a dist[y]> dist[x] + self.graph[x][y]: dist[y] = dist[x] + self.graph[x][y] self.printSolution(dist) # Kód vodiča, ak __name__ == '__main__': g = Graf(9) g.graph = [[0, 4, 0, 0, 0, 0, 0, 8, 0], [4, 0, 8, 0, 0, 0, 0, 11, 0], [0, 8, 0, 7, 0, 4, 0, 0, 2], [0, 0, 7, 0, 9, 14, 0, 0, 0], [0, 0, 0, 9, 0, 10, 0, 0, 0], [0, 0, 4, 14, 10, 0, 2, 0, 0], [0, 0, 0, 0, 0, 2, 0, 1, 6], [8, 11, 0, 0, 0, 0, 1, 0, 7], [0, 0, 2, 0, 0, 0, 6, 7, 0] ] g.dijkstra(0) # Tento kód prispel Divyanshu Mehta a aktualizoval Pranav Singh Sambyal>
C# // C# program for Dijkstra's single // source shortest path algorithm. // The program is for adjacency matrix // representation of the graph using System; class GFG { // A utility function to find the // vertex with minimum distance // value, from the set of vertices // not yet included in shortest // path tree static int V = 9; int minDistance(int[] dist, bool[] sptSet) { // Initialize min value int min = int.MaxValue, min_index = -1; for (int v = 0; v < V; v++) if (sptSet[v] == false && dist[v] <= min) { min = dist[v]; min_index = v; } return min_index; } // A utility function to print // the constructed distance array void printSolution(int[] dist) { Console.Write('Vertex Distance ' + 'from Source
'); for (int i = 0; i < V; i++) Console.Write(i + ' ' + dist[i] + '
'); } // Function that implements Dijkstra's // single source shortest path algorithm // for a graph represented using adjacency // matrix representation void dijkstra(int[, ] graph, int src) { int[] dist = new int[V]; // The output array. dist[i] // will hold the shortest // distance from src to i // sptSet[i] will true if vertex // i is included in shortest path // tree or shortest distance from // src to i is finalized bool[] sptSet = new bool[V]; // Initialize all distances as // INFINITE and stpSet[] as false for (int i = 0; i < V; i++) { dist[i] = int.MaxValue; sptSet[i] = false; } // Distance of source vertex // from itself is always 0 dist[src] = 0; // Find shortest path for all vertices for (int count = 0; count < V - 1; count++) { // Pick the minimum distance vertex // from the set of vertices not yet // processed. u is always equal to // src in first iteration. int u = minDistance(dist, sptSet); // Mark the picked vertex as processed sptSet[u] = true; // Update dist value of the adjacent // vertices of the picked vertex. for (int v = 0; v < V; v++) // Update dist[v] only if is not in // sptSet, there is an edge from u // to v, and total weight of path // from src to v through u is smaller // than current value of dist[v] if (!sptSet[v] && graph[u, v] != 0 && dist[u] != int.MaxValue && dist[u] + graph[u, v] < dist[v]) dist[v] = dist[u] + graph[u, v]; } // print the constructed distance array printSolution(dist); } // Driver's Code public static void Main() { /* Let us create the example graph discussed above */ int[, ] graph = new int[, ] { { 0, 4, 0, 0, 0, 0, 0, 8, 0 }, { 4, 0, 8, 0, 0, 0, 0, 11, 0 }, { 0, 8, 0, 7, 0, 4, 0, 0, 2 }, { 0, 0, 7, 0, 9, 14, 0, 0, 0 }, { 0, 0, 0, 9, 0, 10, 0, 0, 0 }, { 0, 0, 4, 14, 10, 0, 2, 0, 0 }, { 0, 0, 0, 0, 0, 2, 0, 1, 6 }, { 8, 11, 0, 0, 0, 0, 1, 0, 7 }, { 0, 0, 2, 0, 0, 0, 6, 7, 0 } }; GFG t = new GFG(); // Function call t.dijkstra(graph, 0); } } // This code is contributed by ChitraNayal>
Javascript // A Javascript program for Dijkstra's single // source shortest path algorithm. // The program is for adjacency matrix // representation of the graph let V = 9; // A utility function to find the // vertex with minimum distance // value, from the set of vertices // not yet included in shortest // path tree function minDistance(dist,sptSet) { // Initialize min value let min = Number.MAX_VALUE; let min_index = -1; for(let v = 0; v < V; v++) { if (sptSet[v] == false && dist[v] <= min) { min = dist[v]; min_index = v; } } return min_index; } // A utility function to print // the constructed distance array function printSolution(dist) { console.log('Vertex Distance from Source '); for(let i = 0; i < V; i++) { console.log(i + ' ' + dist[i] + ' '); } } // Function that implements Dijkstra's // single source shortest path algorithm // for a graph represented using adjacency // matrix representation function dijkstra(graph, src) { let dist = new Array(V); let sptSet = new Array(V); // Initialize all distances as // INFINITE and stpSet[] as false for(let i = 0; i < V; i++) { dist[i] = Number.MAX_VALUE; sptSet[i] = false; } // Distance of source vertex // from itself is always 0 dist[src] = 0; // Find shortest path for all vertices for(let count = 0; count < V - 1; count++) { // Pick the minimum distance vertex // from the set of vertices not yet // processed. u is always equal to // src in first iteration. let u = minDistance(dist, sptSet); // Mark the picked vertex as processed sptSet[u] = true; // Update dist value of the adjacent // vertices of the picked vertex. for(let v = 0; v < V; v++) { // Update dist[v] only if is not in // sptSet, there is an edge from u // to v, and total weight of path // from src to v through u is smaller // than current value of dist[v] if (!sptSet[v] && graph[u][v] != 0 && dist[u] != Number.MAX_VALUE && dist[u] + graph[u][v] < dist[v]) { dist[v] = dist[u] + graph[u][v]; } } } // Print the constructed distance array printSolution(dist); } // Driver code let graph = [ [ 0, 4, 0, 0, 0, 0, 0, 8, 0 ], [ 4, 0, 8, 0, 0, 0, 0, 11, 0 ], [ 0, 8, 0, 7, 0, 4, 0, 0, 2 ], [ 0, 0, 7, 0, 9, 14, 0, 0, 0], [ 0, 0, 0, 9, 0, 10, 0, 0, 0 ], [ 0, 0, 4, 14, 10, 0, 2, 0, 0], [ 0, 0, 0, 0, 0, 2, 0, 1, 6 ], [ 8, 11, 0, 0, 0, 0, 1, 0, 7 ], [ 0, 0, 2, 0, 0, 0, 6, 7, 0 ] ] dijkstra(graph, 0); // This code is contributed by rag2127>
Výkon
Vertex Distance from Source 0 0 1 4 2 12 3 19 4 21 5 11 6 9 7 8 8 14>
Časová zložitosť: O(V2)
Pomocný priestor: O(V)
Poznámky:
- Kód vypočíta najkratšiu vzdialenosť, ale nevypočíta informácie o ceste. Vytvorte rodičovské pole, aktualizujte rodičovské pole po aktualizácii vzdialenosti a použite ho na zobrazenie najkratšej cesty od zdroja k rôznym vrcholom.
- Časová náročnosť realizácie je O(V 2 ) . Ak je vstup graf je znázornený pomocou zoznamu susedstiev , možno ho pomocou binárnej haldy redukovať na O(E * log V). Prosím pozri Dijkstrov algoritmus na reprezentáciu zoznamu susedných vzťahov pre viac detailov.
- Dijkstrov algoritmus nefunguje pre grafy so zápornými cyklami hmotnosti.
Prečo Dijkstrove algoritmy zlyhávajú pre grafy so zápornými okrajmi?
Problém so zápornými váhami vyplýva zo skutočnosti, že Dijkstrov algoritmus predpokladá, že po pridaní uzla do množiny navštívených uzlov je jeho vzdialenosť finalizovaná a nezmení sa. Avšak v prítomnosti záporných váh môže tento predpoklad viesť k nesprávnym výsledkom.
Zvážte nasledujúci graf ako príklad:

Vo vyššie uvedenom grafe je A zdrojový uzol medzi hranami A do B a A do C , A do B je menšia hmotnosť a Dijkstra priraďuje najkratšiu vzdialenosť B ako 2, ale z dôvodu existencie zápornej hrany z C do B , skutočná najkratšia vzdialenosť sa zníži na 1, ktorú Dijkstra nedokáže zistiť.
Poznámka: Používame Algoritmus najkratšej cesty Bellmana Forda v prípade, že máme v grafe záporné hrany.
Použitie Dijkstrovho algoritmu Zoznam susedstva v O(E logV):
Pre Dijkstrov algoritmus sa vždy odporúča použiť Vždy, keď sa vzdialenosť vrcholu zníži, pridáme ďalšiu inštanciu vrcholu do priority_queue. Aj keď existuje viacero inštancií, berieme do úvahy len inštanciu s minimálnou vzdialenosťou a ostatné inštancie ignorujeme.
Časová zložitosť zostáva O(E * LogV) pretože v prioritnom rade bude najviac vrcholov O(E) a O(logE) je to isté ako O(logV)
Nižšie je uvedená implementácia vyššie uvedeného prístupu:
C++ // C++ Program to find Dijkstra's shortest path using // priority_queue in STL #include using namespace std; #define INF 0x3f3f3f3f // iPair ==>Integer Pair typedef pair iPair; // Táto trieda predstavuje orientovaný graf pomocou // triedy reprezentácie zoznamu susediacich Graph { int V; // Počet vrcholov // Vo váženom grafe musíme uložiť vrchol // a pár váh pre každý zoznam hrán>* adj; verejné: Graf(int V); // Konštruktor // funkcia na pridanie hrany do grafu void addEdge(int u, int v, int w); // vypíše najkratšiu cestu z s void shortestPath(int s); }; // Alokuje pamäť pre zoznam susediacich Graph::Graph(int V) { this->V = V; adj = nový zoznam [V]; } void Graph::addEdge(int u, int v, int w) { adj[u].push_back(make_pair(v, w)); adj[v].push_back(make_pair(u, w)); } // Vypíše najkratšie cesty z src do všetkých ostatných vrcholov void Graph::shortestPath(int src) { // Vytvorenie prioritného frontu na ukladanie vrcholov, ktoré // sa predspracujú. Toto je zvláštna syntax v C++. // Podrobnosti o tejto syntaxi nájdete na nižšie uvedenom odkaze // https://www.techcodeview.com priority_queue , väčší > pq; // Vytvorte vektor pre vzdialenosti a inicializujte všetky // vzdialenosti ako nekonečný (INF) vektor dist(V, INF); // Vložte samotný zdroj do prioritného frontu a inicializujte // jeho vzdialenosť ako 0. pq.push(make_pair(0, src)); dist[src] = 0; /* Opakuje sa, kým sa prioritný front nevyprázdni (alebo všetky vzdialenosti nie sú dokončené) */ while (!pq.empty()) { // Prvý vrchol v páre je minimálna vzdialenosť // vrchol, extrahujte ho z prioritného frontu. // označenie vrcholu je uložené v sekunde z páru (musí sa to urobiť // týmto spôsobom, aby sa zachovali vrcholy // zoradená vzdialenosť (vzdialenosť musí byť prvá položka // v páre) int u = pq.top().second; pq.pop(); // 'i' sa používa na získanie všetkých susedných vrcholov // zoznamu vrcholov>::iterátor i; for (i = adj[u].begin(); i != adj[u].end(); ++i) { // Získanie označenia vrcholu a váhy aktuálneho // susediaceho s u. int v = (*i).prvý; int váha = (*i).sekunda; // Ak existuje skrátená cesta k v cez u. if (dist[v]> dist[u] + hmotnosť) { // Aktualizácia vzdialenosti v dist[v] = dist[u] + hmotnosť; pq.push(make_pair(dist[v], v)); } } } // Tlač najkratších vzdialeností uložených v dist[] printf('Vzdialenosť vrcholu od zdroja
'); pre (int i = 0; i< V; ++i) printf('%d %d
', i, dist[i]); } // Driver's code int main() { // create the graph given in above figure int V = 9; Graph g(V); // making above shown graph g.addEdge(0, 1, 4); g.addEdge(0, 7, 8); g.addEdge(1, 2, 8); g.addEdge(1, 7, 11); g.addEdge(2, 3, 7); g.addEdge(2, 8, 2); g.addEdge(2, 5, 4); g.addEdge(3, 4, 9); g.addEdge(3, 5, 14); g.addEdge(4, 5, 10); g.addEdge(5, 6, 2); g.addEdge(6, 7, 1); g.addEdge(6, 8, 6); g.addEdge(7, 8, 7); // Function call g.shortestPath(0); return 0; }>
Java import java.util.*; class Graph { private int V; private List> adj; Graph(int V) { this.V = V; adj = new ArrayList(); pre (int i = 0; i< V; i++) { adj.add(new ArrayList()); } } void addEdge(int u, int v, int w) { adj.get(u).add(new iPair(v, w)); adj.get(v).add(new iPair(u, w)); } void shortestPath(int src) { PriorityQueue pq = new PriorityQueue(V, Comparator.comparingInt(o -> o.second)); int[] dist = nový int[V]; Arrays.fill(dist, Integer.MAX_VALUE); pq.add(new iPair(0, src)); dist[src] = 0; while (!pq.isEmpty()) { int u = pq.poll().second; for (iPair v : adj.get(u)) { if (dist[v.first]> dist[u] + v.second) { dist[v.first] = dist[u] + v.second; pq.add(new iPair(dist[v.first], v.first)); } } } System.out.println('Vzdialenosť vrcholu od zdroja'); pre (int i = 0; i< V; i++) { System.out.println(i + ' ' + dist[i]); } } static class iPair { int first, second; iPair(int first, int second) { this.first = first; this.second = second; } } } public class Main { public static void main(String[] args) { int V = 9; Graph g = new Graph(V); g.addEdge(0, 1, 4); g.addEdge(0, 7, 8); g.addEdge(1, 2, 8); g.addEdge(1, 7, 11); g.addEdge(2, 3, 7); g.addEdge(2, 8, 2); g.addEdge(2, 5, 4); g.addEdge(3, 4, 9); g.addEdge(3, 5, 14); g.addEdge(4, 5, 10); g.addEdge(5, 6, 2); g.addEdge(6, 7, 1); g.addEdge(6, 8, 6); g.addEdge(7, 8, 7); g.shortestPath(0); } }>
Python import heapq # iPair ==>Celočíselný pár iPair = n-tica # Táto trieda predstavuje orientovaný graf pomocou # triedy reprezentácie zoznamu susednosti Graf: def __init__(self, V: int): # Konštruktor self.V = V self.adj = [[] for _ in range(V )] def addEdge(self, u: int, v: int, w: int): self.adj[u].append((v, w)) self.adj[v].append((u, w)) # Vytlačí najkratšie cesty z src do všetkých ostatných vrcholov def shortestPath(self, src: int): # Vytvorte prioritný front na uloženie vrcholov, ktoré # sa predspracujú pq = [] heapq.heappush(pq, (0, src)) # Vytvorte vektor pre vzdialenosti a inicializujte všetky # vzdialenosti ako nekonečné (INF) dist = [float('inf')] * self.V dist[src] = 0 pričom pq: # Prvý vrchol v páre je minimálna vzdialenosť # vertex, extrahujte ho z prioritného frontu. # vertex label je uložený v sekunde páru d, u = heapq.heappop(pq) # 'i' sa používa na získanie všetkých susedných vrcholov # vrcholu pre v, váhu v self.adj[u]: # If je tam skrátená cesta do v cez u. if dist[v]> dist[u] + hmotnosť: # Aktualizácia vzdialenosti v dist[v] = dist[u] + hmotnosť heapq.heappush(pq, (dist[v], v)) # Tlačiť najkratšie vzdialenosti uložené v dist[] for i in range(self.V): print(f'{i} {dist[i]}') # Kód vodiča, ak __name__ == '__main__': # vytvorte graf uvedený na obrázku vyššie V = 9 g = Graph(V) # vytvorte vyššie uvedený graf g.addEdge(0, 1, 4) g.addEdge(0, 7, 8) g.addEdge(1, 2, 8) g.addEdge(1, 7, 11) g.addEdge(2, 3, 7) g.addEdge(2, 8, 2) g.addEdge(2, 5, 4) g.addEdge(3, 4, 9) g.addEdge(3, 5, 14) g.addEdge(4, 5, 10) g.addEdge(5, 6, 2) g.addEdge(6, 7, 1) g.addEdge(6, 8, 6) g.addEdge(7, 8, 7) g.shortestPath(0)>
C# using System; using System.Collections.Generic; // This class represents a directed graph using // adjacency list representation public class Graph { private const int INF = 2147483647; private int V; private List [] adj; public Graf(int V) { // Počet vrcholov this.V = V; // Vo váženom grafe musíme uložiť vrchol // a pár váh pre každú hranu this.adj = new List [V]; pre (int i = 0; i< V; i++) { this.adj[i] = new List (); } } public void AddEdge(int u, int v, int w) { this.adj[u].Add(new int[] { v, w }); this.adj[v].Add(new int[] { u, w }); } // Vypíše najkratšie cesty z src do všetkých ostatných vrcholov public void ShortestPath(int src) { // Vytvorenie prioritného frontu na ukladanie vrcholov, ktoré // sú predspracované. SortedSet pq = new SortedSet (nový DistanceComparer()); // Vytvorte pole pre vzdialenosti a inicializujte všetky // vzdialenosti ako nekonečné (INF) int[] dist = new int[V]; pre (int i = 0; i< V; i++) { dist[i] = INF; } // Insert source itself in priority queue and initialize // its distance as 0. pq.Add(new int[] { 0, src }); dist[src] = 0; /* Looping till priority queue becomes empty (or all distances are not finalized) */ while (pq.Count>0) { // Prvý vrchol v páre je minimálna vzdialenosť // vrchol, extrahujte ho z prioritného frontu. // štítok vrcholu je uložený v sekunde z páru (// treba to urobiť týmto spôsobom, aby sa vrcholy // zoradili podľa vzdialenosti) int[] minDistVertex = pq.Min; pq.Remove(minDistVertex); int u = minDistVertex[1]; // 'i' sa používa na získanie všetkých susedných vrcholov // vrcholu foreach (int[] adjVertex v tomto.adj[u]) { // Získanie označenia vrcholu a váhy aktuálneho // susediaceho s u. int v = adjVertex[0]; int váha = adjVertex[1]; // Ak existuje kratšia cesta k v cez u. if (dist[v]> dist[u] + hmotnosť) { // Aktualizácia vzdialenosti v dist[v] = dist[u] + hmotnosť; pq.Add(new int[] { dist[v], v }); } } } // Tlač najkratších vzdialeností uložených v dist[] Console.WriteLine('Vzdialenosť vrcholu od zdroja'); pre (int i = 0; i< V; ++i) Console.WriteLine(i + ' ' + dist[i]); } private class DistanceComparer : IComparer { public int Porovnaj(int[] x, int[] y) { if (x[0] == y[0]) { return x[1] - y[1]; } return x[0] - y[0]; } } } public class Program { // Kód ovládača public static void Main() { // vytvorte graf uvedený na obrázku vyššie int V = 9; Graph g = new Graph(V); // vytvorenie vyššie uvedeného grafu g.AddEdge(0, 1, 4); g.AddEdge(0, 7, 8); g.AddEdge(1, 2, 8); g.AddEdge(1, 7, 11); g.AddEdge(2, 3, 7); g.AddEdge(2, 8, 2); g.AddEdge(2, 5, 4); g.AddEdge(3, 4, 9); g.AddEdge(3, 5, 14); g.AddEdge(4, 5, 10); g.AddEdge(5, 6, 2); g.AddEdge(6, 7, 1); g.AddEdge(6, 8, 6); g.AddEdge(7, 8, 7); g.ShortestPath(0); } } // tento kód prispel bhardwajji>
Javascript // javascript Program to find Dijkstra's shortest path using // priority_queue in STL const INF = 2147483647; // This class represents a directed graph using // adjacency list representation class Graph { constructor(V){ // No. of vertices this.V = V; // In a weighted graph, we need to store vertex // and weight pair for every edge this.adj = new Array(V); for(let i = 0; i < V; i++){ this.adj[i] = new Array(); } } addEdge(u, v, w) { this.adj[u].push([v, w]); this.adj[v].push([u, w]); } // Prints shortest paths from src to all other vertices shortestPath(src) { // Create a priority queue to store vertices that // are being preprocessed. This is weird syntax in C++. // Refer below link for details of this syntax // https://www.techcodeview.com let pq = []; // Create a vector for distances and initialize all // distances as infinite (INF) let dist = new Array(V).fill(INF); // Insert source itself in priority queue and initialize // its distance as 0. pq.push([0, src]); dist[src] = 0; /* Looping till priority queue becomes empty (or all distances are not finalized) */ while (pq.length>0) { // Prvý vrchol v páre je minimálna vzdialenosť // vrchol, extrahujte ho z prioritného frontu. // štítok vrcholu je uložený v druhom z páru (to // treba urobiť týmto spôsobom, aby sa zachovali vrcholy // zoradená vzdialenosť (vzdialenosť musí byť prvá položka // v páre) nech u = pq[0][1]; pq.shift() // 'i' sa používa na získanie všetkých susedných vrcholov // vrcholu for(nech i = 0; i);< this.adj[u].length; i++){ // Get vertex label and weight of current // adjacent of u. let v = this.adj[u][i][0]; let weight = this.adj[u][i][1]; // If there is shorted path to v through u. if (dist[v]>dist[u] + hmotnosť) { // Aktualizácia vzdialenosti v dist[v] = dist[u] + hmotnosť; pq.push([dist[v], v]); pq.sort((a, b) =>{ if(a[0] == b[0]) return a[1] - b[1]; return a[0] - b[0]; }); } } } // Tlač najkratších vzdialeností uložených v dist[] console.log('Vzdialenosť vrcholu od zdroja'); pre (nech i = 0; i< V; ++i) console.log(i, ' ', dist[i]); } } // Driver's code // create the graph given in above figure let V = 9; let g = new Graph(V); // making above shown graph g.addEdge(0, 1, 4); g.addEdge(0, 7, 8); g.addEdge(1, 2, 8); g.addEdge(1, 7, 11); g.addEdge(2, 3, 7); g.addEdge(2, 8, 2); g.addEdge(2, 5, 4); g.addEdge(3, 4, 9); g.addEdge(3, 5, 14); g.addEdge(4, 5, 10); g.addEdge(5, 6, 2); g.addEdge(6, 7, 1); g.addEdge(6, 8, 6); g.addEdge(7, 8, 7); // Function call g.shortestPath(0); // The code is contributed by Nidhi goel.>
Výkon
Vertex Distance from Source 0 0 1 4 2 12 3 19 4 21 5 11 6 9 7 8 8 14>
Časová zložitosť: O(E * logV), kde E je počet hrán a V je počet vrcholov.
Pomocný priestor: O(V)
top 10 hentai
Aplikácie Dijkstrovho algoritmu:
- Google Mapy používa Dijkstrov algoritmus na zobrazenie najkratšej vzdialenosti medzi zdrojom a cieľom.
- In počítačové siete , Dijkstrov algoritmus tvorí základ pre rôzne smerovacie protokoly, ako napríklad OSPF (Open Shortest Path First) a IS-IS (Intermediate System to Intermediate System).
- Dopravné a dopravné systémy využívajú Dijkstrov algoritmus na optimalizáciu dopravného toku, minimalizáciu zápch a plánovanie najefektívnejších trás pre vozidlá.
- Letecké spoločnosti používajú Dijkstrov algoritmus na plánovanie letových trás, ktoré minimalizujú spotrebu paliva a skracujú čas cesty.
- Dijkstrov algoritmus sa používa v automatizácii elektronického dizajnu na smerovanie pripojení na integrovaných obvodoch a čipoch veľmi veľkej integrácie (VLSI).
Podrobnejšie vysvetlenie nájdete v tomto článku Dijkstrov algoritmus najkratšej cesty pomocou priority_queue STL .