Algoritma Dijkstra membolehkan kita mencari jalan terpendek antara dua bucu graf.
Ia berbeza dengan pokok rentang minimum kerana jarak terpendek antara dua bucu mungkin tidak termasuk semua bucu grafik.
Bagaimana Algoritma Dijkstra berfungsi
Algoritma Dijkstra berfungsi berdasarkan bahawa setiap subpath B -> Ddari jalan terpendek A -> Dantara bucu A dan D juga merupakan jalan terpendek antara bucu B dan D.
Setiap subpath adalah jalan terpendek
Djikstra menggunakan harta ini pada arah yang bertentangan iaitu kita melebih-lebihkan jarak setiap bucu dari bucu permulaan. Kemudian kami melawat setiap simpul dan jirannya untuk mencari jalan kecil terpendek ke jiran tersebut.
Algoritma menggunakan pendekatan tamak dalam arti bahawa kita mencari penyelesaian terbaik seterusnya dengan harapan bahawa hasil akhirnya adalah penyelesaian terbaik untuk keseluruhan masalah.
Contoh algoritma Dijkstra
Lebih mudah untuk memulakan dengan contoh dan kemudian memikirkan algoritma.
Mulakan dengan graf berwajaran 
Pilih titik permulaan dan tetapkan nilai jalur tak terhingga ke semua peranti lain 
Pergi ke setiap bucu dan kemas kini panjang lintasannya 
Jika panjang lintasan bucu bersebelahan lebih rendah daripada panjang lintasan baru, jangan kemas kini 
Elakkan mengemas kini laluan panjang bucu yang sudah dikunjungi 
Selepas setiap lelaran, kami memilih bucu yang tidak dilawati dengan panjang lintasan paling sedikit. Oleh itu, kita memilih 5 sebelum 7 
Perhatikan bagaimana puncak paling kanan mempunyai panjang lintasannya dikemas kini dua kali 
Ulangi sehingga semua bucu telah dikunjungi
Pseudocode algoritma Djikstra
Kita perlu mengekalkan jarak laluan setiap bucu. Kita boleh menyimpannya dalam pelbagai ukuran v, di mana v adalah bilangan bucu.
Kami juga ingin mendapatkan jalan terpendek, bukan hanya mengetahui panjang jalan terpendek. Untuk ini, kami memetakan setiap bucu ke bucu yang terakhir mengemas kini panjang lintasannya.
Setelah algoritma selesai, kita dapat mundur dari titik tujuan ke bucu sumber untuk mencari jalan.
Baris keutamaan minimum dapat digunakan untuk menerima bucu dengan cekap dengan jarak jalan paling sedikit.
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()
Kod untuk Algoritma Dijkstra
Pelaksanaan Algoritma Dijkstra dalam C ++ diberikan di bawah. Kerumitan kod dapat diperbaiki, tetapi abstraksi adalah mudah untuk mengaitkan kod dengan algoritma.
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
