Introduction to Shortest Path & Network Flow Algorithms
Explore the basics of shortest path and network flow algorithms in graph theory.
Questions in this quiz
15 questions on Introduction to Shortest Path & Network Flow Algorithms. Work through them here, then start the quiz to answer them and see your score.
1.What is the primary goal of Dijkstra's algorithm?
- ATo find the longest path in a graph
- BTo find the shortest path from a single source to all vertices
- CTo detect cycles in a graph
- DTo find the minimum spanning tree
2.Which data structure is commonly used to implement Dijkstra's algorithm efficiently?
- ALinked List
- BStack
- CQueue
- DPriority Queue
3.What is the main difference between Dijkstra's algorithm and Bellman-Ford algorithm?
- ABoth can handle negative weights
- BNeither can handle negative weights
- CBellman-Ford can handle negative weights, Dijkstra's cannot
- DDijkstra's can handle negative weights, Bellman-Ford cannot
4.In the context of network flow, what does 'capacity' refer to?
- AThe shortest path length
- BThe maximum number of nodes in a graph
- CThe total number of edges in a graph
- DThe maximum flow that can pass through an edge
5.What is the purpose of the Ford-Fulkerson method?
- ATo find the minimum spanning tree
- BTo detect cycles in a graph
- CTo find the maximum flow in a flow network
- DTo find the shortest path in a graph
6.Which algorithm is used to find the shortest path in an unweighted graph?
- ADijkstra's algorithm
- BDepth-First Search
- CBellman-Ford algorithm
- DBreadth-First Search
7.What is the time complexity of Dijkstra's algorithm using a priority queue?
- AO(V log V)
- BO(V + E log V)
- CO(V^2)
- DO(E^2)
8.In network flow algorithms, what is an 'augmenting path'?
- AA path that has no flow
- BA path that forms a cycle
- CA path that decreases the flow
- DA path that increases the flow
9.Which algorithm is used to find the shortest path in a graph with negative weight edges?
- ABellman-Ford algorithm
- BPrim's algorithm
- CKruskal's algorithm
- DDijkstra's algorithm
10.What is the main limitation of the Ford-Fulkerson method?
- AIt cannot find maximum flow
- BIt is only applicable to undirected graphs
- CIt cannot handle negative weights
- DIt requires integer capacities
11.Which of the following is a common application of network flow algorithms?
- AFinding the shortest path
- BFinding the minimum spanning tree
- CCycle detection
- DJob scheduling
12.What is the Edmonds-Karp algorithm an implementation of?
- AKruskal's algorithm
- BBellman-Ford algorithm
- CDijkstra's algorithm
- DFord-Fulkerson method
13.Which algorithm is used to find the shortest path in a graph with both positive and negative weight edges, but no negative cycles?
- ABellman-Ford algorithm
- BFloyd-Warshall algorithm
- CPrim's algorithm
- DDijkstra's algorithm
14.What is the time complexity of the Bellman-Ford algorithm?
- AO(V^2)
- BO(E^2)
- CO(V + E)
- DO(VE)
15.Which of the following algorithms can be used to detect negative weight cycles in a graph?
- APrim's algorithm
- BDijkstra's algorithm
- CBellman-Ford algorithm
- DKruskal's algorithm