Dijkstra and Flooding Algorithms Flashcards (27 cards)

All cards

1Question

What is a shortest path between vertices?

Answer

A route with minimal total edge weight.

2Question

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

Answer

Shortest paths to all destination vertices.

3Question

What does a tentative label represent?

Answer

An unconfirmed distance estimate.

4Question

What does a permanent label represent?

Answer

A confirmed shortest distance.

5Question

How does Dijkstra's algorithm initialize vertex distances?

Answer

The source gets distance 0; every other vertex gets infinity.

6Question

How does Dijkstra's algorithm choose its next working vertex?

Answer

It selects the vertex with the smallest tentative label.

7Question

What does Dijkstra's algorithm do after selecting a working vertex?

Answer

It examines adjacent vertices and relaxes their labels.

8Question

When does Dijkstra's algorithm make a selected label permanent?

Answer

After examining the selected vertex's adjacent vertices.

9Question

What is the relaxation rule for updating vertex vv through vertex uu?

Answer

D(v)=min⁡(D(v),D(u)+w(u,v))D(v)=\min(D(v),D(u)+w(u,v))

10Question

How does flooding forward an incoming packet at each router?

Answer

On every outgoing line except the arrival line.

11Question

What three effects can flooding cause?

Answer

Duplicate packets, loops, and increased network traffic.

12Question

What does flooding do with incoming packets?

Answer

Distributes them across eligible outgoing lines.

13Question

What does an edge weight measure in a path?

Answer

The edge’s contribution to the path’s total weight.

14Question

How many edges can a shortest path contain at most in a graph with nn vertices?

Answer

n−1n-1 edges.

15Question

Why can a path containing a cycle not be shortest?

Answer

Removing the cycle yields a shorter path.

16Question

How is the final path reconstructed from destination to source?

Answer

Trace predecessor or probe nodes backward from the destination to the source.

17Question

What routing approach and knowledge does flooding use at each router?

Answer

Static routing and local knowledge.

18Question

What happens to a packet when its hop counter reaches zero?

Answer

The packet is discarded.

19Question

How does a packet’s hop counter change during forwarding?

Answer

It is decremented at every hop.

20Question

How does sequence-number control identify packets already received?

Answer

Routers maintain lists of received packets.

21Question

What do routers do with duplicate packets under sequence-number control?

Answer

They discard duplicate packets.

22Question

Which outgoing lines does selective flooding use?

Answer

Lines approximately in the correct direction.

23Question

What does Dijkstra mean in the final revision cues?

Answer

Shortest route.

24Question

What does relaxation mean in the final revision cues?

Answer

Updating a shorter distance.

25Question

What does tentative mean in the final revision cues?

Answer

Not confirmed.

26Question

What does flooding do in the final revision cues?

Answer

Sends packets through all eligible outgoing lines.

27Question

What does a hop counter limit in the final revision cues?

Answer

The number of hops.

Test yourself with the quiz

Answer 9 questions on Dijkstra and Flooding Algorithms.

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

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

Take the quiz →

Read the study guide

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

Read the study guide →

Related classes

Make your own flashcards

Upload your class notes and Revizly writes your flashcards in about a minute.

Flashcard maker