„Dijkstra“ algoritmas leidžia mums rasti trumpiausią kelią tarp bet kokių dviejų grafiko viršūnių.
Jis skiriasi nuo minimalaus tarpatramio medžio, nes trumpiausias atstumas tarp dviejų viršūnių gali neapimti visų grafiko viršūnių.
Kaip veikia Dijkstros algoritmas
Dijkstros algoritmas veikia tuo pagrindu, kad bet B -> Dkuris trumpiausio kelio A -> Dtarp viršūnių A ir D potipis yra ir trumpiausias kelias tarp B ir D viršūnių.
Kiekvienas potipis yra trumpiausias kelias
Djikstra naudojo šią savybę priešinga kryptimi, ty mes pervertiname kiekvienos viršūnės atstumą nuo pradinės viršūnės. Tada aplankome kiekvieną mazgą ir jo kaimynus, kad rastume trumpiausią potinkį tiems kaimynams.
Algoritmas naudoja godų požiūrį ta prasme, kad randame kitą geriausią sprendimą tikėdamiesi, kad galutinis rezultatas yra geriausias visos problemos sprendimas.
Dijkstros algoritmo pavyzdys
Lengviau pradėti nuo pavyzdžio ir tada pagalvoti apie algoritmą.
Pradėkite nuo svertinio grafiko 
Pasirinkite pradinę viršūnę ir priskirkite begalybės kelio vertes visiems kitiems įrenginiams 
Eikite į kiekvieną viršūnę ir atnaujinkite jos kelio ilgį 
Jei gretimos viršūnės kelio ilgis yra mažesnis nei naujo kelio ilgis, 
neatnaujinkite jau aplankytų viršūnių ilgiai 
Po kiekvienos iteracijos mes pasirenkame mažiausiai kelio ilgio neaplankytą viršūnę. Taigi mes pasirenkame 5 prieš 7. 
Atkreipkite dėmesį, kaip dešiniosios viršūnės kelio ilgis atnaujinamas du kartus. 
Pakartokite, kol bus aplankytos visos viršūnės
Džikstra algoritmo pseudokodas
Turime išlaikyti kiekvienos viršūnės kelio atstumą. Mes galime tai laikyti v dydžio masyve, kur v yra viršūnių skaičius.
Mes taip pat norime, kad būtų galima pasiekti trumpiausią kelią, ne tik žinoti trumpiausio kelio ilgį. Tam mes susiejame kiekvieną viršūnę su viršūne, kuri paskutinį kartą atnaujino savo kelio ilgį.
Pasibaigus algoritmui, galime grįžti iš paskirties viršūnės į šaltinio viršūnę, kad rastume kelią.
Norint efektyviai priimti viršūnę su mažiausiu kelio atstumu, galima naudoti minimalaus prioriteto eilę.
function dijkstra(G, S) for each vertex V in G distance(V) <- infinite previous(V) <- NULL If V != S, add V to Priority Queue Q distance(S) <- 0 while Q IS NOT EMPTY U <- Extract MIN from Q for each unvisited neighbour V of U tempDistance <- distance(U) + edge_weight(U, V) if tempDistance < distance(V) distance(V) <- tempDistance previous(V) <- U return distance(), previous()
„Dijkstra“ algoritmo kodas
Dijkstros algoritmo įgyvendinimas C ++ yra pateiktas žemiau. Kodo sudėtingumą galima pagerinti, tačiau abstrakcijas patogu susieti kodą su algoritmu.
„Python Java C C ++“ # Dijkstra's Algorithm in Python import sys # Providing the graph vertices = ((0, 0, 1, 1, 0, 0, 0), (0, 0, 1, 0, 0, 1, 0), (1, 1, 0, 1, 1, 0, 0), (1, 0, 1, 0, 0, 0, 1), (0, 0, 1, 0, 0, 1, 0), (0, 1, 0, 0, 1, 0, 1), (0, 0, 0, 1, 0, 1, 0)) edges = ((0, 0, 1, 2, 0, 0, 0), (0, 0, 2, 0, 0, 3, 0), (1, 2, 0, 1, 3, 0, 0), (2, 0, 1, 0, 0, 0, 1), (0, 0, 3, 0, 0, 2, 0), (0, 3, 0, 0, 2, 0, 1), (0, 0, 0, 1, 0, 1, 0)) # Find which vertex is to be visited next def to_be_visited(): global visited_and_distance v = -10 for index in range(num_of_vertices): if visited_and_distance(index)(0) == 0 and (v < 0 or visited_and_distance(index)(1) <= visited_and_distance(v)(1)): v = index return v num_of_vertices = len(vertices(0)) visited_and_distance = ((0, 0)) for i in range(num_of_vertices-1): visited_and_distance.append((0, sys.maxsize)) for vertex in range(num_of_vertices): # Find next vertex to be visited to_visit = to_be_visited() for neighbor_index in range(num_of_vertices): # Updating new distances if vertices(to_visit)(neighbor_index) == 1 and visited_and_distance(neighbor_index)(0) == 0: new_distance = visited_and_distance(to_visit)(1) + edges(to_visit)(neighbor_index) if visited_and_distance(neighbor_index)(1)> new_distance: visited_and_distance(neighbor_index)(1) = new_distance visited_and_distance(to_visit)(0) = 1 i = 0 # Printing the distance for distance in visited_and_distance: print("Distance of ", chr(ord('a') + i), " from source vertex: ", distance(1)) i = i + 1
// Dijkstra's Algorithm in Java public class Dijkstra ( public static void dijkstra(int()() graph, int source) ( int count = graph.length; boolean() visitedVertex = new boolean(count); int() distance = new int(count); for (int i = 0; i < count; i++) ( visitedVertex(i) = false; distance(i) = Integer.MAX_VALUE; ) // Distance of self loop is zero distance(source) = 0; for (int i = 0; i < count; i++) ( // Update the distance between neighbouring vertex and source vertex int u = findMinDistance(distance, visitedVertex); visitedVertex(u) = true; // Update all the neighbouring vertex distances for (int v = 0; v < count; v++) ( if (!visitedVertex(v) && graph(u)(v) != 0 && (distance(u) + graph(u)(v) < distance(v))) ( distance(v) = distance(u) + graph(u)(v); ) ) ) for (int i = 0; i < distance.length; i++) ( System.out.println(String.format("Distance from %s to %s is %s", source, i, distance(i))); ) ) // Finding the minimum distance private static int findMinDistance(int() distance, boolean() visitedVertex) ( int minDistance = Integer.MAX_VALUE; int minDistanceVertex = -1; for (int i = 0; i < distance.length; i++) ( if (!visitedVertex(i) && distance(i) < minDistance) ( minDistance = distance(i); minDistanceVertex = i; ) ) return minDistanceVertex; ) public static void main(String() args) ( int graph()() = new int()() ( ( 0, 0, 1, 2, 0, 0, 0 ), ( 0, 0, 2, 0, 0, 3, 0 ), ( 1, 2, 0, 1, 3, 0, 0 ), ( 2, 0, 1, 0, 0, 0, 1 ), ( 0, 0, 3, 0, 0, 2, 0 ), ( 0, 3, 0, 0, 2, 0, 1 ), ( 0, 0, 0, 1, 0, 1, 0 ) ); Dijkstra T = new Dijkstra(); T.dijkstra(graph, 0); ) )
// Dijkstra's Algorithm in C #include #define INFINITY 9999 #define MAX 10 void Dijkstra(int Graph(MAX)(MAX), int n, int start); void Dijkstra(int Graph(MAX)(MAX), int n, int start) ( int cost(MAX)(MAX), distance(MAX), pred(MAX); int visited(MAX), count, mindistance, nextnode, i, j; // Creating cost matrix for (i = 0; i < n; i++) for (j = 0; j < n; j++) if (Graph(i)(j) == 0) cost(i)(j) = INFINITY; else cost(i)(j) = Graph(i)(j); for (i = 0; i < n; i++) ( distance(i) = cost(start)(i); pred(i) = start; visited(i) = 0; ) distance(start) = 0; visited(start) = 1; count = 1; while (count < n - 1) ( mindistance = INFINITY; for (i = 0; i < n; i++) if (distance(i) < mindistance && !visited(i)) ( mindistance = distance(i); nextnode = i; ) visited(nextnode) = 1; for (i = 0; i < n; i++) if (!visited(i)) if (mindistance + cost(nextnode)(i) < distance(i)) ( distance(i) = mindistance + cost(nextnode)(i); pred(i) = nextnode; ) count++; ) // Printing the distance for (i = 0; i < n; i++) if (i != start) ( printf("Distance from source to %d: %d", i, distance(i)); ) ) int main() ( int Graph(MAX)(MAX), i, j, n, u; n = 7; Graph(0)(0) = 0; Graph(0)(1) = 0; Graph(0)(2) = 1; Graph(0)(3) = 2; Graph(0)(4) = 0; Graph(0)(5) = 0; Graph(0)(6) = 0; Graph(1)(0) = 0; Graph(1)(1) = 0; Graph(1)(2) = 2; Graph(1)(3) = 0; Graph(1)(4) = 0; Graph(1)(5) = 3; Graph(1)(6) = 0; Graph(2)(0) = 1; Graph(2)(1) = 2; Graph(2)(2) = 0; Graph(2)(3) = 1; Graph(2)(4) = 3; Graph(2)(5) = 0; Graph(2)(6) = 0; Graph(3)(0) = 2; Graph(3)(1) = 0; Graph(3)(2) = 1; Graph(3)(3) = 0; Graph(3)(4) = 0; Graph(3)(5) = 0; Graph(3)(6) = 1; Graph(4)(0) = 0; Graph(4)(1) = 0; Graph(4)(2) = 3; Graph(4)(3) = 0; Graph(4)(4) = 0; Graph(4)(5) = 2; Graph(4)(6) = 0; Graph(5)(0) = 0; Graph(5)(1) = 3; Graph(5)(2) = 0; Graph(5)(3) = 0; Graph(5)(4) = 2; Graph(5)(5) = 0; Graph(5)(6) = 1; Graph(6)(0) = 0; Graph(6)(1) = 0; Graph(6)(2) = 0; Graph(6)(3) = 1; Graph(6)(4) = 0; Graph(6)(5) = 1; Graph(6)(6) = 0; u = 0; Dijkstra(Graph, n, u); return 0; )
// Dijkstra's Algorithm in C++ #include #include #define INT_MAX 10000000 using namespace std; void DijkstrasTest(); int main() ( DijkstrasTest(); return 0; ) class Node; class Edge; void Dijkstras(); vector* AdjacentRemainingNodes(Node* node); Node* ExtractSmallest(vector& nodes); int Distance(Node* node1, Node* node2); bool Contains(vector& nodes, Node* node); void PrintShortestRouteTo(Node* destination); vector nodes; vector edges; class Node ( public: Node(char id) : id(id), previous(NULL), distanceFromStart(INT_MAX) ( nodes.push_back(this); ) public: char id; Node* previous; int distanceFromStart; ); class Edge ( public: Edge(Node* node1, Node* node2, int distance) : node1(node1), node2(node2), distance(distance) ( edges.push_back(this); ) bool Connects(Node* node1, Node* node2) ( return ( (node1 == this->node1 && node2 == this->node2) || (node1 == this->node2 && node2 == this->node1)); ) public: Node* node1; Node* node2; int distance; ); /////////////////// void DijkstrasTest() ( Node* a = new Node('a'); Node* b = new Node('b'); Node* c = new Node('c'); Node* d = new Node('d'); Node* e = new Node('e'); Node* f = new Node('f'); Node* g = new Node('g'); Edge* e1 = new Edge(a, c, 1); Edge* e2 = new Edge(a, d, 2); Edge* e3 = new Edge(b, c, 2); Edge* e4 = new Edge(c, d, 1); Edge* e5 = new Edge(b, f, 3); Edge* e6 = new Edge(c, e, 3); Edge* e7 = new Edge(e, f, 2); Edge* e8 = new Edge(d, g, 1); Edge* e9 = new Edge(g, f, 1); a->distanceFromStart = 0; // set start node Dijkstras(); PrintShortestRouteTo(f); ) /////////////////// void Dijkstras() ( while (nodes.size()> 0) ( Node* smallest = ExtractSmallest(nodes); vector* adjacentNodes = AdjacentRemainingNodes(smallest); const int size = adjacentNodes->size(); for (int i = 0; i at(i); int distance = Distance(smallest, adjacent) + smallest->distanceFromStart; if (distance distanceFromStart) ( adjacent->distanceFromStart = distance; adjacent->previous = smallest; ) ) delete adjacentNodes; ) ) // Find the node with the smallest distance, // remove it, and return it. Node* ExtractSmallest(vector& nodes) ( int size = nodes.size(); if (size == 0) return NULL; int smallestPosition = 0; Node* smallest = nodes.at(0); for (int i = 1; i distanceFromStart distanceFromStart) ( smallest = current; smallestPosition = i; ) ) nodes.erase(nodes.begin() + smallestPosition); return smallest; ) // Return all nodes adjacent to 'node' which are still // in the 'nodes' collection. vector* AdjacentRemainingNodes(Node* node) ( vector* adjacentNodes = new vector(); const int size = edges.size(); for (int i = 0; i node1 == node) ( adjacent = edge->node2; ) else if (edge->node2 == node) ( adjacent = edge->node1; ) if (adjacent && Contains(nodes, adjacent)) ( adjacentNodes->push_back(adjacent); ) ) return adjacentNodes; ) // Return distance between two connected nodes int Distance(Node* node1, Node* node2) ( const int size = edges.size(); for (int i = 0; i Connects(node1, node2)) ( return edge->distance; ) ) return -1; // should never happen ) // Does the 'nodes' vector contain 'node' bool Contains(vector& nodes, Node* node) ( const int size = nodes.size(); for (int i = 0; i < size; ++i) ( if (node == nodes.at(i)) ( return true; ) ) return false; ) /////////////////// void PrintShortestRouteTo(Node* destination) ( Node* previous = destination; cout << "Distance from start: " id
node2 == node) ( cout << "adjacent: " id
Dijkstra's Algorithm Complexity
Time Complexity: O(E Log V)
where, E is the number of edges and V is the number of vertices.
Space Complexity: O(V)
Dijkstra's Algorithm Applications
- To find the shortest path
- In social networking applications
- In a telephone network
- To find the locations in the map
