Finite Mathematics Quiz: Shortest Paths
7 questions · exam conditions
0:00
Shortest PathsQuestion 1 of 7

A network has 6 vertices connected in a specific topology. When finding shortest paths from vertex 1 to all other vertices using breadth-first search (assuming unit edge weights), the algorithm processes vertices in this order: 1, 2, 3, 4, 5, 6. The shortest path distances found are: to vertex 2 (distance 1), to vertex 3 (distance 1), to vertex 4 (distance 2), to vertex 5 (distance 2), to vertex 6 (distance 3). Which property must be true about the network topology?

Vertex 1 has exactly 2 neighbors, and the network forms a tree structure with no cycles
Vertices 2 and 3 are directly connected to vertex 1, and vertex 6 has exactly one neighbor
The network contains exactly one cycle, and vertex 6 is a leaf node connected to vertex 5
Vertices 2 and 3 are adjacent to vertex 1, but the connectivity of vertex 6 cannot be determined
← Back to quizzes

Finite Mathematics Quiz

Finite Mathematics Quiz: Shortest Paths

Practice Shortest Paths in Finite Mathematics with focused quiz questions that help you check what you know, review explanations, and build confidence with test-style prompts.

What this quiz covers

This quiz focuses on Shortest Paths, giving you a quick way to practice the rules, question types, and explanations that matter most for Finite Mathematics.

How to use this quiz

Try each quiz question before looking at the correct answer. Use the explanations to review missed ideas, then come back to similar questions until the pattern feels familiar.

All questions

Question 1

A network has 6 vertices connected in a specific topology. When finding shortest paths from vertex 1 to all other vertices using breadth-first search (assuming unit edge weights), the algorithm processes vertices in this order: 1, 2, 3, 4, 5, 6. The shortest path distances found are: to vertex 2 (distance 1), to vertex 3 (distance 1), to vertex 4 (distance 2), to vertex 5 (distance 2), to vertex 6 (distance 3). Which property must be true about the network topology?

  1. Vertex 1 has exactly 2 neighbors, and the network forms a tree structure with no cycles
  2. Vertices 2 and 3 are directly connected to vertex 1, and vertex 6 has exactly one neighbor
  3. The network contains exactly one cycle, and vertex 6 is a leaf node connected to vertex 5
  4. Vertices 2 and 3 are adjacent to vertex 1, but the connectivity of vertex 6 cannot be determined (correct answer)
Explanation: From the BFS results, we know vertices 2 and 3 are distance 1 from vertex 1, so they're directly connected to vertex 1. Vertex 6 is distance 3, meaning it's reachable via a path of length 3, but this doesn't determine its exact connectivity - it could be connected to vertex 4, 5, or even have multiple connections. Choice A incorrectly assumes a tree and that vertex 1 has exactly 2 neighbors. Choice B makes unfounded claims about vertex 6's degree. Choice C assumes specific structural properties not supported by the given information.

Question 2

Consider a weighted directed graph where the shortest path from A to E passes through vertices B, C, and D in some order. The path A→B→C→D→E has total weight 20, while A→B→D→C→E has total weight 18, and A→D→B→C→E has total weight 22. If the edge weights are all positive integers, what is the minimum possible weight for the shortest path from A to E that uses a completely different set of intermediate vertices?

  1. 17, since it must be less than the current shortest path of 18
  2. 19, representing a path that avoids vertices B, C, and D entirely
  3. Cannot be determined without knowing the complete graph structure and all edge weights (correct answer)
  4. 18, as alternative paths would likely have the same optimal weight in a well-connected graph
Explanation: The question asks for the shortest path using completely different intermediate vertices (not B, C, or D). Without knowing what other vertices exist in the graph, their connections, or the edge weights involving them, we cannot determine this path's weight. The given information only tells us about paths through B, C, and D. Choice A assumes the new path must be shorter, Choice B arbitrarily suggests 19, and Choice D incorrectly assumes equal optimal weights across different vertex sets.

Question 3

Two students implement shortest path algorithms on the same weighted graph. Student 1 reports the shortest path from S to T as S→U→V→T with distance 15. Student 2 reports the shortest path as S→W→X→T with distance 15. When they trace their algorithms step-by-step, both approaches are mathematically sound. What is the most likely explanation for these different results?

  1. One student made a computational error, as shortest paths in weighted graphs are always unique
  2. The students used different algorithms that prioritize different optimization criteria beyond just minimizing distance
  3. Multiple shortest paths of equal length exist, and the students' algorithms selected different valid solutions (correct answer)
  4. The students used different tie-breaking rules when processing vertices with equal tentative distances during execution
Explanation: When two different paths have the same total weight (15), both are equally valid shortest paths. Many graphs have multiple shortest paths between the same pair of vertices. Both students found optimal solutions. Choice A incorrectly claims shortest paths are unique. Choice B mischaracterizes shortest path algorithms as having different optimization criteria. Choice D focuses on tie-breaking during algorithm execution, but the key point is that multiple optimal solutions exist in the graph itself.

Question 4

A graph has vertices {A, B, C, D, E} where the shortest path tree rooted at A results in the following parent relationships: B's parent is A, C's parent is A, D's parent is B, E's parent is C. If the shortest distances from A are: B(3), C(4), D(7), E(9), what can be concluded about the edge weights in the original graph?

  1. Edge A-B has weight 3, edge B-D has weight 4, and the graph contains no cycles
  2. Edge A-B weighs 3, edge A-C weighs 4, edge B-D weighs 4, edge C-E weighs 5
  3. The edge weights match the shortest distances, indicating a tree topology without alternative paths
  4. Edge weights are: A-B(3), A-C(4), B-D(4), C-E(5), but other edges may exist with higher weights (correct answer)
Explanation: From the shortest path tree: A to B costs 3, so A-B weighs 3. A to C costs 4, so A-C weighs 4. A to D costs 7 via B, and B costs 3, so B-D weighs 7-3=4. A to E costs 9 via C, and C costs 4, so C-E weighs 9-4=5. However, the original graph may contain additional edges with higher weights that weren't used in the shortest path tree. Choice A gives wrong weight for B-D and makes unfounded claims about cycles. Choice B is mostly correct but doesn't acknowledge possible additional edges. Choice C incorrectly assumes tree topology.

Question 5

Using Dijkstra's algorithm to find shortest paths from vertex A in a weighted graph, after processing vertices A and B, the tentative distances are: C(7), D(12), E(9), F(∞). The next vertex to be processed is C. From C, we can reach D with weight 3 and F with weight 8. What are the updated tentative distances after processing vertex C?

  1. C(7), D(10), E(9), F(15) with all distances finalized
  2. C(processed), D(10), E(9), F(15) with C marked as processed (correct answer)
  3. C(processed), D(3), E(9), F(8) showing only direct distances from C
  4. C(processed), D(12), E(9), F(15) with no updates to existing distances
Explanation: In Dijkstra's algorithm, when processing vertex C with distance 7, we update neighbors: D gets min(12, 7+3) = 10, and F gets min(∞, 7+8) = 15. C is marked as processed. E remains 9 (not reachable from C). Choice A incorrectly suggests all distances are finalized. Choice C shows only the edge weights from C, not the total distances from A. Choice D fails to update the distances, which violates the algorithm.

Question 6

The 'principle of optimality' is fundamental to finding shortest paths. It states that if P is a shortest path from a vertex U to a vertex V, and W is any intermediate vertex on P, then a certain property must hold. Based on this principle, which of the following statements is always true?

  1. The subpath of P from U to W is one of possibly several shortest paths from U to W. (correct answer)
  2. The subpath of P from U to W will always contain fewer edges than any other path from U to W.
  3. No other path from U to V can have the same number of intermediate vertices as P.
  4. The subpath of P from W to V is the only shortest path from W to V.
Explanation: The principle of optimality states that any subpath of a shortest path is itself a shortest path. Therefore, if P is a shortest path from U to V passing through W, the portion of P from U to W must be a shortest path from U to W, and the portion from W to V must be a shortest path from W to V. Choice A correctly states this. It also correctly includes the nuance that this subpath may not be unique; there could be other paths from U to W with the same minimum length. Choice B is incorrect because shortest path refers to total weight, not the number of edges. A path with more edges can have a smaller total weight. Choice C is incorrect because another path could exist with the same number of edges but a greater weight. Choice D is incorrect because it claims uniqueness; the subpath from W to V is a shortest path, but not necessarily the only one.

Question 7

In a network routing problem, the shortest path from router R1 to router R5 must avoid router R3 due to security restrictions. The available paths with their costs are: R1→R2 (cost 4), R2→R4 (cost 6), R2→R5 (cost 12), R1→R4 (cost 9), R4→R5 (cost 3), and R1→R6→R5 (total cost 14). After computing the shortest valid path, network administrators add a new direct link R1→R5 with cost 11. How does this addition affect the optimal routing decision?

  1. The new link becomes the shortest path, reducing total cost from 12 to 11 (correct answer)
  2. The new link provides an alternative but doesn't change the optimal route cost of 12
  3. The optimal path remains R1→R4→R5 with cost 12, as it's still shorter than the new direct link
  4. The new link is suboptimal compared to the existing best path R1→R2→R4→R5 with cost 13
Explanation: Initially, avoiding R3, the possible paths are: R1→R2→R5 (4+12=16), R1→R4→R5 (9+3=12), R1→R2→R4→R5 (4+6+3=13), and R1→R6→R5 (14). The shortest is R1→R4→R5 with cost 12. Adding the direct link R1→R5 with cost 11 creates a new shortest path that improves upon the previous optimum of 12.