What is the time complexity of the Floyd-Warshall all-pairs shortest paths algorithm for a graph with V vertices and E edges?
Floyd-Warshall uses three nested loops over all vertices k, i, j from 1 to V. Total time complexity = O($V^3)$.
In Floyd-Warshall algorithm, what does the matrix entry $d^{k}$[i, j] represent?
$d^{k}$[i, j] represents the shortest path weight from vertex i to vertex j such that all intermediate vertices on the path belong to the subset {1, 2, ..., k}.
How can Floyd-Warshall algorithm detect the presence of a NEGATIVE WEIGHT CYCLE in a directed graph?
Normally, d[i][i] = 0 (distance from a vertex to itself). If d[i][i] becomes negative, it means a path from i back to i has negative total weight, signaling a negative weight cycle.
What is the main advantage of the Bellman-Ford algorithm over Dijkstra's algorithm for single-source shortest paths?
Dijkstra's greedy choice fails on negative edge weights. Bellman-Ford correctly computes shortest paths with negative edges and detects negative cycles.
What is the worst-case time complexity of Bellman-Ford algorithm on a graph with V vertices and E edges?
Bellman-Ford relaxes all E edges (V - 1) times. Total time complexity = O(V * E).