spf 算法树是怎么样理解的?
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等。
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 算法树中构建的。当LSDB 在一个区域完全相同，稳定时，
以自身为根，算出到达每条链路的最佳路径。注意，是最佳，而不是最短。这个图就是spf
算法树.
储陆金裕： 当一个区域内所有的路由器LSDB 都一致的时候,每路由器以自己为根生成自己的SPF 树, 再从SPF 树中推导出路由表. 红盟过客:ospf 的路由表是由spf 算法树中构建的.当LSDB 在一个区域完全相同,稳定时, 以自身为根,算出到达每条链路的最佳路径.注意,是最佳,而不是最短.这个图就是spf 算法树.
唐河县19432915007： OSPF协议的SPF算法? - ？
储陆金裕： SPF算法是OSPF路由协议的基础.SPF算法有时也被称为Dijkstra算法,这是因为最短路径优先算法SPF是Dijkstra发明的.SPF算法将每一个路由器作为根(ROOT)来计算其到每一个目的地路由器的距离,每一个路由器根据一个统一的数据库...
唐河县19432915007： SPF算法怎样构建网络的SPF树? ？
储陆金裕： 因为链路状态路由协议会交换链路状态信息,所以SPF算法可以构建网络的SPF树,有了SPF树,路由器可独立确定通向每个网络的最短路径
唐河县19432915007： 在思科的OSPF协议中是如何决定路由器的ID的? - ？
储陆金裕： SPF算法是OSPF路由协议的基础.SPF算法有时也被称为Dijkstra算法,这是因为最短路径优先算法SPF是Dijkstra发明的.SPF算法将每一个路由器作为根(ROOT)来计算其到每一个目的地路由器的距离,每一个路由器根据一个统一的数据库...
唐河县19432915007： 计算机操作系统中spf是什么意思 - ？
储陆金裕： 额
唐河县19432915007： 请教各位同学:spf算法中,因为每一颗生成树都是由路由器单独计算,那是否意味着计算出的生成树可能不同? - ？
储陆金裕： 计算出的生成树就是不同的. 每个路由器都是以自己为根来构建最短路径树的. 负载分担是针对某一个路由器来说的. 路由作为叶子节点,这两个节点可能代表一个相同的路由. 如果到达两个叶子节点的距离相同,不就可以负载分担吗.
唐河县19432915007： OSPF路由协议的工作原理是什么?？
储陆金裕： 首先要说它是链路状态协议,是基于spf算法中的dijkstra算法的 再说邻居发现协议的整个过程 router发送hello包给组播地址zhidao224.0.0.5,然后是邻居的路由就会回复,进而建立邻居关系 然后osfp会进行链路状态数据库(lsdb)的交换和更新过程,进而使整个区域中的全部路由器都有一张相同的链路状态表,就是lsdb 基于lsdb再结合dijkstra算法,计算出来无环的路由信息也就是spf树,然后路由器根据spf树选择出最佳路径,将这个路径加入到其路由表中
唐河县19432915007： 计算时间短的优先算法的例子,求解释: - ？
储陆金裕： 第一个任务来了就执行了, 等到其他任务也来了,造成资源阻塞,第一个执行完了后再按时间短的优先选择执行.
唐河县19432915007： 请问CCNA中单区域OSPF的工作原理？
储陆金裕： OSPF协议工作过程: 1、宣告OSPF的路由器从所有启动OSPF协议的接口上发出HELLO报文,两台ROUTER共享一条公共数据链路,并且能够相互成功协商各自HELLO报文中所指定的参数.那么它们就成为邻居(Neighbor) 2、邻接关系(...
唐河县19432915007： RIP与OSPF的算法有什么区别? - ？
储陆金裕： 一、OSPF协议 (一)、OSPF协议简介 OSPF是Open Shortest Path First(即“开放最短路由优先协议”)的缩写.它是IETF组织开发的一个基于链路状态的自治系统内部路由协议.在IP网络上,它通过收集和传递自治系统的链路状态来动...
