路由算法详解

文章摘要：这些步骤的流程图如下： 示例：Dijkstra算法我们想找到A与E（下图）之间的最佳路由。可以看到A与E之间有六条可能路径（ABE、ACE、ABDE、ACDE、ABDCE、ACDBE），很明显ABDE是最佳路由，因为它的权值最小。但是实际情况并非总是如此简单，有很多复杂的情形需要使用算法来找到最佳路由。 如下图所示，源节点(A)被选为T节点，所以它的标号是永久（我们将永久性节点以实圈标注，T节点以-->符号标注）。 <-- -->在这一步中，直接链接到T节点的暂时性节点(B, C)的状态记录集已经被修改。同时，由于B有更小的权值，所以它被选作T节点，其标号被改为永久（如下图

路由算法详解,标签：电子电路基础,模拟电路基础,http://www.88dzw.com

这些步骤的流程图如下：

示例：Dijkstra算法

我们想找到A与E（下图）之间的最佳路由。可以看到A与E之间有六条可能路径（ABE、ACE、ABDE、ACDE、ABDCE、ACDBE），很明显ABDE是最佳路由，因为它的权值最小。但是实际情况并非总是如此简单，有很多复杂的情形需要使用算法来找到最佳路由。

1. 如下图所示，源节点(A)被选为T节点，所以它的标号是永久（我们将永久性节点以实圈标注，T节点以-->符号标注）。

   <-- -->

2. 在这一步中，直接链接到T节点的暂时性节点(B, C)的状态记录集已经被修改。同时，由于B有更小的权值，所以它被选作T节点，其标号被改为永久（如下图所示）。

   <-- -->

3. 与步骤2类似，在这一步中，直接链接到T节点的暂时性节点(D, E)的状态记录集已经被修改。同时，由于D有更小的权值，所以它被选作T节点，其标号被改为永久（如下图所示）。

   <-- -->

4. 在这一步中，已经没有任何暂时性节点，所以我们仅仅需要确认下一个T节点。因为E有最小权值，所以它被选作T节点。

   <-- -->

5. E是目的节点，所以我们在这里停止。

我们已经到达了终点！现在，我们需要确定路由。E的前序节点是D，D的前序节点是B，B的前序节点是A。所以最佳路由是ABDE。在这个案例中，权值和为4(1+2+1)。

虽然这个算法工作良好，但是它非常复杂，以致于路由器需要花费大量时间进行处理，网络的性能因此下降了。同样，如果一个路由器将错误的信息发送给其他路由器，那么所有的路由决定都将是无效的。为了更好的理解这个算法，下面给出由C语言编写的源代码：

#define MAX_NODES 1024        /*最大节点数 */
#define INFINITY 1000000000      /*比所有最大路径都大的数 */
int n,dist[MAX_NODES][MAX_NODES];     /*dist[I][j] 是从 i 到 j 的距离*/

上一页  [1] [2] [3] [4] [5]  下一页