Dijkstra’s Algorithm

Overview

Dijkstra’s Algorithm is a renowned graph algorithm in applied mathematics and computer science, designed to find the shortest paths from a given start node to all other nodes in the graph.
The algorithm works by visiting nodes in the graph starting from the root node, then iteratively adding the next most nearby node until all nodes have been visited.

A graph is a collection of nodes (or vertices) interconnected by lines known as edges.
The weight of an edge refers to a numerical value assigned to the connection between two nodes in a graph. It often represents a ‘cost’ or ‘distance’ between those nodes.
The shortest path between two nodes is the path with the least total edge weight or cost.
Dijkstra’s Algorithm uses a greedy approach. It always picks the node with the smallest total distance from the start node at each step, assuming this will lead to an optimal solution.

Assign to every node a tentative distance from the start node: set it to zero for the initial node and to infinity for all other nodes.
Set the initial node as the current node. For the current node, consider all of its unvisited neighbours and calculate their tentative distances from the start node.
When done considering all unvisited neighbours of the current node, mark it as visited. A visited node will not be checked again.
If the destination node has been marked as visited, stop. The algorithm has finished.
Otherwise, select the unvisited node that is marked with the smallest tentative distance, and set it as the new current node.
Repeat steps 3 to 5 until all nodes have been visited or the shortest path to the destination node is found.

Dijkstra’s Algorithm is an iterative algorithm that provides us with the shortest path from one particular starting node to all other nodes in the graph.
The algorithm maintains a list of unvisited nodes and continuously updates their tentative distances from the start node, optimising the path iteratively until the shortest path is found.

Used in routing and as a subroutine in other graph algorithms.
For a map with cities as the nodes and roads as the edges, and a numerical value that indicates the distance between the two cities, Dijkstra’s Algorithm can find the shortest possible route between two given cities.

Dijkstra’s Algorithm doesn’t work for graphs with negative edge weights. The algorithm assumes that the current shortest path is optimal, and this is not always true with negative weights.

Bellman-Ford Algorithm is a generalisation to deal with edges that have negative weights. The downside is that it’s slower compared to Dijkstra’s Algorithm.
Floyd-Warshall Algorithm finds the shortest path between all possible pairs of nodes, but it’s slower than Dijkstra’s Algorithm which finds the shortest path from one node to all other nodes.
Prim’s Algorithm is a graph algorithm that finds a minimum spanning tree for a given weighted graph, whereas Dijkstra’s Algorithm is more about pathfinding and not constructing a tree.