What is the time complexity of Prim's algorithm using a Binary Min-Heap for a graph with V vertices and E edges?
Extracting minimum vertex V times takes O(V log V) and updating edge key values E times takes O(E log V), total O((V + E) log V).
Dijkstra's single-source shortest path algorithm fails or may produce incorrect results when the graph contains:
Dijkstra's algorithm assumes once a vertex is finalized, its shortest path is found. Negative edge weights violate this greedy assumption.
Which algorithm can detect negative weight cycles in a directed weighted graph?
Bellman-Ford relaxes all edges V - 1 times. Running a V-th iteration that further reduces any distance indicates a negative weight cycle.
What is the time complexity of the Bellman-Ford algorithm for a graph with V vertices and E edges?
Bellman-Ford relaxes all E edges for V - 1 iterations, yielding a time complexity of O(V * E).
Which algorithm computes all-pairs shortest paths in a directed weighted graph using dynamic programming?
Floyd-Warshall computes shortest paths between all pairs of vertices in O($V^3)$ time using dynamic programming.