All simulators
Shortest paths
Find the quickest route across a city map, step by step, the way maps apps do.
Find the quickest route across a city map, step by step, the way maps apps do.
Malleshwaram is 0 minutes from itself. Every other place starts at ∞ (no route known yet).
A maps app sees the city as a graph: places are nodes and roads are edges with a travel time. Dijkstra’s algorithm keeps a best-time-so-far for every place. Each round it ticks off the unfinished place with the smallest time, which is now final because every other way there is already longer. Then it checks that place’s roads to see if they give a quicker way to its neighbours.
Breadth-first search ignores the minutes and counts roads. It explores in rings: first every place 1 road away, then 2 roads away, and so on, using a queue. Fewest roads is not always fastest: a route with more, quicker roads can win.
Takeaway: “shortest” depends on what you count. Dijkstra finds the least total time (as long as no road has a negative time); BFS finds the fewest stops.
| Place | Time | Via | Status |
|---|---|---|---|
| Yelahanka | ∞ | — | |
| Malleshwaram (start) | 0 | — | frontier |
| Hebbal | ∞ | — | |
| Majestic | ∞ | — | |
| MG Road | ∞ | — | |
| Indiranagar | ∞ | — | |
| Whitefield (end) | ∞ | — | |
| Jayanagar | ∞ | — | |
| Koramangala | ∞ | — | |
| Electronic City | ∞ | — |
A maps app sees the city as a graph: places are nodes and roads are edges with a travel time. Dijkstra’s algorithm keeps a best-time-so-far for every place. Each round it ticks off the unfinished place with the smallest time, which is now final because every other way there is already longer. Then it checks that place’s roads to see if they give a quicker way to its neighbours.
Breadth-first search ignores the minutes and counts roads. It explores in rings: first every place 1 road away, then 2 roads away, and so on, using a queue. Fewest roads is not always fastest: a route with more, quicker roads can win.
Takeaway: “shortest” depends on what you count. Dijkstra finds the least total time (as long as no road has a negative time); BFS finds the fewest stops.
Things to try