Eppstein’s k shortest paths in the web browser with OpenStreetMap

This page demonstrates a JavaScript implementation of Eppstein’s k shortest paths algorithm applied to geospatial data from OpenStreetMap.

Eppstein’s algorithm finds the k shortest paths connecting a pair of nodes in a digraph with n nodes and m edges in time O(m + n log n + k).

Technologies used:

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

Paths are listed on the left. Move your cursor over a path to render it on the map. Click the reload button to calculate a new set of paths connecting two random nodes.