Practice Exam

Bellman-Ford Algorithm

It can handle graphs with negative weight edges.

Bellman-Ford Algorithm

It only calculates paths up to the first negative cycle.

Bellman-Ford Algorithm

Time complexity is 𝑂(∣𝑉∣×∣𝐸∣).

Bellman-Ford Algorithm

When the graph contains negative weight edges and you need to verify the presence of negative weight cycles.

Bellman-Ford Algorithm

After how many iterations of edge relaxations does the Bellman-Ford algorithm conclude in a graph with 𝑛n vertices? Answer:𝑛−1n−1

Bellman-Ford Algorithm

The purpose of the additional iteration after the initial ∣𝑉∣−1 iterations is to check for negative weight cycles.

Bellman-Ford Algorithm

Space complexity is 𝑂(∣𝑉∣).

Dijkstra's Algorithm

Priority Queue is commonly used in the implementation for optimal efficiency.

Dijkstra's Algorithm

It cannot handle negative weight cycles.

Dijkstra's Algorithm

Time complexity using a binary heap (priority queue) is 𝑂((∣𝐸∣+∣𝑉∣)log⁡∣𝑉∣).

Dijkstra's Algorithm

Terminated when all of the above conditions are met.

Dijkstra's Algorithm

When you need to find the shortest path in a graph with non-negative edge weights.

Dijkstra's Algorithm

It effectively solves finding the shortest path from a single source to all other vertices.

Dijkstra's Algorithm

Ensures the shortest path to a vertex is found before moving on to the next vertex by always choosing the vertex with the smallest known distance from the source next.

Floyd-Warshall Algorithm

It primarily computes the shortest paths between every pair of vertices in a graph.

Floyd-Warshall Algorithm

It updates its estimates based on relaxation of edges like Dijkstra's algorithm.

Floyd-Warshall Algorithm

Time complexity is 𝑂(∣𝑉∣3).

Floyd-Warshall Algorithm

Typically implemented on an Adjacency matrix.

Floyd-Warshall Algorithm

The matrix dist[][] is initially filled out by setting dist[i][j] to the weight of the edge (i, j) if it exists, otherwise infinity.

Floyd-Warshall Algorithm

It can detect cycles by finding negative values on the diagonal of the distance matrix after completion.

Floyd-Warshall Algorithm

Ideal for using when you need the shortest paths between every pair of vertices in a dense graph.