Find the shortest route, and see what it cost to find it.
RouteOpt is a graph-based navigation system that runs Dijkstra, A*, Bellman–Ford and BFS on the same weighted map. Pick two places and watch each algorithm search.
Try the demoSee benchmarksGet the data
- Start
- Destination
- Visited by the search
- Route found
- Nodes visited
- –
- Edges checked
- –
- Route cost
- –
- Stops on route
- –
What RouteOpt does
Route computation
Locations are vertices and routes are weighted edges. The system computes shortest paths and discovers routes across large map data.
Graph traversal
BFS and DFS handle connectivity checks, cycle detection and reachability queries. Topological sorting orders dependency-aware directed graphs.
Location search
A Trie powers prefix autocomplete, and a hash table gives constant-time lookup of a location and its metadata. Both are running in the search box above.
Benchmarking
A benchmarking framework compares traversal and shortest-path strategies as graphs grow, measuring runtime, memory use and scalability.
Shortest-path showdown
Dijkstra, A*, Bellman–Ford and BFS race on the same map and start–destination pair. Watch nodes visited, edges checked and route cost update live.
Map analytics
Heatmaps of visits, the cost matrix, busiest roads and scaling curves reveal how the map behaves — with every dataset downloadable as CSV.
Algorithms and data structures
| Technique | Time | Used for |
|---|---|---|
| Dijkstra | O((V + E) log V) | Shortest paths on non-negative weights, using a binary-heap priority queue |
| A* search | Depends on the heuristic | Goal-directed shortest paths that explore fewer nodes |
| Bellman–Ford | O(V · E) | Shortest paths that also tolerate negative weights |
| BFS / DFS | O(V + E) | Traversal, connectivity, cycle detection, reachability |
| Topological sort | O(V + E) | Ordering dependency-aware directed graphs |
| Trie | O(k) per prefix of length k | Autocomplete for location names |
| Hash table | O(1) average | Location lookup and metadata retrieval |
Data and benchmarks
Search effort — how hard each algorithm works
Same map, same pairs, four algorithms. Lower is better everywhere except route quality, where matching the cheapest route is the goal.
Average search effort
Mean over 630 pairs of 36 locations (all pairs, or a fixed sample on bigger maps), computed in your browser when the page loads.
Route quality
How much more the average route costs than the cheapest one, over the sampled pairs. BFS minimises hops, not cost.
Effort by distance
Average nodes visited, grouped by how many hops apart the start and destination are.
A* versus Dijkstra
Priority queue activity
Dijkstra and A* both use a binary heap. Pushes count how many entries were added, and the peak is the largest the heap ever got.
Average heap pushes per search
Average peak heap size
Time per search
Average time per search over the sampled pairs, measured in your browser. Timings vary between devices.
Bellman–Ford passes
Bellman–Ford repeats a pass over every road until nothing improves. Number of searches by passes needed:
What if road weights vary more?
The map is rebuilt with wider ranges of road weight, shown as a multiple of straight-line distance.
Who visits fewest nodes?
Share of sampled pairs where each algorithm visits the fewest nodes (ties count for every algorithm tied).
Map structure — what the map looks like
The terrain everything above runs on: sizes, shapes and distances.
The map in numbers
- Locations
- –
- Roads
- –
- Roads per location
- –
- Most hops between two places
- –
Roads per location
Road weight
Most connected places
Locations with the most roads meeting there — the map's natural hubs.
Least connected places
Hop distances
How many hops apart are pairs of places? Fewest-hop paths (BFS) across the sampled pairs.
Pairs reachable within k hops (cumulative)
Which locations get searched most
Many pairs of locations are searched (every pair on the 6 Ă— 6 map, a fixed sample on bigger maps), and each location visited along the way is counted.
How the cost grows
Road weight in numbers
Every road weight is its straight-line distance times 0.8–1.4.
- Lightest road
- –
- Average road
- –
- Heaviest road
- –
Routes — where the traffic goes
Tracing every cheapest route to see which places and roads matter most.
How far is everything from one place
Cheapest route cost from the chosen location to every other location. Darker means farther.
Which roads carry the most routes
The cheapest route for every sampled pair is traced, and each road on it is counted. Thicker means more routes.
Cheap roads carry more routes
Each dot is one road: its weight against how many cheapest routes use it.
Route costs
Cheapest route cost over all sampled pairs
Route cost divided by straight-line distance. 1.0 would be a straight road.
Longest cheapest routes
Top 5 costliest cheapest-routes across the sampled pairs.
Which locations sit in the middle
A location is counted each time it lies between the start and end of a cheapest route. Darker means more routes pass through it.
Locations most often passed through
Scaling — how it grows
From this map up to thousands of nodes: measure it live, or read the pre-measured Python numbers.
Scale it yourself
Builds grid graphs from 100 to 6,400 nodes and times each algorithm corner to corner. Timings depend on your device.
Measured scaling (Python)
Corner-to-corner searches on k × k grids, median of 3 runs with routeopt.py — the same code the Streamlit app and notebook use. Raw numbers: scaling_benchmark.csv.
Dependency ordering
Topological sort (Kahn's algorithm) orders dependency-aware task graphs and spots cycles — the same routine the Streamlit app and routeopt.topological_sort use. Try adding a line like deploy: fetch to create a cycle.
Data
The demo map is generated from seed 11 (6 Ă— 6 grid, 36 locations, 65 roads; switch to 8 Ă— 8 or 10 Ă— 10 above). The same data is checked into the repo so you can reproduce every chart:
- nodes.csv6 Ă— 6 map: 36 locations (id, label, x, y)
- edges.csv6 Ă— 6 map: 65 roads (endpoints, labels, weight)
- benchmark_allpairs.csv6 Ă— 6 map: 400 rows, 4 algorithms Ă— 100 random pairs
- nodes_8x8.csv8 Ă— 8 map: 64 locations (id, label, x, y)
- edges_8x8.csv8 Ă— 8 map: 121 roads
- benchmark_8x8.csv8 Ă— 8 map: 1,200 rows, 4 algorithms Ă— 300 random pairs
- scaling_benchmark.csvMeasured scaling: corner-to-corner on 25–900 node grids, median of 3 runs
Regenerate them any time with routeopt.py: make_grid_graph(6, 6, 11) + pair_effort(g, 100). The notebook walks through this step by step, and the Streamlit app lets you rebuild the map with different seeds and sizes.
Links and contact
Contact: harshinisuresha7@gmail.com