ANSPR0 near-shortest paths in the web browser with OpenStreetMap

This page demonstrates a JavaScript implementation of the ANSPR0 near-shortest paths algorithm (Carlyle and Wood 2005). The algorithm finds all loopless paths within some threshold of the shortest path.

ANSPR0 has exponential worst case time complexity but tends to be very fast on smaller networks with lower thresholds (Medrano and Church 2011). In the random examples on this page, some NSPs will be generated quickly while others will take much longer.

Technologies used:

• OpenStreetMap geospatial data
• Leaflet rendering
• MapBox tiles
• React & Redux user interface

The orange line represents a random shortest path. The purple lines represent all paths within 3% of the shortest path.