Study guide: Dijkstra and Flooding Algorithms

Course Outline

  1. Shortest Paths and Dijkstra
  2. Dijkstra Relaxation and Path Recovery
  3. Flooding and Duplicate Control
  4. Algorithm Comparison and Revision

1. Shortest Paths and Dijkstra

Key Concepts & Definitions

  • Shortest path: A route between vertices whose total edge weight is minimal.
  • Dijkstra algorithm: An algorithm that finds shortest paths from one source vertex to all destination vertices.
  • Edge weight: The value assigned to an edge and used to measure its contribution to a path's total weight.

★ Must-know

📌 A tentative label is an unconfirmed distance estimate, whereas a permanent label is a confirmed shortest distance.

Further detail

  • A shortest path contains at most n−1n-1 edges because a path containing a cycle cannot be shortest.

Memory Hook

Tentative labels are unconfirmed; permanent labels are confirmed shortest distances.

2. Dijkstra Relaxation and Path Recovery

★ Must-know

  • Dijkstra's algorithm initializes the source distance to 0 and every other distance to infinity, selects the working vertex with the smallest tentative label, examines its adjacent vertices, relaxes their labels, makes the selected label permanent, and repeats until destinations are processed.

📐 Formula - The relaxation rule is D(v)=min⁡(D(v),D(u)+w(u,v))D(v)=\min(D(v),D(u)+w(u,v)), where the estimate for vertex vv is compared with the distance to uu plus the weight of edge (u,v)(u,v).

Further detail

  • The final path is reconstructed by tracing predecessor or probe nodes backward from the destination to the source.

Memory Hook

Initialize, choose, relax, repeat, then trace predecessors.

3. Flooding and Duplicate Control

Key Concepts & Definitions

  • Flooding: A routing method in which a router forwards an incoming packet on every outgoing line except the line on which the packet arrived.
  • Selective flooding: A flooding method that forwards packets only through outgoing lines approximately in the correct direction.

★ Must-know

  • Flooding can create duplicate packets, loops, and increased network traffic.

Further detail

  • Flooding uses static routing and local knowledge at each router.

  • A hop counter is placed in the packet header, decremented at every hop, and the packet is discarded when the counter reaches zero.

  • 🔄 Sequence-number control works as follows:

    1. The source assigns a sequence number to each packet.
    2. Routers maintain lists of received packets.
    3. Routers discard packets identified as duplicates.

4. Algorithm Comparison and Revision

★ Must-know

📌 Dijkstra determines shortest paths from one source to destinations, whereas flooding distributes incoming packets across eligible outgoing lines.

Further detail

  • The Dijkstra revision cues are:

    • Dijkstra: shortest route
    • Relaxation: update a shorter distance
    • Tentative: not confirmed
    • Permanent: shortest distance confirmed
  • The flooding revision cues are:

    • Flooding: send through all eligible outgoing lines
    • Hop counter: limits hops
    • Sequence number: detects duplicates
    • Selective flooding: selected directions only

Memory Hook

Dijkstra selects a shortest route; flooding sends copies along eligible lines.

Synthesis Tables

Dijkstra and Flooding Comparison

DimensionDijkstraFlooding
PurposeFind shortest paths from one source to destinationsForward packets through eligible outgoing lines
Working methodUses tentative and permanent distance labelsForwards an incoming packet on outgoing lines except its arrival line
Route selectionSelects shortest paths using edge weightsUses all eligible lines, or selected directions with selective flooding
Information usedSource distances, edge weights, and adjacent verticesStatic routing and local knowledge
Packet forwardingSelects a route based on shortest-path distancesDuplicates forwarding across eligible outgoing lines

Test yourself

Take a 9-question practice quiz on Dijkstra and Flooding Algorithms, with every answer explained.

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 →

Study with flashcards

Memorize the key concepts of Dijkstra and Flooding Algorithms with 27 flashcards.

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 →

Related classes

Make your own study guides

Upload your class notes and Revizly writes a study guide, a quiz and flashcards in about a minute.

Study guide maker