Link-State Algorithm

• Basic idea: two step procedure

• Each source node gets a map of all nodes and link metrics (link
state) of the entire network
• Find the shortest path on the map from the source node to all
destination nodes

• Broadcast of link-state information

• Every node i in the network broadcasts to every other node in
the network:
• ID’s of its neighbors: Ni = set of neighbors of i
• Distances to its neighbors: {Cij | j Ni}
• Flooding is a popular method of broadcasting packets
 Dijkstra Algorithm: Finding shortest paths
in order
Find shortest paths from Closest node to s is 1 hop away
source s to all other
destinations 2nd closest node to s is 1 hop
away from s or w”
3rd closest node to s is 1 hop
w' away from s, w”, or x

z
w
x
s z'
w"
x'
 Dijkstra’s algorithm
• N: set of nodes for which shortest path already found
• Initialization: (Start with source node s)
• N = {s}, Ds = 0, “s is distance zero from itself”
• Dj = Csj for all j  s, distances of directly-connected neighbors
• Step A: (Find next closest node i)
• Find i  N such that
• Di = min Dj for j  N ,Add i to N,
• If N contains all the nodes, stop
• Step B: (update minimum costs)
• For each node j  N
• Dj = min (Dj, Di+Cij)
• Go to Step A
Minimum distance from s to
j through node i in N
Dijkstra’s algorithm

• Find the shortest path from the source node(node 1) to all other
nodes

2 3
1 1
5 2

4
3 1 3 6

2
2 5
4
Execution of Dijkstra’s algorithm
2 2 
1 3 1 1 3 1
6 6 
5 2 5 2
3 3
1 4 1 4 2
2
3 3
2 2
 4 5 4 5

Iteration N D2 D3 D4 D5 D6
Initial {1} 3 2 5  
1 {1,3} 3 2 4  3
2 {1,2,3} 3 2 4 7 3 
3 {1,2,3,6} 3 2 4  5 3
4 {1,2,3,4,6} 3 2 4 5  3
5 {1,2,3,4,5,6} 3 2 4 5 3
Shortest Paths in Dijkstra’s Algorithm
2 3 1 2 3 1
1 1
6 6
5 2 5 2
3 3
1 4 2 1 4 2
3 3
2 2
4 5 4 5
2 3 1 2 3 1
1 1
6 6
5 2 5 2
3 3
1 4 2 1 4 2
3 3
2 2
4 5 4 5

2 3 1 2 3 1
1 1
6 6
5 2 5 2
3 3
1 4 2 1 4 2
3 3
2 2
4 5 4 5
Shortest path tree from node 1 to other
nodes

2 3
1 1
2

4
3 6

2
2 5
Consider the network in Figure below. Use the Dijkstra's algorithm to find
the set of shortest paths from node 1 to all other nodes.