Design an API to Find shortest Distance between src and destination

Constraints

1. Graph is very very very very Large
   Large Number of Nodes and Many Edges

2. Graph is changing very very very frequently
   Weight of edges are changing
   Nodes are getting down or becoming unreachable or deleted

3. API is called very very very high number of times for different set of src and destination.
   This API Must be scalable

4. Graph is weighted

I think if this problem is similar to how traceroute or ping works?

I could not answer this, what is best design approach for it.