最短路由选择算法

计算图中两个节点之间的最短距离有多种算法，其中最著名的算法是Dijkstra在1959年提出的Dijkstra算法 。该算法要求每个节点用从源节点沿已知最佳路径到本节点的距离来标注。开始时由于一条路径也不知道，故所有的节点都标注无穷大。随着算法的进行和不断找到的路径，标注随之改变，使之反映出较好的路径。一个标注可以是暂时性的(可更改的)，所有标注最初都是暂时的，但一旦发现了标注代表了从源节点到该节点的最短可能路径时，就使之成为永久性的，不再进行修改。

为了说明加标注算法是怎样工作的，请参考右图，其中数字表示两节点的距离。要找A至D的最短距离，首先A标注为永久性的(用实心圆点表示)作为开始，然后依次考察与A相邻的每个节点，用他们各自到A的距离重新标注这些点。找到B节点为最短路径节点后使其成为永久节点，接下来从节点B开始，检查所有与B相邻的节点，如果B的标注与从B到所有节点距离之和小于此节点的标注，就重新标注这个节点。 2100433B

最短路径树Dijkstra算法

设置两个定点的集合T和S，集合S中存放已找到最短路径的定点，集合T中存放当前还未找到的最短路径的定点。初始状态时，集合S中只包含源点v0然后不断从集合T中选取到定点v0路径长度最短的顶点u加入集合S，集合S中每加入一个新的顶点u，都要修改定点v0到集合T中剩余顶点的最短路径长度值，集合T中每个顶点新的最短路径长度值为原来的最短路径长度值与定点u的最短路径长度值加上u到该顶点的路径长度值中的较小值。此过程不断重复，直到集合T的顶点全部加入到集合S为止 。

最短路径树Floyd算法

从代表任意两个节点

考虑一个连通无向图

在一个所有最短路径都明确（例如没有负长度的环）的连通图，我们可以使用如下算法构造最短路径树：

使用Dijkstra算法或Floyd算法计算图 G 从根节点 v 到 顶点 u 的最短距离

对于所有的非根顶点

用各个顶点和它们的父节点之间的边构造最短最短路径树。

上面的算法保证了最短路径树的存在。像最小生成树一样，最短路径树通常也不只有一个的。在所有边的权重都相同的时候，最短路径树和广度优先搜索树一致。在存在负长度的环时，从

路由选择方法的精确描述，属于网路软件的一部分。对它的要求是正确、简单、可靠、稳定、公平和优化。

路由选择算法可分为自适应型和非自适应型两大类。自适应型的特点在于它的路由选择能在一定程度上随网路运行状态（如流量和拓扑）而改变，可避开出现异态的节点或链路。非自适应型采用静态路由选择算法。常见的非自适应型有扩散式、随机式、固定式等；而自适应型有集中式、孤立式、分布式等。

固定式是一种应用范围比较广的非自适应型路由选择算法。它是根据网路拓扑和信息流量的统计模型事先确定各节点的路由表，每个节点的路由表指明从该节点出发到某个目的节点所应该选择的输出链路以及下一节点。路由表由算法确定，而在固定式中是事先预定的。

最短路径算法为最常用的算法，它寻求在源节点和目的节点之间能沿着长度最短的路径来传送分组。这里所指的“长度”赋于特别含义，既可以是实际距离，也可以是平均时延或者链路费用。长度参数是路由表的依据，如果参数值来自网路运行的当前状态，路由表变为动态生成，这样的路由选择算法就属于自适应型。

Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。Dijkstra算法是很有代表性的算法。Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表的方式，这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。

首先，引进一个辅助向量D，它的每个分量D[i]表示当前所找到的从始点v到每个终点vi的的长度：如D[3]=2表示从始点v到终点3的路径相对最小长度为2。这里强调相对就是说在算法过程中D的值是在不断逼近最终结果但在过程中不一定就等于长度。它的初始状态为：若从v到vi有弧，则D为弧上的权值；否则置D为∞。显然，长度为 D[j]=Min{D | vi∈V} 的路径就是从v出发的长度最短的一条。此路径为(v,vj)。 那么，下一条长度次短的是哪一条呢？假设该次短路径的终点是vk，则可想而知，这条路径或者是(v,vk)，或者是(v,vj,vk)。它的长度或者是从v到vk的弧上的权值，或者是D[j]和从vj到vk的弧上的权值之和。 一般情况下，假设S为已求得的终点的集合，则可证明：下一条最短路径（设其终点为X）或者是弧(v,x)，或者是中间只经过S中的顶点而最后到达顶点X的路径。因此，下一条长度次短的的长度必是D[j]=Min{D | vi∈V-S} 其中，D或者是弧(v,vi)上的权值，或者是D[k](vk∈S)和弧(vk,vi)上的权值之和。

算法描述如下：

1）arcs表示弧上的权值。若不存在，则置arcs为∞。S为已找到从v出发的的终点的集合，初始状态为空集。那么，从v出发到图上其余各顶点vi可能达到的度的初值为D=arcs[Locate Vex(G,v),i] vi∈V

2）选择vj，使得D[j]=Min{D | vi∈V-S} 3）修改从v出发到集合V-S上任一顶点vk可达的最短路径长度。