Floyd-Warshall algorithm in Data Structures Theory - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the Floyd-Warshall algorithm used for?

The Floyd-Warshall algorithm is used to find the shortest paths between all pairs of vertices in a weighted graph, including graphs with negative edge weights but no negative cycles.

beginner

How does the Floyd-Warshall algorithm update distances between nodes?

It updates the shortest distance between two nodes by checking if going through an intermediate node provides a shorter path than the current known distance.

intermediate

What is the time complexity of the Floyd-Warshall algorithm?

The time complexity is O(n³), where n is the number of vertices in the graph, because it uses three nested loops to check all pairs of nodes through all possible intermediate nodes.

intermediate

Can the Floyd-Warshall algorithm handle graphs with negative edge weights?

Yes, it can handle negative edge weights as long as there are no negative weight cycles in the graph, because such cycles would make shortest paths undefined.

intermediate

What is the main difference between Floyd-Warshall and Dijkstra's algorithm?

Floyd-Warshall finds shortest paths between all pairs of nodes, while Dijkstra finds the shortest path from one source node to all others. Floyd-Warshall works with negative edges; Dijkstra does not.

What type of graph does the Floyd-Warshall algorithm work on?

A Weighted graphs with no negative cycles

B Only unweighted graphs

C Graphs with negative cycles

D Only directed acyclic graphs

Floyd-Warshall works on weighted graphs and can handle negative edges but not negative cycles.

What is the main idea behind Floyd-Warshall's approach?

A Greedy selection of the next closest node

B Using intermediate nodes to update shortest paths

C Depth-first search traversal

D Sorting edges by weight

The algorithm checks if paths through intermediate nodes are shorter than current known paths.

What is the time complexity of Floyd-Warshall algorithm?

A O(n²)

B O(n log n)

C O(n³)

D O(2^n)

It uses three nested loops over all vertices, resulting in O(n³) time complexity.

Which algorithm is better for finding shortest paths from a single source node?

A Dijkstra

B Floyd-Warshall

C Bellman-Ford

D Prim's algorithm

Dijkstra is optimized for single-source shortest path problems.

What happens if the graph contains a negative weight cycle?

A Floyd-Warshall detects it and stops

B It converts negative weights to positive

C Algorithm runs faster

D Shortest paths are undefined

Negative cycles cause shortest paths to be undefined because you can keep reducing path length indefinitely.

Explain how the Floyd-Warshall algorithm finds shortest paths between all pairs of nodes.

Think about checking every possible path through each node.

Describe the limitations of the Floyd-Warshall algorithm.

Consider what kinds of graphs cause problems and performance issues.