开放式最短路径优先和戴克斯特拉算法

快捷方式: 差异，相似，杰卡德相似系数，参考。

开放式最短路径优先和戴克斯特拉算法之间的区别

开放式最短路径优先 vs. 戴克斯特拉算法

开放式最短路径优先（Open Shortest Path First，縮寫為 OSPF）是对链路状态路由协议的一种实现，隶属内部网关协议（IGP），故运作于自治系统内部。採用戴克斯特拉算法（Dijkstra's algorithm）被用来计算最短路径树。它使用“代价（Cost）”作为路由度量。链路状态数据库（LSDB）用来保存当前网络拓扑结构，路由器上属于同一区域的链路状态数据库是相同的（属于多个区域的路由器会为每个区域维护一份链路状态数据库）。OSPF分为OSPFv2和OSPFv3两个版本,其中OSPFv2用在IPv4网络，OSPFv3用在IPv6网络。OSPFv2是由RFC 2328定义的，OSPFv3是由RFC 5340定义的。 OSPF协议是大中型网络上使用最为广泛的IGP（Interior Gateway Protocol）协议。节点在建立邻接，接受链路状态通告（Link-state Advertisement，LSA）时，可以通过MD5或者明文进行安全验证。 OSPF提出了“区域（Area）”的概念，一个网络可以由单一区域或者多个区域组成。其中，一个特别的区域被称为骨干区域（Backbone Area），该区域是整个OSPF网络的核心区域，并且所有其他的区域都与之直接连接。所有的内部路由都通过骨干区域传递到其他非骨干区域。所有的区域都必须直接连接到骨干区域，如果不能建立直接连接，那么可以通过虚链路（virtual link）和骨干区域建立虚拟连接。 同一个广播域（Broadcast Domain）的路由器或者一个点对点（Point To Point）连接的两端的路由器，在发现彼此的时候，建立邻接（Adjacencies）。多路访问网络以及非广播多路访问网络的路由器会选举指定路由器（Designated Router, DR）和备份指定路由器（Backup Designated Router, BDR），DR和BDR作为网络的中心负责路由器之间的信息交换从而降低了网络中的信息流量。OSPF协议同时使用单播（Unicast）和组播（Multicast）来发送Hello包和链路状态更新（Link State Updates），使用的组播地址为224.0.0.5和224.0.0.6。与RIP和BGP不同的是，OSPF协议不使用TCP或者UDP协议而是承载在IP协议之上，IP协议号为89，工作在OSI模型的传输层。. 戴克斯特拉算法（Dijkstra's algorithm，又译迪杰斯特拉算法）由荷兰计算机科学家艾茲赫尔·戴克斯特拉在1956年提出。戴克斯特拉算法使用了廣度优先搜索解决赋权有向图的单源最短路径问题。该算法存在很多变体；戴克斯特拉的原始版本找到两个顶点之间的最短路径，但是更常见的变体固定了一个顶点作为源节点然后找到该顶点到图中所有其它节点的最短路径，产生一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。举例来说，如果图中的顶点表示城市，而边上的权重表示城市间开车行经的距离，该演算法可以用来找到两个城市之间的最短路径。 该演算法的輸入包含了一個有權重的有向圖 G，以及G中的一個來源頂點 S。我們以 V 表示 G 中所有頂點的集合。每一個圖中的邊，都是兩個頂點所形成的有序元素對。(u, v) 表示從頂點 u 到 v 有路徑相連。我們以 E 表示G中所有邊的集合，而邊的權重則由權重函數 w: E → 定義。因此，w(u, v) 就是從頂點 u 到頂點 v 的非負权重（weight）。邊的权重可以想像成兩個頂點之間的距離。任兩點間路徑的权重，就是該路徑上所有邊的权重總和。已知 V 中有頂點 s 及 t，Dijkstra 演算法可以找到 s 到 t 的最低权重路徑(例如，最短路徑)。這個演算法也可以在一個圖中，找到從一個頂點 s 到任何其他頂點的最短路徑。 最初的戴克斯特拉算法不采用最小优先级队列，时间复杂度是O(|V|^2)(其中|V|为图的顶点个数)。通过斐波那契堆实现的戴克斯特拉算法时间复杂度是O(|E|+|V|\log|V|) (其中|E|是边数) 。对于不含负权的有向图，这是目前已知的最快的单源最短路径算法。.

最短路徑樹

最短路径树，是一种使用最短路径算法生成的数据结构树。.

开放式最短路径优先和最短路徑樹 · 戴克斯特拉算法和最短路徑樹 · 查看更多 »