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