Dijkstra and A* Algorithms: Finding the Shortest Route
Dijkstra and A* (A-star) are the two best-known algorithms for finding the shortest route in a weighted graph, such as a road network. Both are often used in navigation apps, games, and delivery route planning.
Dijkstra's algorithm
This algorithm was developed by Edsger W. Dijkstra in 1956 (published in 1959). Dijkstra finds the shortest distance from one source node to all other nodes, provided that edge weights are not negative.
Steps
Give distance 0 to the source node and infinity to the others. Mark all nodes as unvisited.
Pick the unvisited node with the smallest tentative distance and mark it visited.
For each of its neighbors, compute the new distance through this node. If it is smaller than the tentative distance, update it and record the predecessor.
Repeat until the destination is visited or all nodes are processed.
Trace the predecessors from the destination back to the source to get the route.
Dijkstra example
A graph with edges: A-B = 4, A-C = 2, C-B = 1, B-D = 5, C-D = 8. Find the shortest route from A to D.
Start: A = 0. From A: B = 4, C = 2.
Pick C (2). Via C: B = 2 + 1 = 3 (smaller than 4, so updated), D = 2 + 8 = 10.
Pick B (3). Via B: D = 3 + 5 = 8 (smaller than 10, updated).
Pick D (8), done.
The shortest route is A → C → B → D with a total distance of 8.
The A* algorithm
A* was introduced by Hart, Nilsson, and Raphael in 1968. It extends Dijkstra by adding a heuristic so the search is directed toward the goal. Each node is scored with:
f(n) = g(n) + h(n)
g(n): the actual cost from the source to node n.
h(n): the estimated cost from n to the goal, for example straight-line (Euclidean) distance or Manhattan distance on a grid.
A* always expands the node with the smallest f(n), using an open list (candidates) and a closed list (already examined). For the result to be optimal, the heuristic must be admissible, meaning it never exceeds the true cost to the goal. If the heuristic is also consistent, nodes need not be re-examined.
Differences between Dijkstra and A*
Dijkstra expands nodes based only on g(n), so it spreads in all directions. A* uses g(n) + h(n), so it is more directed toward the goal.
Dijkstra gives distances to all nodes, while A* focuses on a single source and goal pair.
If h(n) = 0 for all nodes, A* behaves exactly like Dijkstra.
A* usually examines fewer nodes when the heuristic is good, but it needs a suitable heuristic.
Strengths and weaknesses
Dijkstra: guaranteed optimal for non-negative weights and easy to implement, but it can be slow on large graphs because it explores in all directions. With a priority queue, its complexity is about O((V + E) log V).
A*: faster when the heuristic is good and optimal when the heuristic is admissible, but it needs more memory and its quality depends on the heuristic design.
Neither handles negative weights (use Bellman-Ford for that).
Applications
Both algorithms are used for map navigation, game pathfinding, network routing, and logistics route optimization. For a thesis, you can compare the number of nodes examined and the execution time of both on the same map.
Conclusion
Dijkstra suits finding shortest distances to many destinations, while A* is more efficient for a single destination with a good heuristic. Choose according to your needs and explain the heuristic you use.