We need at least memory to store all pairs shortest path.

We can use Dijkstra's algorithm to find the shortest path in edge-weighted graph, even if we have negative weights as long as there is no negative cycle.

The table entry in the Floyd-Warshall algorithm stores the distance of the shortest path from vertex to vertex that goes through the vertex .

We can detect existence of a negative cycle in the graph using Floyd-Warshall algorithm.