★ Must-know
📌 A tentative label is an unconfirmed distance estimate, whereas a permanent label is a confirmed shortest distance.
Further detail
Tentative labels are unconfirmed; permanent labels are confirmed shortest distances.
★ Must-know
📐 Formula - The relaxation rule is , where the estimate for vertex is compared with the distance to plus the weight of edge .
Further detail
Initialize, choose, relax, repeat, then trace predecessors.
★ Must-know
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:
★ 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:
The flooding revision cues are:
Dijkstra selects a shortest route; flooding sends copies along eligible lines.
Dijkstra and Flooding Comparison
| Dimension | Dijkstra | Flooding |
|---|---|---|
| Purpose | Find shortest paths from one source to destinations | Forward packets through eligible outgoing lines |
| Working method | Uses tentative and permanent distance labels | Forwards an incoming packet on outgoing lines except its arrival line |
| Route selection | Selects shortest paths using edge weights | Uses all eligible lines, or selected directions with selective flooding |
| Information used | Source distances, edge weights, and adjacent vertices | Static routing and local knowledge |
| Packet forwarding | Selects a route based on shortest-path distances | Duplicates forwarding across eligible outgoing lines |
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?
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.
Upload your class notes and Revizly writes a study guide, a quiz and flashcards in about a minute.
Study guide maker