Johnson's algorithm improves the efficiency of finding all-pairs shortest paths in which type of graph?
Dense graphs with positive edge weights
Unweighted graphs
Directed acyclic graphs (DAGs)
Sparse graphs with negative edge weights
What is the relationship between A* search and Dijkstra's algorithm?
Dijkstra's algorithm is a special case of A* search.
A* and Dijkstra's algorithm are entirely unrelated.
A* is only applicable to unweighted graphs, while Dijkstra's algorithm works for weighted graphs.
A* is a generalization of Dijkstra's algorithm.
An undirected graph has 7 vertices, each with a degree of 4. Does this graph contain an Eulerian circuit?
No
Yes
Cannot be determined
The graph cannot exist
If a graph has negative edge weights but no negative weight cycles, which algorithm can still find the shortest path?
Neither algorithm can find the shortest path
Only Dijkstra's algorithm
Only Bellman-Ford algorithm
Both Dijkstra's and Bellman-Ford algorithm
What is an advantage of using a Fibonacci heap implementation for Dijkstra's algorithm?
It improves the time complexity for sparse graphs.
It simplifies the implementation of the algorithm.
It reduces the space complexity of the algorithm.
It allows the algorithm to handle negative edge weights.
How does Johnson's algorithm address the issue of negative edge weights when using Dijkstra's algorithm?
It ignores negative edge weights and proceeds with Dijkstra's algorithm.
It adds a large constant to all edge weights to make them positive.
It reweights the edges using a shortest path potential function.
It removes all negative edges from the graph.
How does the Bellman-Ford algorithm handle negative weight cycles when determining shortest paths?
It detects and reports the existence of negative weight cycles, indicating that a shortest path may not exist.
It ignores negative weight cycles and finds the shortest path regardless.
It modifies the edge weights to eliminate negative cycles before finding the shortest path.
It utilizes a separate algorithm to handle negative weight cycles after executing the main algorithm.
Dijkstra's algorithm can be considered a special case of which algorithm when applied to graphs with non-negative edge weights?
Bellman-Ford Algorithm
Depth First Search
Breadth First Search
A* Search
What technique does Johnson's algorithm utilize to handle negative edge weights efficiently?
Greedy edge relaxation
Reweighting edges using a potential function
Dynamic programming
Divide and conquer approach
Which of the following data structures is commonly used to implement the priority queue in A* search?
Binary heap
Queue
Stack
Linked list