Shortest Paths and Flooding Practice Quiz (8 questions)

All questions and answers

1. In a weighted graph, what makes one path between two nodes a shortest path?

It has the minimum total edge weight among paths between those nodes.
It has the smallest final-edge weight among paths between those nodes.
It has the fewest edges among paths between those nodes.
It has the maximum total edge weight among paths between those nodes.

It has the minimum total edge weight among paths between those nodes.

Explanation

A shortest path minimizes the sum of the weights of its edges. Choosing by edge count or by a single edge does not necessarily minimize that total.

2. A simple path is sought between two nodes in a graph with nn vertices. What is the greatest number of edges it can contain?

At least n−1n-1 edges, to ensure all vertices are visited.
At most n−2n-2 edges, since both endpoint edges are excluded.
At most nn edges, since each vertex can contribute one edge.
At most n−1n-1 edges, since a path with a cycle could be shortened.

At most $$n-1$$ edges, since a path with a cycle could be shortened.

Explanation

A shortest path cannot contain a cycle, so it cannot revisit a vertex; with nn vertices, a simple path has at most n−1n-1 edges. The nn and n−2n-2 alternatives miscount the maximum edge count, while the lower-bound claim incorrectly requires visiting all vertices.

3. What problem does Dijkstra's algorithm solve when run from a chosen source node?

Finds a minimum spanning tree connecting all nodes.
Finds shortest paths between every pair of nodes without selecting a source.
Finds shortest paths from that source to all destinations.
Finds a path with the fewest edges from the source to one destination.

Finds shortest paths from that source to all destinations.

Explanation

Dijkstra's algorithm computes shortest paths from one source to all destinations. An all-pairs method, a fewest-edges objective, and a minimum spanning tree are different tasks.

4. At the start of Dijkstra's algorithm, a network has source node S and other nodes A and B. Which distance labels should be assigned?

S: infinity; A: 0; B: 0.
S: 1; A: infinity; B: infinity.
S: 0; A: 0; B: 0.
S: 0; A: infinity; B: infinity.

S: 0; A: infinity; B: infinity.

Explanation

Initialization assigns distance zero to the source and infinity to every other node because no routes to those nodes have yet been established. Setting all labels to zero, reversing the source assignment, or using an unsupported finite value misstates this initialization.

5. What does the flooding algorithm do with an incoming packet at a node?

Forwards it along the outgoing line with the lowest edge weight
Sends it toward the destination using a confirmed shortest route
Keeps it at the node until a duplicate packet is detected
Forwards it on every outgoing line except the one it arrived on

Forwards it on every outgoing line except the one it arrived on

Explanation

Flooding forwards an incoming packet on all outgoing lines other than its arrival line. Choosing a lowest-weight line describes a route-selection approach, not flooding’s broad forwarding rule.

6. Which distinction between Dijkstra's algorithm and flooding is central to comparing their routing behavior?

Dijkstra limits packet travel by hop count, while flooding updates distances by relaxation.
Dijkstra forwards packets through all outgoing lines, while flooding selects the shortest route.
Dijkstra detects duplicate packets, while flooding confirms shortest-distance labels.
Dijkstra selects shortest routes, while flooding forwards packets through all eligible outgoing lines.

Dijkstra selects shortest routes, while flooding forwards packets through all eligible outgoing lines.

Explanation

Dijkstra is used to select shortest routes, whereas flooding sends packets through all eligible outgoing lines. Hop counters can limit flooding, but they do not define Dijkstra's routing behavior.

7. What is the role of edge weights when determining a shortest path in a weighted graph?

They provide the values summed to compare the total cost of candidate paths.
They identify which vertices can serve as the source of a route.
They indicate how many vertices a path is allowed to visit.
They record the order in which edges were added to the graph.

They provide the values summed to compare the total cost of candidate paths.

Explanation

Edge weights contribute to a path’s total weight, and the shortest path is the one with the minimum total. The number of vertices visited does not define the path’s weight.

8. How does Dijkstra’s algorithm use distance information differently from flooding when handling routes through a network?

Dijkstra selects routes by hop count, while flooding confirms shortest distances from a chosen source.
Dijkstra forwards each packet across eligible outgoing lines, while flooding compares weighted candidate distances.
Dijkstra updates candidate distances using edge weights, while flooding forwards packets across eligible outgoing lines.
Dijkstra records packet sequence numbers, while flooding reconstructs routes from predecessor nodes.

Dijkstra updates candidate distances using edge weights, while flooding forwards packets across eligible outgoing lines.

Explanation

Dijkstra uses edge weights to update candidate distances and identify shortest routes, whereas flooding propagates packets along eligible outgoing lines. Flooding’s forwarding behavior is not a comparison of weighted candidate distances.

Study with flashcards

Lock in the answers with 8 flashcards on Shortest Paths and Flooding.

What defines a shortest path between nodes?

It has the minimum total edge weight.

What does Dijkstra's algorithm find from one source?

Shortest paths to all destinations.

What initial distances does Dijkstra's algorithm assign to the source and other nodes?

Zero for the source and infinity for every other node.

See the flashcards →

Read the study guide

Go over the full study guide for Shortest Paths and Flooding.

Read the study guide →

Related classes

Make your own practice quizzes

Upload your class notes and Revizly writes a practice quiz with explained answers in about a minute.

Quiz maker