Dijkstra's Algorithm

Overview

Dijkstra's Algorithm is a popular algorithm in computer science for finding the shortest path between nodes in a graph. It is widely used in network routing and geographical mapping systems.

Key Features

• Efficient for graphs with non-negative edge weights.
• Utilizes a greedy approach to determine the shortest path.

Algorithm Steps

1. The very first step is to mark all nodes as unvisited
2. Mark the picked starting node with a current distance of 0 and the rest nodes with infinity
3. Now, fix the starting node as the current node
4. For the current node, analyse all of its unvisited neighbours and measure their distances by adding the current distance of the current node to the weight of the edge that connects the neighbour node and current node
5. Compare the recently measured distance with the current distance assigned to the neighbouring node and make it as the new current distance of the neighbouring node
6. After that, consider all of the unvisited neighbours of the current node, mark the current node as visited
7. If the destination node has been marked visited then stop, an algorithm has ended
8. Else, choose the unvisited node that is marked with the least distance, fix it as the new current node, and repeat the process again from step 4

For more detailed information, visit the Wikipedia page on Dijkstra's Algorithm.