请问,ospfspf算法具体一点的工作过程是怎样的..

请问,ospfspf算法具体一点的工作过程是怎样的..

spf算法用的就是Dijkstra算法.下面是摘自百度百科的内容,我推荐你去看TCP/IP路由第一卷这本书,里面讲的比较易懂.

Dijkstra算法的原理.
首先，引进一个辅助向量D，它的每个分量D表示当前所找到的从始点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为∞（在本程序中为MAXCOST）。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可达的最短路径长度。

按路径长度递增次序产生最短路径算法：
把V分成两组：
（1）S：已求出最短路径的顶点的集合
（2）V-S=T：尚未确定最短路径的顶点集合
将T中顶点按最短路径递增的次序加入到S中，
保证：（1）从源点V0到S中各顶点的最短路径长度都不大于
从V0到T中任何顶点的最短路径长度
（2）每个顶点对应一个距离值
S中顶点：从V0到此顶点的最短路径长度
T中顶点：从V0到此顶点的只包括S中顶点作中间
顶点的最短路径长度
依据：可以证明V0到T中顶点Vk的最短路径，或是从V0到Vk的
直接路径的权值；或是从V0经S中顶点到Vk的路径权值之和
（反证法可证）
求最短路径步骤
… 初使时令 S={V0},T={其余顶点}，T中顶点对应的距离值
? 若存在，为弧上的权值
? 若不存在，为∝
… 从T中选取一个其距离值为最小的顶点W，加入S
… 对T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的
距离值比不加W的路径要短，则修改此距离值
… 重复上述步骤，直到S中包含所有顶点，即S=V为止

spf算法是ospf路由协议的基础。spf算法有时也被称为dijkstra算法，这是因为最短路径优先算法spf是dijkstra发明的。spf算法将每一个路由器作为根（root）来计算其到每一个目的地路由器的距离，每一个路由器根据一个统一的数据库会计算出路由域的拓扑结构图，该结构图类似于一棵树，在spf算法中，被称为最短路径树。在ospf路由协议中，最短路径树的树干长度，即ospf路由器至每一个目的地路由器的距离，称为ospf的cost，其算法为：cost = 100×106/链路带宽 . 在这里，链路带宽以bps来表示。也就是说，ospf的cost 与链路的带宽成反比，带宽越高，cost越小，表示ospf到目的地的距离越近。举例来说，fddi或快速以太网的cost为1，2m串行链路的cost为48，10m以太网的cost为10等。