Dijkstra’s algorithm, discussion

Algorithm complexity: n nodes

• each iteration: need to check all nodes, w, not in N

• n*(n+1)/2 comparisons: O(n**2)

• more efficient implementations possible: O(nlogn)

Oscillations possible: (ADAPTING TOO QUICKLY)

• e.g., link cost = amount of carried traffic

1

1+e

e

0

e

1

1

0

0

0

2+e

1+e

1

0

0

initially

… recompute

routing

… recompute

… recompute

Previous slide

Next slide

Back to first slide

View graphic version