black_hatinside's blog

how to optimize dijkstra algorithm in a graph where new nodes and edges can be added
By black_hatinside, history, 3 years ago, In English

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).

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply