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?
heap based dijkstra
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.
Can you tell me some study materials on heap based dijkstra?
ocw.mit.edu