Floyd Warshall All Pairs Shortest Path in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What problem does the Floyd Warshall algorithm solve?

It finds the shortest paths between all pairs of nodes in a weighted graph, including graphs with negative edge weights but no negative cycles.

intermediate

What is the main idea behind the Floyd Warshall algorithm?

It uses dynamic programming to update shortest paths by considering each node as an intermediate point, improving paths step-by-step until all shortest paths are found.

intermediate

In Floyd Warshall, what does the matrix entry dist[i][j] represent during the algorithm?

It represents the shortest known distance from node i to node j considering only intermediate nodes from the set {1, 2, ..., k} at step k.

beginner

What is the time complexity of the Floyd Warshall algorithm?

The time complexity is O(n³), where n is the number of nodes in the graph, because it uses three nested loops over all nodes.

advanced

Can Floyd Warshall detect negative weight cycles? If yes, how?

Yes, by checking if any dist[i][i] becomes negative after the algorithm finishes, indicating a negative cycle reachable from node i.

What does Floyd Warshall algorithm compute?

A Shortest paths between all pairs of nodes

B Shortest path from a single source to all nodes

C Minimum spanning tree

D Topological sort

Floyd Warshall finds shortest paths between every pair of nodes.

Which of these is true about Floyd Warshall algorithm?

A It can handle negative edges but no negative cycles

B It works only on graphs without negative edges

C It finds shortest paths using BFS

D It uses a priority queue

Floyd Warshall can handle negative edges but fails if negative cycles exist.

What is the main data structure used in Floyd Warshall?

A Adjacency list

B Queue

C Stack

D Distance matrix

Floyd Warshall uses a matrix to store shortest distances between nodes.

What does a negative value in dist[i][i] after Floyd Warshall indicate?

A No path exists

B Graph is disconnected

C Negative weight cycle reachable from node i

D Algorithm failed

Negative dist[i][i] means a negative cycle involving node i.

What is the time complexity of Floyd Warshall algorithm?

A O(n log n)

B O(n³)

C O(n²)

D O(m + n)

Floyd Warshall uses three nested loops over n nodes, so O(n³).

Explain how Floyd Warshall algorithm updates the shortest path matrix step-by-step.

Think about dynamic programming and intermediate nodes.

Describe how Floyd Warshall algorithm can detect negative weight cycles in a graph.

Focus on the meaning of dist[i][i] after algorithm finishes.