Must a landmark be on the final route?

No. It is a reference vertex used to obtain a distance bound.

Is the sum of distances through a landmark the lower bound?

No. In the undirected example, the absolute difference supplies the lower bound; the sum corresponds to a possible detour.

Can the same formula be used unchanged for one-way networks?

No. Directed graphs require direction-aware distances and inequalities.

AI Glossary / Graphs and symbolic AI / Intermediate

Landmark points

Definition

In shortest-path search, landmark points are selected graph vertices whose precomputed distances help estimate the remaining distance between other vertices. A landmark-based heuristic uses those distances and the triangle inequality to obtain a lower bound for a route query. This entry uses that search meaning, rather than facial landmarks or other reference points in computer vision.

What it means

The landmark is a reference vertex, not necessarily a famous place, an intermediate stop, or part of the final route. Its usefulness comes from the distance information stored around it. That information can help A* prioritize promising search states while preserving the required lower-bound property.
The approach is often called ALT, referring to A*, landmarks, and the triangle inequality. It separates preparation from individual queries: the system invests work in computing landmark distances, then reuses them for many searches. This makes the amount of preprocessing, available memory, and stability of the graph important practical considerations.

How it works

For an undirected graph with nonnegative edge costs, shortest-path distances satisfy the triangle inequality. If L is a landmark, u is the current vertex, and t is the target, the difference between their distances from L provides a bound: the absolute value of d(L,t) minus d(L,u) cannot exceed d(u,t).
Compute such a bound for each selected landmark and take the largest. Each bound is valid, so their maximum is also a valid lower bound. Directed graphs require direction-aware formulas and distances to and from landmarks; simply assuming symmetry is incorrect. The search must also handle unreachable vertices appropriately rather than performing undefined arithmetic with infinite distances.

Three practical examples

A route service preprocesses a stable road graph so that repeated point-to-point queries can use landmark-based lower bounds.
A warehouse routing experiment compares landmark choices on a fixed aisle graph with nonnegative travel costs.
A graph-search lesson contrasts a landmark distance bound with the cost of an actual route that detours through the landmark.

Think of it this way

Think of comparing two places by how far each lies from the same reference town. A large difference proves that the places cannot be extremely close together. The analogy is limited because graph distance follows permitted connections and costs; it need not equal straight-line geographic distance, and directed travel may differ between the two directions.

Worked example

Consider an invented undirected graph with two landmarks, L1 and L2. For a query from u to t, suppose the stored shortest-path distances are d(L1,u) = 3 and d(L1,t) = 11. Landmark L1 therefore gives the lower bound |11 - 3| = 8.
Suppose d(L2,u) = 9 and d(L2,t) = 2. Landmark L2 gives |2 - 9| = 7. Combining the landmarks yields h(u) = max(8, 7) = 8. If the actual shortest-path cost from u to t is 10, the heuristic is a valid underestimate by 2 cost units.
These numbers are mutually compatible. One possible graph contains edges u - t of cost 10, L1 - u of cost 3, L1 - t of cost 11, L2 - u of cost 9, and L2 - t of cost 2. None of the indirect alternatives shortens the four stated landmark distances.
Adding the two distances through L1 gives 3 + 11 = 14, which describes a possible walk via L1, not the lower bound used here. Confusing 14 with the heuristic would overestimate the true cost of 10. The example illustrates distance bounds, not a measured speed improvement or a recommendation for choosing these particular landmarks.

Illustrative case study

In a fictional routing project, Harbor Paths adds landmark preprocessing to a fixed network. The team initially treats landmark vertices as compulsory stops and produces unnecessary detours. It corrects the implementation so that landmark information only guides the search priorities.
Later, an edge-cost update prompts a review of the cached distances before they are reused. The team does not assume that old bounds remain valid after arbitrary changes. This invented case highlights the difference between a reference used for reasoning and a required location in the route itself.

Common misconceptions and mistakes

Landmarks do not automatically lie on an optimal path. More landmarks also do not guarantee lower total runtime, because computing and storing their information has a cost and each query must evaluate the relevant bounds.
Do not use the undirected absolute-difference formula indiscriminately for directed graphs. Also distinguish the triangle inequality for shortest-path distances from a requirement that individual edge weights form a Euclidean metric. A lower-bound heuristic guides search; it does not by itself replace the search algorithm or prove that a particular implementation handles updates, disconnected components, and numerical issues correctly.

Business use

Landmark methods can be useful when a system answers many route queries over a graph that changes relatively slowly. Evaluate the full workload: preprocessing time, memory per landmark, query latency, and the cost of rebuilding or validating data after updates.
Compare representative queries rather than selecting landmarks only for one convenient example. Record which edge costs and directions the stored distances reflect. For a changing operational network, establish when cached information can be reused safely. These choices matter more to deployment than the mere presence of a landmark heuristic in the algorithm description.

Check your understanding

Which lower bound does the worked example use, and why not add 8 and 7?

Answer: It uses the maximum, 8. Both numbers bound the same remaining distance; adding them has no general justification and could overestimate that distance.

Related terms

Admissible heuristic
Shortest Paths
Triangle inequality
Preprocessing
Directed graph
A* search
shortest path
distance oracle
ALT algorithm

Learn next

Draw the five-edge example and verify each landmark distance. Then remove one direction of travel and examine why symmetric distance assumptions fail. Compare a lower bound with the cost of a complete candidate route.

Sources

Sources: Goldberg and Harrelson, Computing the Shortest Path: A* Search Meets Graph Theory, original research record: https://www.microsoft.com/en-us/research/publication/computing-the-shortest-path-a-search-meets-graph-theory-2/ JGraphT, official ALTAdmissibleHeuristic documentation: https://jgrapht.org/javadoc/org.jgrapht.core/org/jgrapht/alg/shortestpath/ALTAdmissibleHeuristic.html

Previous: Landmark point Next: Landmarks