{"id":17705,"date":"2023-08-25T06:33:04","date_gmt":"2023-08-25T06:33:04","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=17705"},"modified":"2024-02-08T05:47:05","modified_gmt":"2024-02-08T05:47:05","slug":"dijkstras-algorithm","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/dijkstras-algorithm\/","title":{"rendered":"Dijkstra\u2019s algorithm"},"content":{"rendered":"

\"\"<\/p>\n

Dijkstra’s algorithm, named after Dutch computer scientist Edsger W. Dijkstra, is a fundamental algorithm used in graph theory and computer science for finding the shortest path between nodes in a graph with non-negative edge weights. Originally designed to solve the single-source shortest path problem, Dijkstra’s algorithm efficiently determines the shortest path from a designated starting node to all other nodes in the graph. Its simplicity and effectiveness make it a widely used tool in various applications, including network routing protocols, transportation networks, and data processing systems.<\/p>\n

How Dijkstra algorithm Work?<\/h2>\n

The algorithm works by maintaining a set of vertices that have already been visited, and a set of vertices that have not yet been visited. The algorithm starts at the source vertex and adds it to the set of visited vertices. Then, it repeatedly finds the vertex in the set of unvisited vertices that has the shortest known path to the source vertex, and adds that vertex to the set of visited vertices. This process continues until all vertices have been visited.
\n\"\"<\/p>\n

The Dijkstra algorithm is a greedy algorithm, which means that it makes the best possible choice at each step, without considering the future consequences of its decisions. In the case of Dijkstra algorithm, the best possible choice is to add the vertex with the shortest known path to the source vertex to the set of visited vertices.<\/p>\n

The Dijkstra algorithm is a very efficient algorithm for finding the shortest paths in a graph. Its time complexity is O(V log V), where V is the number of vertices in the graph.<\/p>\n

Example of Dijkstra algorithm<\/h2>\n

Here is an example of Dijkstra algorithm that is discussed below.<\/p>\n

Step 1 :<\/strong> Start with a weighted graph.
\n\"\"<\/p>\n

Step 2 :<\/strong> Choose a starting vertex and assign infinity path values to all other devices.
\n\"\"<\/p>\n

Step 3 :<\/strong> Go to each vertex and update its path length.
\n\"\"<\/p>\n

Step 4 :<\/strong> If the path length of the adjacent vertex is less than new path length, don’t update it.
\n\"\"<\/p>\n

Step 5 :<\/strong> Avoid updating path lengths of already visited vertices.
\n\"\"<\/p>\n

Step 6 :<\/strong> After each iteration, we pick the unvisited vertex with the least path length. So we choose 5.
\n\"\"<\/p>\n

Step 7 :<\/strong> Notice how the rightmost vertex has its path length updated twice.
\n\"\"<\/p>\n

Step 8 :<\/strong> Repeat until all the vertices have been visited.
\n\"\"<\/p>\n

Pseudocode for Dijkstra algorithm<\/h2>\n

The following is a pseudocode for Dijkstra algorithm:<\/p>\n

procedure Dijkstra(G, s)\n    for each vertex v in G\n        dist[v] := infinity\n        prev[v] := nil\n    dist[s] := 0\n    Q := {s}\n    while Q is not empty\n        u := vertex in Q with minimum dist[u]\n        remove u from Q\n        for each vertex v adjacent to u\n            if dist[v] > dist[u] + weight(u, v)\n                dist[v] := dist[u] + weight(u, v)\n                prev[v] := u<\/code><\/pre>\n
In this pseudocode, G<\/code> is the graph, s<\/code> is the source vertex, dist[v]<\/code> is the shortest known path from s<\/code> to vertex v<\/code>, and prev[v]<\/code> is the predecessor of vertex v<\/code> in the shortest path from s<\/code> to v<\/code>.<\/p>\n
Code Implementation of Dijkstra algorithm<\/h2>\n
Here is a code implementation of the Dijkstra algorithm in C++.<\/p>\n\t\t\t\t\t\t