Table of Contents
The algorithms A* and Dijkstra’s are fundamental in pathfinding and graph traversal. They are widely used in navigation systems, robotics, and network routing. Understanding their mathematical foundations helps in optimizing their performance and applicability.
Graph Representation
Both algorithms operate on graphs, which consist of nodes (vertices) and edges. Edges may have weights representing costs, distances, or times. The graph can be directed or undirected, and the weights are usually non-negative.
Cost Functions and Heuristics
The core of these algorithms involves calculating the cost to reach each node. Dijkstra’s algorithm uses the cumulative cost from the start node, while A* adds a heuristic estimate of the remaining cost to the goal. The heuristic must be admissible, meaning it never overestimates the true cost.
Mathematical Formulation
Let G = (V, E) be a graph with vertices V and edges E. Each edge (u, v) has a weight w(u, v). The goal is to find the shortest path from start node s to goal node t.
Dijkstra’s algorithm updates the distance d(v) for each vertex v, initialized as d(s) = 0 and d(v) = ∞ for v ≠ s. It iteratively selects the vertex with the smallest d(v), then relaxes its neighboring edges.
A* modifies this by incorporating a heuristic h(v) estimating the cost from v to t. The priority function becomes f(v) = d(v) + h(v). The algorithm expands nodes based on the lowest f(v).
Algorithm Efficiency
The efficiency depends on the data structures used. Dijkstra’s algorithm has a time complexity of O(|E| + |V| log |V|) with a priority queue. A* can be faster if the heuristic is well-designed, reducing the number of nodes expanded.
- Graph with non-negative weights
- Admissible heuristic for A*
- Priority queue for node selection
- Relaxation of edges to update costs