Graph Algorithms: Basics of Shortest Path and Network Flow
An introductory quiz on graph algorithms focusing on shortest path and network flow concepts.
Questions in this quiz
15 questions on Graph Algorithms: Basics of Shortest Path and Network Flow. Work through them here, then start the quiz to answer them and see your score.
1.What is the primary purpose of Dijkstra's algorithm?
- ATo find the shortest path from a single source to all other nodes in a weighted graph.
- BTo find the minimum spanning tree of a graph.
- CTo perform a depth-first search on a graph.
- DTo detect cycles in a graph.
2.Which data structure is commonly used to implement Dijkstra's algorithm efficiently?
- AStack
- BHash Table
- CQueue
- DPriority Queue
3.What is the Bellman-Ford algorithm primarily used for?
- AFinding the maximum flow in a network.
- BDetecting cycles in a graph.
- CFinding the shortest path in an unweighted graph.
- DFinding the shortest path in a graph with negative weight edges.
4.Which of the following algorithms is used to find the maximum flow in a flow network?
- ADijkstra's algorithm
- BKruskal's algorithm
- CFord-Fulkerson algorithm
- DPrim's algorithm
5.In the context of network flow, what is a 'residual graph'?
- AA graph representing the minimum spanning tree.
- BA graph representing the shortest path between nodes.
- CA graph used to detect cycles.
- DA graph showing the remaining capacities of edges after flow has been assigned.
6.What is the time complexity of Dijkstra's algorithm using a priority queue?
- AO(V^2)
- BO(V + E log V)
- CO(V log V + E log V)
- DO(E log V)
7.Which algorithm can be used to detect negative weight cycles in a graph?
- AFloyd-Warshall algorithm
- BDijkstra's algorithm
- CBellman-Ford algorithm
- DKruskal's algorithm
8.What is the main difference between Dijkstra's and Bellman-Ford algorithms?
- ADijkstra's algorithm works with negative weights, Bellman-Ford does not.
- BBellman-Ford works with negative weights, Dijkstra's does not.
- CDijkstra's algorithm is used for unweighted graphs, Bellman-Ford for weighted graphs.
- DBellman-Ford is used for unweighted graphs, Dijkstra's for weighted graphs.
9.What is the purpose of the Edmonds-Karp algorithm?
- ATo find the shortest path in a graph.
- BTo detect cycles in a graph.
- CTo find the maximum flow in a flow network using the BFS approach.
- DTo find the minimum spanning tree of a graph.
10.Which graph algorithm can be used to find all pairs shortest paths?
- AFloyd-Warshall algorithm
- BBellman-Ford algorithm
- CDijkstra's algorithm
- DKruskal's algorithm
11.What is the time complexity of the Floyd-Warshall algorithm?
- AO(E log V)
- BO(V + E)
- CO(V^3)
- DO(V^2)
12.In a flow network, what is a 'cut'?
- AA path from source to sink.
- BA cycle in the network.
- CA set of edges with maximum capacity.
- DA partition of the vertices into two disjoint subsets.
13.Which algorithm is used to find the minimum cut in a flow network?
- ADijkstra's algorithm
- BKarger's algorithm
- CFord-Fulkerson algorithm
- DBellman-Ford algorithm
14.What is the main advantage of using the Bellman-Ford algorithm over Dijkstra's algorithm?
- AIt can handle graphs with negative weight edges.
- BIt uses less memory.
- CIt is faster for all types of graphs.
- DIt is easier to implement.
15.What is the primary goal of the network flow problem?
- ATo find the shortest path between two nodes.
- BTo detect cycles in a graph.
- CTo find the maximum flow from a source to a sink in a flow network.
- DTo find the minimum spanning tree of a graph.