Master Shortest Path Algorithms: Dijkstra's, Bellman-Ford, Floyd-Warshall

Question 1

In the context of shortest path algorithms, what does the term 'relaxation' refer to?

Accepted Answer

Updating the distance estimate of a vertex

Answer

Marking a vertex as visited

Answer

Adding a vertex to the priority queue

Question 2

Which of the following is not a Shortest Path Algorithm?

Accepted Answer

Breadth-first search (BFS)

Answer

Dijkstra's algorithm

Answer

Bellman-Ford algorithm

Answer

Floyd-Warshall algorithm

Question 3

What is a key advantage of using a heap data structure in Dijkstra's algorithm?

Accepted Answer

Faster extraction of the vertex with the smallest distance

Answer

Reduced memory usage

Answer

Improved time complexity

Answer

Easier implementation

Question 4

Which algorithm can be used to find the shortest path between any two vertices in a graph with negative weights, but **no negative cycles**?

Accepted Answer

Bellman-Ford

Answer

Dijkstra

Answer

Floyd-Warshall

Question 5

Which algorithm efficiently computes **all-pairs shortest paths** in a graph?

Accepted Answer

Floyd-Warshall

Answer

Dijkstra

Answer

Bellman-Ford

Question 6

Which data structure is typically used to efficiently implement Dijkstra's algorithm?

Accepted Answer

Priority queue

Answer

Array

Answer

Linked list

Question 7

Which technique can be used to optimize Floyd-Warshall algorithm for **sparse graphs**?

Accepted Answer

Transitive closure

Answer

Path relaxation

Answer

Bellman-Ford relaxation

Question 8

Which property of a graph ensures that Floyd-Warshall algorithm will terminate?

Accepted Answer

Absence of negative cycles

Answer

Acyclic graph

Answer

Weighted edges

Question 9

Which application of shortest path algorithms involves finding the shortest route between two locations on a map?

Accepted Answer

Routing

Answer

Network optimization

Answer

Scheduling

Question 10

Which of the following is not a Shortest Path Algorithm?

Accepted Answer

Kruskal's Algorithm

Answer

Dijkstra's Algorithm

Answer

Bellman-Ford Algorithm

Answer

Floyd-Warshall Algorithm

Question 11

Which algorithm can handle negative edge weights without negative cycles?

Accepted Answer

Bellman-Ford Algorithm

Answer

Dijkstra's Algorithm

Answer

Floyd-Warshall Algorithm

Question 12

What does the Floyd-Warshall Algorithm compute?

Accepted Answer

Shortest paths between all pairs of vertices

Answer

Minimum spanning tree of a graph

Answer

Longest path in a graph

Answer

Eulerian circuit of a graph

Question 13

Which of the following data structures is used in the implementation of Dijkstra's Algorithm?

Accepted Answer

Priority Queue

Answer

Adjacency List

Answer

Hash Table

Answer

Stack

Question 14

In a directed graph with non-negative edge weights, which algorithm is best suited to find the shortest path between two vertices?

Accepted Answer

Dijkstra's Algorithm

Answer

Bellman-Ford Algorithm

Answer

Floyd-Warshall Algorithm

Question 15

Which algorithm can efficiently find the shortest path between two nodes in a directed graph, even if the graph contains negative edge weights?

Accepted Answer

Bellman-Ford algorithm

Answer

Dijkstra's algorithm

Answer

Floyd-Warshall algorithm

Answer

Prim's algorithm

Question 16

Which algorithm efficiently finds the shortest path from a source vertex to all other vertices in a weighted, directed graph that does not contain negative-weight cycles?

Accepted Answer

Dijkstra's algorithm

Answer

Bellman-Ford algorithm

Answer

Kruskal's algorithm

Answer

Floyd-Warshall algorithm

Question 17

Which algorithm is suitable for finding the shortest paths between all pairs of vertices in a weighted, directed graph?

Accepted Answer

Floyd-Warshall algorithm

Answer

Prim's algorithm

Answer

Bellman-Ford algorithm

Answer

Dijkstra's algorithm

Question 18

What is the worst-case time complexity of Dijkstra's algorithm?

Accepted Answer

O((V + E) * log V)

Answer

O(V^2)

Answer

O(V * log E)

Answer

O(E * log V)

Question 19

What is the main difference between Dijkstra's algorithm and the Bellman-Ford algorithm?

Accepted Answer

Dijkstra's algorithm cannot handle negative-weight edges, while Bellman-Ford algorithm can.

Answer

Dijkstra's algorithm can handle negative-weight edges, while Bellman-Ford algorithm cannot.

Answer

Bellman-Ford algorithm is faster than Dijkstra's algorithm.

Question 20

Which shortest path algorithm is most suitable for efficiently finding the shortest path between all pairs of vertices in a weighted graph?

Accepted Answer

Floyd-Warshall Algorithm

Answer

Breadth-First Search Algorithm

Answer

Dijkstra's Algorithm

Answer

Bellman-Ford Algorithm

Question 21

Dijkstra's algorithm is guaranteed to find the shortest paths from a single source vertex to all other vertices in a graph if:

Accepted Answer

All edge weights are non-negative.

Answer

The graph is undirected.

Answer

The graph is acyclic.

Answer

The graph is connected.

Question 22

Which data structure is most commonly used for efficient implementation of Dijkstra's algorithm?

Accepted Answer

Priority Queue

Answer

Queue

Answer

Stack

Answer

Hash Table

Question 23

In a weighted graph containing negative edge weights, which algorithm is the most suitable for finding the shortest path between a given pair of vertices?

Accepted Answer

Bellman-Ford Algorithm

Answer

Dijkstra's Algorithm

Answer

Floyd-Warshall Algorithm

Answer

A* Search Algorithm

Question 24

Which of the following is NOT a typical application of shortest path algorithms?

Accepted Answer

Sorting a list of numbers

Answer

Finding the shortest driving route between two locations

Answer

Routing packets in a computer network

Answer

Optimizing resource allocation in a project

Question 25

In the context of shortest path algorithms, what does the relaxation operation involve?

Accepted Answer

Updating the estimated distance to a vertex if a shorter path through a neighboring vertex is found

Answer

Calculating the total weight of a path

Answer

Adding a new edge to the graph

Answer

Removing a vertex from the graph

Question 26

How does the Floyd-Warshall algorithm handle negative weight cycles in a weighted graph?

Accepted Answer

It can detect the presence of negative weight cycles but cannot compute shortest paths if they exist.

Answer

It ignores negative weight cycles and computes shortest paths as if they were positive.

Answer

It can find the shortest paths even in the presence of negative weight cycles.

Answer

It terminates with an error upon encountering a negative weight cycle.

Question 27

What is the primary difference between Dijkstra's algorithm and the A* search algorithm?

Accepted Answer

A* utilizes a heuristic function to guide its search towards the destination, while Dijkstra's does not.

Answer

A* is guaranteed to find the shortest path, while Dijkstra's may not.

Answer

A* is only applicable to grid-based graphs, while Dijkstra's is more general.

Answer

Dijkstra's algorithm can handle negative edge weights, while A* cannot.