What should be the time taken to execute a code to find all pair shortest paths among 800 vertices using iterative dijkstra? Which algorithm should I use to get it done within 1 second?
Use Fibonacci heap for Priority Queue implementation.
Time Complexity can be reduced to O(E+VlogV) from O(ElogV) because Fibonacci Heap takes O(1) time for decrease key operation while binary takes O(logn) time.
heap based dijkstra
Can you tell me some study materials on heap based dijkstra?
ocw.mit.edu