路由选择算法源程序（最短路径算法）

Distance vector arithmetic

Test of the program

Test1: the topological picture of one network as follow

The vertex of the graph represent the routers with tabels (0,1,…,8,9), and the edges are for the

links between linked routers with a time delay for each link (In this graph, each delay is 1 unit).

Our goal is to find the most time-saving path from one router to another using the distance vector

arithmetic.

The Input file contains the link information of N(now 10) routers.

3

4 1

5 1

7 1

2

3 1

5 1

1

3 1

2

1 1

6 1

2

5 1

7 1

3

0 1

6 1

8 1

2

7 1

For example, "2->6: nextrouter is 3, time left to reach dest is 4" is from the list of router 2, which

means that if the destination is router6 , router 2 should transfer it first to router 3, and the

expected total delay from 2 to 6 is 4units.

Output.txt:

0->6: nextrouter is 5, time left to reach dest is 2

0->7: nextrouter is 7, time left to reach dest is 1

0->8: nextrouter is 7, time left to reach dest is 2

0->9: nextrouter is 7, time left to reach dest is 3

1->0: nextrouter is 5, time left to reach dest is 2

1->1: nextrouter is 1, time left to reach dest is 0

1->2: nextrouter is 3, time left to reach dest is 2

1->3: nextrouter is 3, time left to reach dest is 1

1->4: nextrouter is 5, time left to reach dest is 3

2->0: nextrouter is 3, time left to reach dest is 4

2->1: nextrouter is 3, time left to reach dest is 2

2->2: nextrouter is 2, time left to reach dest is 0

2->3: nextrouter is 3, time left to reach dest is 1

2->4: nextrouter is 3, time left to reach dest is 5

2->5: nextrouter is 3, time left to reach dest is 3

2->6: nextrouter is 3, time left to reach dest is 4

2->7: nextrouter is 3, time left to reach dest is 5

2->8: nextrouter is 3, time left to reach dest is 6

2->9: nextrouter is 3, time left to reach dest is 7

3->5: nextrouter is 1, time left to reach dest is 2

3->6: nextrouter is 1, time left to reach dest is 3

3->7: nextrouter is 1, time left to reach dest is 4

3->8: nextrouter is 1, time left to reach dest is 5

3->9: nextrouter is 1, time left to reach dest is 6

4->6: nextrouter is 0, time left to reach dest is 3

4->7: nextrouter is 0, time left to reach dest is 2

4->8: nextrouter is 0, time left to reach dest is 3

4->9: nextrouter is 0, time left to reach dest is 4

5->0: nextrouter is 0, time left to reach dest is 1

5->1: nextrouter is 1, time left to reach dest is 1

5->2: nextrouter is 1, time left to reach dest is 3

5->3: nextrouter is 1, time left to reach dest is 2

5->4: nextrouter is 0, time left to reach dest is 2

6->0: nextrouter is 5, time left to reach dest is 2

6->1: nextrouter is 5, time left to reach dest is 2

6->2: nextrouter is 5, time left to reach dest is 4

6->3: nextrouter is 5, time left to reach dest is 3

6->4: nextrouter is 5, time left to reach dest is 3

6->5: nextrouter is 5, time left to reach dest is 1

6->6: nextrouter is 6, time left to reach dest is 0

6->7: nextrouter is 7, time left to reach dest is 1

6->8: nextrouter is 7, time left to reach dest is 2

6->9: nextrouter is 7, time left to reach dest is 3

7->5: nextrouter is 0, time left to reach dest is 2

7->6: nextrouter is 6, time left to reach dest is 1

7->7: nextrouter is 7, time left to reach dest is 0

7->8: nextrouter is 8, time left to reach dest is 1

7->9: nextrouter is 8, time left to reach dest is 2

8->6: nextrouter is 7, time left to reach dest is 2

8->7: nextrouter is 7, time left to reach dest is 1

8->8: nextrouter is 8, time left to reach dest is 0

8->9: nextrouter is 9, time left to reach dest is 1

9->0: nextrouter is 8, time left to reach dest is 3

9->1: nextrouter is 8, time left to reach dest is 5

9->2: nextrouter is 8, time left to reach dest is 7

9->3: nextrouter is 8, time left to reach dest is 6

9->4: nextrouter is 8, time left to reach dest is 4

Test2: If the link between router 0 and 4 bacomes quite bad, with a delay of 500 unit, then

what's th e result?

5 1

7 1

2

3 1

5 1

1

3

0 1

1 1

6 1

2

5 1

7 1

3

0 1

6 1