Module org.jgrapht.demo

Package org.jgrapht.demo

Class ShortestPathAStarALTDemo

java.lang.Object

org.jgrapht.demo.ShortestPathAStarALTDemo

public final class ShortestPathAStarALTDemo
extends Object

Demo comparing A* shortest path search with a trivial (zero) heuristic against A* guided by the ALT (A*, Landmarks, Triangle inequality) heuristic.

ALT precomputes shortest-path distances from a small set of landmark vertices and uses the triangle inequality to derive a tight, admissible lower-bound estimate of the remaining distance to the target. This lets A* skip exploring large portions of the graph without ever sacrificing the guarantee of finding the true shortest path.

The demo builds a weighted grid graph, computes the shortest path between two opposite corners using both heuristics, and reports how many vertices each search had to expand. Both approaches must agree on the path weight -- ALT only changes search efficiency, never correctness.

Author:

federicodeca

Method Summary

Modifier and Type	Method	Description
static void	main(String[] args)	Main demo entry point.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Details

main

public static void main(String[] args)

Main demo entry point.

Parameters:

args - command line arguments