第三章 路由算法的设计
路由算法的数学模型是图论模型。如下图：
图7 网络模型
路由过程的选择，即是在加权无向图（或有向图）中寻找源结点与目标结点的最佳路径，根据最佳路径选择下一站路由器。如图7中，0结点至4结点的最佳路径是0→2→3→4，那么由0结点发往4结点的数据包在0结点时的下一站路由器是2结点，其余类推。
目前已有众多成熟的路由算法，典型如Dijkstra算法，可以方便的计算某一顶点到其余各顶点的最短路径，该过程的复杂度为O(n2)，则计算一个网络模型的路由表的时候，共需要调用n次算法，所以复杂度为O(n3)。另一个典型算法是Floyed算法，可以计算图中每对顶点之间的最短路径，复杂度为O(n3)。路由算法的详细情况可见于参考资料[6]和[7]。
但随着计算机科学的发展，新兴的计算模型得到广泛的注意和利用，尤其是智能计算。本文的路由算法设计中，改造实现了Floyed算法，使之由计算最短路径并同时计算路由表。另外，独立设计一种演化路由算法，并初步讨论了算法的收敛性。最后根据实验数据分析两种算法的性能。
§3.1 Floyed路由算法设计
Floyed算法从图的邻接矩阵开始，按照图结点0，1，2，…，n-1的顺序，分别以每个结点k（0<=k<=n-1）作为新考虑的中间点，在第k-1次运算得到的A (k-1) ( A (-1)为图的邻接矩阵GA)的基础上，求出每对结点i～j的目前最短路径长度A (k)[i][j]。计算公式为：
A(k)[i][j]=min(A(k-1)[i][j],A(k-1)[i][k] + A(k-1)[k][j])，
（ 0<= i<=n-1，0<= j <=n-1 ）。
当i结点是源结点，j结点是目标结点，而且i结点与k结点是相邻的时候，k结点就是目前最短路径中i结点的下一站路由器。
当k从0取到n-1的时候，矩阵A(n-1) 就是最后得到的结果--最短路径的矩阵，而同时按照上述方法跟踪就可以得到最优路由表。
原理如上所述，Floyed路由算法设计如下：
Algorithm Floyed-RoutCompute.
routNum是路由器数目，netArray[ routNum ][ routNum ] 是存储网络拓扑信息的矩阵，valArray[ routNum ][ routNum ] 是网络耗散信息的矩阵。.from是源路由器，routTable[ routNum ][ 2 ] 是待返回的路由表。matrix[ routNum ][ routNum ] 是存储源路由器到其它路由器的最短距离的矩阵。
BEGIN
bVal = TRUE;
For i=0 To routNum-1 Do
For j=0 To routNum-1 Do
matrix[i][j] = valArray[i][j];
For i=0 To routNum-1 Do
BEGIN //路由表初始化
routTable [i][0]=-1;
routTable [i][1]=-1;
END;
While(TRUE)
BEGIN
For k=0 To routNum-1 Do
For i=0 To routNum-1 Do
For j=0 To routNum-1 Do
BEGIN
If( matrix[i][j] >=(matrix[i][k] + matrix[k][j]))
BEGIN
//计算目前最短路径长度A(k)[i][j]
matrix[i][j] = matrix[i][k] + matrix[k][j];
If(i==from && netArray[i][k]==1)
BEGIN
//计算目前最短长度下路由表
If( i!=k OR k==j )
BEGIN
routTable [j][0] = j;
routTable [j][1] = k;
END;
END;
END; // end of If
END; // end of For
For i=0 To routNum-1 Do
bVal=bVal AND( routTable [i][0]!=-1)AND(routTable[i][1]!=-1);
If( bVal )
Break;
Else
bVal =TRUE;
END; // end of While
返回routTable;
END.
Floyed算法基于图论的矩阵理论，是非常有特点的一个传统算法。而且，易于程序实现，且可以方便的计算每对顶点之间的最短路径，这是和Dijkstra算法等其他算法不同的。对于连通图，其邻接矩阵A (-1)经过上述公式的计算，得到矩阵A(n-1)，这个过程是正确而收敛的，可以见于参考资料[2]，这也是Floyed算法的关键之处。我们在开始说Floyed算法的复杂度是O(n3)的，在后面算法分析的部分我们将结合实验数据来看算法的效率。
本文地址：http://com.8s8s.com/it/it36710.htm