I'm trying to come up with an algorithm to solve all-pairs shortest paths (APSP) problem in dynamic directed planar graph with nonnegative real weights. Additionally:
- My primary focus is to achieve lowest possible query time ($O(1)$ would be perfect), it's the most important thing for me, this operation will be done very often (of course the price will be increased memory consumption, but I'm fine with that),
- Graph is fully dynamic - both edges & vertices can be added/deleted - it would be nice if I didn't have to recompute everything from scratch,
- $|V| = 10000$ (approximately).
I've search the Internet and skimmed through lots of articles, but didn't find anything that matched perfectly my case.
Any help and/or links would be highly appreciated.