Scribd
Upload
6 views2 pages

Dijkstra Routing Algorithm

Dijkstra's algorithm is a method for finding the shortest path from a source node to all other nodes in a network, commonly used in link-state routing protocols like OSPF. The algorithm involves assigning tentative distances, updating neighbors, and marking nodes as visited until all nodes are processed. An example illustrates the process with a network graph, showing the final shortest paths from the source node A to nodes B, C, and D.

Uploaded by

Nagidi Gayathri
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
6 views2 pages

Dijkstra Routing Algorithm

Dijkstra's algorithm is a method for finding the shortest path from a source node to all other nodes in a network, commonly used in link-state routing protocols like OSPF. The algorithm involves assigning tentative distances, updating neighbors, and marking nodes as visited until all nodes are processed. An example illustrates the process with a network graph, showing the final shortest paths from the source node A to nodes B, C, and D.

Uploaded by

Nagidi Gayathri
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

Dijkstra's (Shortest Path) Routing Algorithm

Definition:

Dijkstra's algorithm is a shortest path routing algorithm used in computer networks to find the
minimum cost path from the source node to all other nodes in the network. It is commonly used in
link-state routing protocols like OSPF (Open Shortest Path First).

Steps of Dijkstra's Algorithm:

1. Assign a tentative distance value to every node. Set the distance to the source node as 0 and all
others as infinity.
2. Mark all nodes as unvisited. Set the source node as the current node.
3. For the current node, update the tentative distances of its neighbors.
4. After considering all neighbors, mark the current node as visited.
5. Select the unvisited node with the smallest tentative distance as the new current node.
6. Repeat steps 3-5 until all nodes are visited.

Example:

Consider the following network graph:

2
A ------- B
|\ |
1| 4\ |1
| \ |
C ------- D
3

Source node: A

Step-by-Step Table:

Step Current Node Distance from A Visited Nodes


1 A A=0, B=2, C=1, D=4 A
2 C A=0, B=2, C=1, D=4 A, C
3 B A=0, B=2, C=1, D=3 A, C, B
4 D A=0, B=2, C=1, D=3 A, C, B, D

Final Shortest Paths:

- A to B: 2
- A to C: 1
- A to D: 3

Summary:

- Start at A
- Pick the node with the smallest distance next
- Keep updating neighbors until all nodes are visited

You might also like