(Red dotted lines on the A* graph represent a Straight Line Distance
heuristic
from every node to the goal node.)
\(\forall t \in V, d[t] \leftarrow \infty \) // for all vertices (nodes) set initial distance estimates from source to be infinity
\(d[s] \leftarrow 0 \) // set start node distance to be zero
\(F \leftarrow \{v | \forall v \in V\} \) // \(F\) is the set of nodes that are yet to achieve final distance estimates
\( D \leftarrow \emptyset \) // \(D\) is the set of nodes that have achieved final distance estimates
\(while\) \(F \neq \emptyset\) \(do\)
\(x \leftarrow \) set x to be the node in F with the minimum distance estimate
\(for (x,y) \in E\) \(do\)
\(d[y] \leftarrow min\{d[y], d[x] + w(x,y)\} \) // "relax" the estimate y by setting its distance
// to the start node as the min of its current distance and the distance from start to x plus the distance from x to y
// to maintain/ record shortest paths: if d[y] changes, then \(\pi(y) \leftarrow x\) (set the predecessor of y to be x)
\(F \leftarrow F \backslash \{x\} \) // remove x from the set of nodes yet to achieve a final distance
\(D \leftarrow D \cup \{x\} \) // add x to the set of nodes that has achieved a final distance
Invariant:
Dijkstra maintains the following invariant: \(\forall t \in V\), the algorithm computes an estimate \(d[t]\) of the distance of \(t\) from the source (start) node such that:
- 1. At any point in time, \(d[t] \ge d(s,t)\)
- 2. When a vertex \(t\) has achieved a final distance estimate, \(d[t]= d(s,t)\)
Variables & Sets:
- \(F\) is the set of nodes that are yet to achieve final distance estimates
- \(D\) is set of nodes that have achieved final distance estimates
- \(E\) is set of neighbor nodes for an arbitrary node \(x\)
- \(w(x,y)\) is the distance from a neighbor node of \(x\), to \(x\). Label a neighbor of \(x\) as \(y\)
- \(\pi(y)\) maps to the predecessor node of an arbitrary vertex \(t\)
- \(d[t]\) is the distance of a node \(t\) to that of the source (start) node
- \(d(s,t)\) is the shortest distance of a node \(t\) to that of the (start) node
A*
A* differs from Dijkstra in a few ways. From Wikipedia:
At each iteration of its main loop, A* needs to determine which of its paths to extend. It does so based on the cost of the path and an estimate of the cost required to extend the path all the way to the goal. Specifically, A* selects the path that minimizes \(f(n) = g(n) + h(n)\) where \(n\) is the next node on the path, \(g(n)\) is the cost of the path from the start node to \(n\), and \(h(n)\) is a heuristic function that estimates the cost of the cheapest path from n to the goal. A* terminates when the path it chooses to extend is a path from start to goal or if there are no paths eligible to be extended.The heuristic function is problem-specific. If the heuristic function is admissible – meaning that it never overestimates the actual cost to get to the goal –, A* is guaranteed to return a least-cost path from start to goal.
Sources: