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

Recall & Review

beginner

What is the main purpose of the Floyd Warshall algorithm?

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

beginner

What is the time complexity of the Floyd Warshall algorithm?

The time complexity is O(V³), where V is the number of vertices in the graph.

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 intermediate nodes up to a certain index k.

intermediate

Why can Floyd Warshall handle negative edge weights but not negative cycles?

Because it updates shortest paths by checking intermediate nodes, but if a negative cycle exists, distances can decrease indefinitely, making shortest paths undefined.

beginner

What is the initial setup of the distance matrix in Floyd Warshall?

Set dist[i][j] to the edge weight if there is an edge from i to j; set dist[i][i] to 0 for all i; set dist[i][j] to infinity if no direct edge exists.

What does Floyd Warshall algorithm compute?

A Minimum spanning tree

B Shortest path from a single source to all vertices

C Shortest paths between all pairs of vertices

D Topological sort

Floyd Warshall computes shortest paths between every pair of vertices.

What is the time complexity of Floyd Warshall algorithm for a graph with V vertices?

A O(V²)

B O(V³)

C O(E log V)

D O(V + E)

Floyd Warshall uses three nested loops over vertices, resulting in O(V³) time.

Which type of graphs can Floyd Warshall handle that Dijkstra's algorithm cannot?

A Graphs with negative edge weights

B Graphs with cycles

C Graphs with only positive weights

D Graphs without edges

Floyd Warshall can handle negative edge weights as long as there are no negative cycles.

What does the Floyd Warshall algorithm use to update shortest paths?

A Relaxation of edges

B Depth-first search

C Greedy selection of edges

D Dynamic programming with intermediate nodes

It uses dynamic programming considering intermediate nodes to update shortest paths.

What is the initial value of dist[i][i] in Floyd Warshall algorithm?

A 0

B Edge weight from i to i

C Infinity

D -1

Distance from a node to itself is always 0.

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

Think about how the algorithm tries all possible intermediate nodes.

Describe the differences between Floyd Warshall and Dijkstra's algorithm in terms of use cases and limitations.

Consider the type of graphs and the problem each algorithm solves.