Блог пользователя black_hatinside

Автор black_hatinside, история, 4 года назад, По-английски

Trying to implement the system design of Uber where I am allowed to add new locations and new routes to those locations anywhere in the map. How can I optimize my Dijkstra algorithm so that I don't have to run it for all the nodes everytime I add a new edge or node to my graph (map).

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
4 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Iirc Uber and other location based services work on Hilbert Curve.

»
4 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

You can read about D* algorithms, for example D*Lite.