Johnson's algorithm leverages which two algorithms to efficiently find all-pairs shortest paths in a graph with both positive and negative edge weights?
Bellman-Ford algorithm and Floyd-Warshall algorithm
Depth-First Search and Breadth-First Search
A* search algorithm and Dijkstra's algorithm
Dijkstra's algorithm and Bellman-Ford algorithm
How does Johnson's algorithm address the issue of negative edge weights when using Dijkstra's algorithm?
It reweights the edges using a shortest path potential function.
It adds a large constant to all edge weights to make them positive.
It ignores negative edge weights and proceeds with Dijkstra's algorithm.
It removes all negative edges from the graph.
What technique does Johnson's algorithm utilize to handle negative edge weights efficiently?
Divide and conquer approach
Reweighting edges using a potential function
Dynamic programming
Greedy edge relaxation
Which of the following scenarios would likely benefit most from using the A* search algorithm?
Finding all possible paths between two vertices in a graph.
Determining if a graph is connected.
Finding the shortest path in a weighted graph with a known heuristic estimate to the goal.
Finding the shortest path in an unweighted, undirected graph.
What is the purpose of the heuristic function in the A* search algorithm?
To estimate the cost of the cheapest path from the current node to the goal node.
To store the visited nodes to avoid cycles.
To determine the order in which nodes are visited during the search.
To calculate the exact cost of the path from the start node to the current node.
Johnson's algorithm improves the efficiency of finding all-pairs shortest paths in which type of graph?
Directed acyclic graphs (DAGs)
Unweighted graphs
Dense graphs with positive edge weights
Sparse graphs with negative edge weights
A graph representing a social network has users as vertices and friendships as edges. What does finding the chromatic number of this graph signify?
The maximum number of friendships in the network.
The minimum number of groups that can be formed where everyone knows each other within a group.
The maximum number of users who are not friends with each other.
The minimum number of groups that can be formed where no two friends are in the same group.
In the worst-case scenario, what is the time complexity of the Floyd-Warshall algorithm for a graph with 'V' vertices?
O(V^2)
O(V^3)
O(E log V)
O(V log V)
In a directed graph, what is the necessary and sufficient condition for the existence of an Eulerian path?
At most two vertices have a difference of 1 between their in-degree and out-degree, and all other vertices have equal in-degree and out-degree.
The graph has no cycles.
All vertices have the same in-degree and out-degree.
The graph is strongly connected.
What is the time complexity of the Edmonds-Karp algorithm when using a Breadth-First Search (BFS) to find augmenting paths in a network flow graph with 'V' vertices and 'E' edges?
O(V * E)
O(E^2 * V)
O(V + E)
O(V^2 * E)