Computer Networks · M2 · read-chapter

Routing: build the shortest path one step at a time

Unit 4 · shortest paths and routing tables

1. Routing, forwarding, distance and next hop
2. Relaxation: replace an old route only when the candidate is cheaper
3. One edge relaxation · example 1
4. One edge relaxation · example 2
5. One edge relaxation · example 3
6. Dijkstra: settle the closest unfinished vertex
7. Dijkstra · complete example 1
8. Dijkstra · complete example 2
9. Dijkstra · complete example 3
10. Bellman–Ford: repeat relaxation across all edges
11. Bellman–Ford · complete example 1
12. Bellman–Ford · complete example 2
13. Bellman–Ford · negative-cycle example