Dijkstra and Flooding Algorithms Practice Quiz (9 questions)

All questions and answers

1. A delivery route between two network vertices is considered a shortest path when what condition is met?

Its final edge has the smallest weight among route edges
Its total edge weight is minimal among routes between the vertices
Its total edge weight is maximal among routes between the vertices
It contains the fewest edges among routes between the vertices

Its total edge weight is minimal among routes between the vertices

Explanation

A shortest path minimizes the sum of the weights of its edges; having fewer edges or a light final edge does not by itself guarantee the smallest total weight.

2. What does Dijkstra’s algorithm determine when run from a chosen source vertex?

Shortest paths from that source to all destination vertices
A shortest path from that source to one specified destination
Shortest paths between every pair of vertices
Maximum-weight paths from that source to all destination vertices

Shortest paths from that source to all destination vertices

Explanation

Dijkstra’s algorithm computes shortest paths from one source to all destination vertices. A single-destination result and an all-pairs computation describe different scopes.

3. During a Dijkstra run, vertex P has a tentative label of 8, while vertex Q has just been selected and its label confirmed as 6. How should these labels be interpreted?

Both distances are confirmed because both labels have numeric values
P’s distance is confirmed, while Q’s remains an unconfirmed estimate
P’s distance remains an unconfirmed estimate, while Q’s is a confirmed shortest distance
Both distances are unconfirmed until every vertex has been processed

P’s distance remains an unconfirmed estimate, while Q’s is a confirmed shortest distance

Explanation

A tentative label is an unconfirmed distance estimate, whereas a permanent label is a confirmed shortest distance. A finite value alone does not make a label permanent, and the smaller value does not determine label status.

4. A network has source S and several unprocessed vertices. Which sequence correctly describes the next stages of Dijkstra’s algorithm?

Initialize S to 0 and others to infinity; select the smallest tentative label, make it permanent, then examine adjacent vertices without relaxing them
Initialize all vertices to infinity; select the largest tentative label, relax adjacent vertices, and repeat
Initialize S to 0 and others to infinity; examine adjacent vertices, make them permanent, then select the smallest tentative label and repeat
Initialize S to 0 and others to infinity; select the smallest tentative label, examine adjacent vertices, relax labels, make the selected label permanent, and repeat

Initialize S to 0 and others to infinity; select the smallest tentative label, examine adjacent vertices, relax labels, make the selected label permanent, and repeat

Explanation

Dijkstra initializes the source to zero and other distances to infinity, then repeatedly selects the smallest tentative label, examines adjacent vertices, relaxes their labels, and makes the selected label permanent. The alternatives change the initialization, selection, or relaxation order.

5. For an edge from U to V, the current estimate is D(V)=11D(V)=11, the distance to U is D(U)=7D(U)=7, and the edge weight is w(U,V)=3w(U,V)=3. What estimate results from applying relaxation?

D(V)=14D(V)=14
D(V)=10D(V)=10
D(V)=3D(V)=3
D(V)=11D(V)=11

$$D(V)=10$$

Explanation

Relaxation compares the current estimate with the route through U: min⁡(11,7+3)=min⁡(11,10)=10\min(11,7+3)=\min(11,10)=10. Adding the current estimate, keeping the larger value, or using the edge weight alone does not apply the rule.

6. A router receives a packet on link L1. Under flooding, how should it forward that packet?

Only on the outgoing link with the lowest cost
On every outgoing link except L1
On L1 and every other outgoing link
On one randomly selected outgoing link

On every outgoing link except L1

Explanation

Flooding forwards an incoming packet across every outgoing line other than the one on which it arrived. Choosing a lowest-cost link confuses flooding with route selection; sending it back on L1 ignores the arrival-link exclusion; choosing one random link is not flooding’s distribution rule.

7. A network begins flooding packets without duplicate control. What is the most likely effect as packets spread through the network?

Packets follow one fixed route and reduce network traffic
Routers automatically remove duplicates before forwarding
Duplicate packets and possible loops increase network traffic
Packets avoid loops and reduce traffic as they spread

Duplicate packets and possible loops increase network traffic

Explanation

Flooding can create duplicate packets and loops, which increase network traffic. A single fixed route describes another routing behavior; automatic duplicate removal is not guaranteed by flooding; and flooding does not inherently prevent loops or reduce traffic.

8. A network task asks for shortest paths from one source to destinations, while another task distributes each incoming packet across eligible outgoing lines. Which pairing correctly identifies the methods?

Flooding distributes packets; Dijkstra replicates each packet
Flooding finds shortest paths; Dijkstra distributes packets
Dijkstra finds shortest paths; flooding distributes packets
Dijkstra finds shortest paths; flooding selects one best route

Dijkstra finds shortest paths; flooding distributes packets

Explanation

Dijkstra determines shortest paths from one source to destinations, whereas flooding distributes incoming packets across eligible outgoing lines. Reversing the methods swaps their purposes; treating flooding as a shortest-path calculation confuses distribution with route computation; describing Dijkstra as packet replication confuses path selection with forwarding behavior.

9. During a shortest-path calculation, a node's distance label has not yet been confirmed. Which revision cue describes that label?

Dijkstra
Permanent
Relaxation
Tentative

Tentative

Explanation

A tentative label is not confirmed, while a permanent label indicates that the shortest distance is confirmed. Relaxation means updating a shorter distance, and Dijkstra names the shortest-route method rather than this label status.

Study with flashcards

Lock in the answers with 27 flashcards on Dijkstra and Flooding Algorithms.

What is a shortest path between vertices?

A route with minimal total edge weight.

What does Dijkstra’s algorithm find from one source vertex?

Shortest paths to all destination vertices.

What does a tentative label represent?

An unconfirmed distance estimate.

See the flashcards →

Read the study guide

Go over the full study guide for Dijkstra and Flooding Algorithms.

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