# Dijkstra algorithm

> Source: Courseiva IT Certification Glossary — https://courseiva.com/glossary/dijkstra-algorithm

## Quick definition

The Dijkstra algorithm helps routers find the best way to send data across a network. It looks at all possible paths and picks the one with the lowest total cost, like choosing the fastest route on a road trip. This algorithm is the core of how OSPF, a common routing protocol, builds its routing table.

## Simple meaning

Imagine you are planning a road trip across a country with many cities connected by highways. You want to drive from your home town to a friend's city, and you want the shortest possible trip in terms of total miles. There might be many different routes to take, some going through many small towns, others using a big highway. You could try each route one by one and measure the distance, but that would take forever. Instead, you could use a clever method: start at your home town and mark the distance to each directly connected city. Then, from those cities, you look at their neighbors, adding up the distances. You always move to the city with the smallest total distance so far, and you keep doing this until you have found the shortest distance to every city, including your friend's city. That systematic method is the Dijkstra algorithm. In the world of computer networks, routers use this same idea to find the best paths for data packets. Each connection between routers has a cost, which might be based on speed, reliability, or other factors. The Dijkstra algorithm lets each router build a map of the entire network and then calculate the lowest-cost path to every other router. It does this step by step, making sure it always has the optimal route without wasting time checking every possible path. This is why OSPF and other link-state routing protocols are so efficient at adapting to network changes while using minimal processing power.

## Technical definition

The Dijkstra algorithm, also known as the shortest path first (SPF) algorithm, is a fundamental graph-theoretic algorithm used in routing protocols, most notably Open Shortest Path First (OSPF). Its primary function is to compute the shortest path tree from a source node (the router itself) to all destinations in a network graph, where each link has an associated cost. The algorithm was conceived by computer scientist Edsger W. Dijkstra in 1956 and published in 1959. In the context of OSPF, each router maintains a Link State Database (LSDB) that contains a complete and synchronized description of the network topology. All routers in an OSPF area have identical LSDBs. When a router runs the Dijkstra algorithm on its LSDB, it constructs a directed acyclic graph known as the Shortest Path Tree (SPT). The SPT is rooted at the calculating router and shows the lowest-cost path to every reachable network prefix. The algorithm works through an iterative process. It begins by initializing a set of candidate nodes. The source node (the router itself) is assigned a cost of zero. All other nodes are assigned an infinite initial cost. The algorithm then repeatedly selects the node with the lowest cost from the set of unvisited nodes. It marks that node as visited, examines all of its neighbors, and updates their costs if a cheaper path is found via the current node. This process continues until all nodes in the network have been visited. The result is that each router knows exactly the next-hop neighbor to use to reach any destination with the lowest cumulative cost. OSPF uses this algorithm to calculate routes for IPv4 (OSPFv2) and IPv6 (OSPFv3). The cost metric is typically derived from the interface bandwidth, with the formula cost = reference bandwidth / interface bandwidth, where the reference bandwidth is often 100 Mbps. This means a 100 Mbps link has a cost of 1, while a 1 Gbps link would have a cost of 0.1 (but OSPF works with integer costs, so the reference may be higher). The Dijkstra algorithm is deterministic: given the same LSDB, all routers within an area will compute exactly the same SPT, ensuring loop-free routing. However, the algorithm can be resource-intensive on large networks with many routers, which is why OSPF uses areas to limit the size of the LSDB. The computational complexity of the original algorithm is O(|V|^2), where |V| is the number of nodes, but with a binary heap implementation, it can be reduced to O(|E| log |V|), where |E| is the number of edges. Practical implementations in routers also include optimizations like incremental SPF (iSPF) to avoid recalculating the entire tree after minor topology changes.

## Real-life example

Think of a large postal delivery network. You have a central sorting hub (your router) and many local post offices (other routers) spread across a city. Trucks move mail between these hubs every night. Each road between two hubs has a certain length or travel time, which is like the cost of a link in a network. Your job as the sorting hub manager is to figure out the quickest route for a package to reach any local post office. You cannot just send the package on a random road and hope for the best. Instead, you pull out a map that shows every hub and the roads between them, similar to the OSPF link-state database. You start at your own hub and mark the travel time to each directly connected hub. For example, Hub A is 10 minutes away, Hub B is 15 minutes away. You then go to the hub with the smallest travel time, Hub A, and look at its neighbors. You find that from Hub A, you can reach Hub C in another 5 minutes, so the total time to Hub C via Hub A is 15 minutes. That matches the direct time to Hub B. You then move to Hub B and see that from Hub B you can reach Hub C in 2 minutes, making the total time 17 minutes, which is worse than the 15 minutes you already had. So you keep the better route. You continue this process, always picking the hub with the smallest known travel time that you haven't fully explored yet, until you have found the best travel time to every hub. In the real world, if a road is closed or a new expressway opens, you get an updated map and run the same process again. This is exactly how OSPF routers react to network changes. They exchange link-state advertisements (LSAs) to update the LSDB, then rerun the Dijkstra algorithm to recalculate the shortest path tree. The algorithm ensures that each packet takes the most efficient route through the postal network, avoiding traffic jams and road closures, just like data packets avoid congested or failed links.

## Why it matters

In modern enterprise and service provider networks, OSPF is one of the most widely deployed interior gateway protocols (IGPs). The Dijkstra algorithm is the engine that makes OSPF intelligent and efficient. Without it, routers would have to rely on simpler distance-vector algorithms, which can be slower to converge and prone to routing loops. The Dijkstra algorithm gives OSPF the ability to converge quickly when the network topology changes. When a link goes down or a new router is added, OSPF routers flood LSAs to inform all other routers in the area. Each router then recalculates the shortest path tree using the Dijkstra algorithm and updates its routing table. This entire process can take less than a second in a well-designed network. Another reason the algorithm matters is that it guarantees loop-free routing. Because the shortest path tree provides a consistent view from every router, there is no risk of a packet bouncing between routers endlessly. This is critical for reliable data delivery, especially in networks carrying voice over IP or other real-time traffic. Network engineers also use the algorithm's output to troubleshoot performance issues. If a link is congested, they can adjust the OSPF cost manually to influence the Dijkstra calculation, steering traffic away from that link. This gives administrators fine-grained control over traffic flow without needing to change physical connections. The algorithm also supports load balancing: if two or more paths have equal cost, OSPF can place them into the routing table and distribute traffic across them. Understanding the Dijkstra algorithm is therefore essential for anyone who works with OSPF, whether configuring it on Cisco routers, designing a network, or preparing for certification exams.

## Why it matters in exams

The Dijkstra algorithm is a core concept in the Cisco CCNA (200-301) exam, particularly under the section on routing protocols. While the exam does not typically require you to manually run the algorithm step by step on paper, a solid understanding of how it works is essential for interpreting OSPF behavior. CCNA exam objectives include explaining how OSPF uses the SPF algorithm to calculate the shortest path and how it maintains a loop-free topology. You may see questions that ask you to determine the next-hop router or exit interface for a given destination based on OSPF costs. For example, you might be given a network diagram with link costs and asked which path a packet will take. Without understanding the Dijkstra algorithm, you cannot reliably answer such questions. The exam may also include troubleshooting scenarios where OSPF is not converging properly. You might need to identify issues like a mismatched link cost that causes suboptimal routing, or an incorrect link-state database that prevents the Dijkstra algorithm from calculating correct routes. In advanced topics, multiple paths with equal cost trigger OSPF ECMP (equal-cost multi-path), and the exam expects you to know that the Dijkstra algorithm identifies those equal-cost paths. The exam touches on OSPF areas. The reason OSPF uses areas is to limit the size of the LSDB, which in turn limits the computational burden of running the Dijkstra algorithm. Questions might ask why large networks require OSPF areas or what happens when the LSDB grows too large. For the Cisco CCNP Enterprise (350-401 ENCOR) exam, the Dijkstra algorithm is covered in more depth. You might be expected to understand incremental SPF, the impact of different LSA types on the SPF calculation, and how OSPF fast convergence features like SPF throttling work. The algorithm is also relevant in the context of IS-IS, another link-state protocol that uses the same fundamental SPF algorithm. Overall, the Dijkstra algorithm appears in both theoretical and practical question formats across multiple certification levels. Mastery of it is not optional for anyone aiming to pass and understand real-world networking.

## How it appears in exam questions

On the CCNA exam, you can expect several types of questions involving the Dijkstra algorithm. One common type is scenario-based questions where you are given a network diagram with routers and links, each link labeled with an OSPF cost. The question might ask: 'After OSPF converges, which path will packets take from Router A to Router H?' To answer, you must mentally simulate the Dijkstra algorithm, adding costs along possible paths and selecting the one with the lowest total cost. Another pattern is configuration-based: 'An OSPF router has been configured. Which command would you use to verify the OSPF routes calculated by the SPF algorithm?' The correct answer is typically 'show ip route ospf' or 'show ip ospf interface'. There are also troubleshooting questions: 'Users report intermittent connectivity. An OSPF router shows an incomplete routing table. What could prevent the Dijkstra algorithm from computing routes?' Possible answer: 'The router's LSDB is not synchronized with its neighbors, possibly due to a mismatched area ID or authentication failure.' In more advanced exams like CCNP, you might see questions about the sequence of operations during OSPF convergence. For example: 'Place the steps of OSPF operation in order: exchange LSAs, run SPF, establish adjacencies, populate routing table.' The correct order is establish adjacencies, exchange LSAs, run SPF, populate routing table. Another type asks about the impact of cost changes: 'An interface cost is changed from 10 to 20. Describe the sequence of events that occurs on all OSPF routers in the area.' This requires understanding that the router sends a new LSA, all routers update their LSDBs, rerun the Dijkstra algorithm, and update the routing table. The algorithm also appears in questions about OSPF network types, like broadcast and point-to-point, where the need for a designated router reduces the number of adjacencies and thus the processing required for the SPF calculation. You may also see questions that test your knowledge of OSPF metric calculation: 'A router has two paths to a destination, one with cost 15 and another with cost 20. How does OSPF decide which path to use?' The answer is that the Dijkstra algorithm selects the path with the lowest total cost (15). If both paths had equal cost, OSPF would load balance across them.

## Example scenario

Consider a small network with four routers: R1, R2, R3, and R4. They are connected in a partial mesh. R1 is connected to R2 with a cost of 1 and to R3 with a cost of 4. R2 is connected to R3 with a cost of 2 and to R4 with a cost of 5. R3 is connected to R4 with a cost of 1. All routers are running OSPF and belong to the same area. Our job is to find the shortest path from R1 to R4 using the Dijkstra algorithm. We start by considering R1 as the source. We initialize its cost to 0. The cost to reach R2 directly is 1, and to R3 directly is 4. These are our initial candidate routes. The smallest cost among the unvisited nodes is cost 1 to R2. So we add R2 to the shortest path tree. Now, from R2, we can reach R3 with an additional cost of 2, making the total cost to R3 via R2 equal to 1 + 2 = 3. This is lower than the direct cost of 4 from R1, so we update the cost to R3 to 3. From R2, we can also reach R4 with an additional cost of 5, giving a total cost to R4 via R2 of 1 + 5 = 6. So now the candidate costs are: R3 with cost 3, and R4 with cost 6. The smallest cost is 3 to R3, so we add R3 to the tree. From R3, we can reach R4 with an additional cost of 1, giving a total cost to R4 via R3 of 3 + 1 = 4. This is lower than the previous candidate of 6 via R2, so we update the cost to R4 to 4. There are no more unvisited nodes, so we finalize the tree. The shortest path from R1 to R4 is therefore R1 to R2 (cost 1), R2 to R3 (cost 2), R3 to R4 (cost 1), for a total cost of 4. This example shows how the algorithm systematically finds the best route, even when a seemingly longer initial hop (R1 to R2) leads to a better overall path than the direct route (R1 to R3). In a real network, the same logic applies, but with many more routers and links. Each router independently runs this algorithm to build its routing table.

## Common mistakes

- **Mistake:** Thinking the Dijkstra algorithm uses hop count as the metric.
  - Why it is wrong: OSPF uses cost, which is typically derived from bandwidth. Hop count is not the default metric. The algorithm works with any cost value, not just number of hops.
  - Fix: Remember that OSPF cost is based on the reference bandwidth divided by interface bandwidth. Always look for cost values given in the problem, not hop count.
- **Mistake:** Assuming the first path found is the shortest.
  - Why it is wrong: The Dijkstra algorithm explores multiple paths and updates the best cost as it goes. A path that looks good initially may later be replaced when a cheaper route is discovered via another node.
  - Fix: Always continue the algorithm until you have visited all nodes. Do not stop at the first path to the destination.
- **Mistake:** Confusing the Dijkstra algorithm with the Bellman-Ford algorithm used by RIP.
  - Why it is wrong: RIP uses the Bellman-Ford algorithm, which is a distance-vector approach. OSPF uses Dijkstra, which is a link-state algorithm. They have different convergence times and loop prevention mechanisms.
  - Fix: Associate OSPF with link-state and the Dijkstra algorithm. Associate RIP with distance-vector and Bellman-Ford.
- **Mistake:** Forgetting that the algorithm computes paths to all destinations, not just one.
  - Why it is wrong: The Dijkstra algorithm builds a tree from the root to all nodes. It does not stop after finding the first destination. Each router needs a route to every network in the area.
  - Fix: Remember that the output is a shortest path tree covering all routers in the area. Every router in the tree gets a computed path.

## Exam trap

{"trap":"In a network with equal-cost paths to a destination, OSPF will use only one path by default.","why_learners_choose_it":"They assume that the Dijkstra algorithm picks a single 'shortest' path and ignores others. They may be familiar with RIP's behavior of using only the best path.","how_to_avoid_it":"Know that OSPF supports equal-cost multi-path (ECMP). When the Dijkstra algorithm finds two or more paths with the same total cost, OSPF can install all of them in the routing table and load balance traffic. The default ECMP maximum paths is 4 on Cisco routers, but it can be increased up to 32."}

## Commonly confused with

- **Dijkstra algorithm vs Bellman-Ford algorithm:** Bellman-Ford is a distance-vector algorithm used by RIP. It does not require a full topology map and is simpler but slower to converge and prone to routing loops. Dijkstra uses a link-state database and converges faster. (Example: RIP routers use Bellman-Ford by sending their entire routing table to neighbors every 30 seconds, while OSPF routers use Dijkstra to build a network map and calculate routes.)
- **Dijkstra algorithm vs Spanning Tree Protocol:** Spanning Tree Protocol is used on Layer 2 switches to prevent loops in Ethernet networks by blocking redundant links. It does not calculate shortest paths based on cost in the same way as Dijkstra. OSPF uses Dijkstra at Layer 3 to determine optimal routing. (Example: In a switched network, STP blocks some switch ports to prevent loops. In a routed network, OSPF uses Dijkstra to find the best routes and uses all links if they are not in a loop.)
- **Dijkstra algorithm vs EIGRP DUAL algorithm:** EIGRP uses the Diffusing Update Algorithm (DUAL) instead of Dijkstra. DUAL is also designed for fast convergence and loop avoidance, but it is a distance-vector protocol and does not require a complete link-state database. DUAL uses feasible successors to achieve fast failover. (Example: An OSPF router recalculates the entire shortest path tree when a link fails, while an EIGRP router using DUAL can switch to a precomputed backup route (feasible successor) almost instantly without running a full algorithm again.)

## Step-by-step breakdown

1. **Initialize the root node** — The router sets its own distance to 0. All other routers in the network are marked with an infinite distance. A list of unvisited nodes is created containing all routers except the root.
2. **Select the node with smallest distance** — From the set of unvisited nodes, the algorithm picks the one with the smallest cumulative cost from the root. Initially, this will be a direct neighbor of the root that has the lowest link cost.
3. **Mark the selected node as visited** — Once a node is selected, it is added to the shortest path tree and removed from the unvisited set. This node's distance is now final and will not change.
4. **Examine the selected node's neighbors** — For each neighbor of the selected node, the algorithm calculates the new distance by adding the cost from the root to the selected node plus the cost of the link from the selected node to the neighbor.
5. **Update distances if a shorter path is found** — If the newly calculated distance to a neighbor is less than the currently stored distance for that neighbor, the algorithm updates the neighbor's distance and records the selected node as its predecessor in the path.
6. **Repeat until all nodes are visited** — Steps 2 through 5 are repeated until the unvisited set is empty. At that point, the shortest path tree is complete. The routing table is then populated with the best next-hop for each destination based on this tree.

## Practical mini-lesson

In a real-world network, the Dijkstra algorithm runs on every OSPF router every time the network topology changes. As a network professional, you need to understand not only the algorithm itself but also how it interacts with OSPF configuration and behavior. First, the cost metric is critical. On Cisco routers, the default reference bandwidth is 100 Mbps. So a FastEthernet (100 Mbps) interface has a cost of 1. A GigabitEthernet (1000 Mbps) interface would have a cost of 0.1, but OSPF uses only integer costs, so the actual cost becomes 1 as well. To differentiate between higher-speed links, you must manually set the reference bandwidth with the command 'auto-cost reference-bandwidth 10000' for a 10 Gbps reference, making a 100 Mbps link cost 100 and a 1 Gbps link cost 10. Second, OSPF areas reduce the scope of the Dijkstra calculation. Inside an area, every router has the same LSDB and runs the full algorithm. Between areas, summary LSAs are used, and the algorithm only considers routes to the ABR (Area Border Router) rather than all internal destinations of another area. This reduces processing load. Third, you should understand the role of the designated router (DR) on broadcast multi-access networks like Ethernet. The DR reduces the number of OSPF adjacencies, which in turn reduces the number of LSAs and the size of the LSDB, making the Dijkstra algorithm more efficient. Without a DR, every router would form a full mesh of adjacencies, which could overwhelm smaller routers. Fourth, fast convergence features like SPF throttling control how often the algorithm runs. By default, Cisco IOS waits 200 milliseconds after a topology change before starting the first SPF calculation, then waits 1000 milliseconds between subsequent calculations. These timers can be tuned to speed up convergence in high-availability networks. Finally, always verify OSPF operation with 'show ip ospf interface' to see the cost of each interface, and 'show ip route ospf' to see the routes calculated by Dijkstra. If a route is missing, check that the LSDB is synchronized using 'show ip ospf database'. Understanding these practical elements is essential for both passing certification exams and managing real OSPF networks.

## Memory tip

Think 'Dijkstra builds a tree, one node at a time, always picking the cheapest next spot.' The key words are tree, one node, and cheapest.

## FAQ

**Does the Dijkstra algorithm run on every OSPF router?**

Yes, every OSPF router in an area runs the Dijkstra algorithm independently to calculate the shortest path tree. This ensures that each router has a consistent and loop-free view of the network.

**What triggers the Dijkstra algorithm to run again?**

Any change in the network topology, such as a link going down or up, a neighbor change, or an interface cost modification, triggers OSPF to generate new LSAs. All routers that receive these LSAs will recalculate their shortest path tree using the Dijkstra algorithm.

**Can the Dijkstra algorithm cause high CPU usage?**

Yes, especially in large networks with many routers and links. To mitigate this, OSPF uses areas to limit the size of the link-state database and uses incremental SPF to recalculate only the parts of the tree that changed.

**What is the difference between Dijkstra and SPF?**

They are essentially the same thing. SPF stands for Shortest Path First, which is another name for the Dijkstra algorithm as applied to routing. In OSPF literature, you will often see 'SPF calculation' or 'SPF algorithm' used interchangeably.

**Does OSPF always use the path with the lowest cost?**

Yes, the Dijkstra algorithm ensures that the path with the lowest total cost is chosen. However, if multiple paths have the same cost, OSPF can use all of them for load balancing (equal-cost multi-path).

**What happens if a router receives an LSA with outdated information?**

OSPF uses sequence numbers and aging mechanisms to ensure that only the most recent LSA is used. An outdated LSA will be ignored or overwritten by a newer one. The Dijkstra algorithm only uses the current link-state database, so old data does not affect routing decisions.

## Summary

The Dijkstra algorithm, also known as the Shortest Path First algorithm, is the mathematical foundation of the OSPF routing protocol. It enables routers to calculate the most efficient path to every network destination by iteratively building a tree rooted at the local router. This algorithm ensures loop-free and deterministic routing, which is essential for the stability and performance of IP networks. For IT certification learners, particularly those pursuing CCNA and CCNP, understanding the Dijkstra algorithm is critical because it appears in both conceptual and practical exam questions. You need to know how the algorithm works step by step, how OSPF uses link costs to influence path selection, and how network changes trigger recalculation. Common pitfalls include confusing it with distance-vector algorithms like Bellman-Ford and forgetting that OSPF supports equal-cost multi-path load balancing. In real-world network engineering, the Dijkstra algorithm helps in designing scalable OSPF networks, tuning convergence timers, and troubleshooting routing issues. By mastering this algorithm, you will be well-prepared for both certification exams and on-the-job responsibilities. The key takeaway for exam day is to practice manually calculating shortest paths in simple network diagrams, as this skill is directly tested in scenario-based questions.

---

Practice questions and the full interactive page: https://courseiva.com/glossary/dijkstra-algorithm