我要招人

去企业版

首页 > 试题广场 >

开放最短路径优先协议（ OSPF ）采用（）算法计算最佳

[单选题]

开放最短路径优先协议（ OSPF ）采用（）算法计算最佳路由

```
Dynamic-Search
```
```
Bellman-Ford
```
```
Dijkstra
```
```
Spanning-Tree
```

推荐

Jino.

选C。

OSPF是一种基于Diikstra算法的链路状态协议，这种协议要求路由器掌握完整的网络拓扑结构，并据此计算出到达目标的最佳路由。

该算法的基本思想是：互联网上的每个路由器周期性地向其他路由器广播自己与相邻路由器的连接关系，利用其他路由器的广播信息，互联网上的每个路由器都可以形成一张由点和线连接而成的抽象拓扑结构图；一旦得到了这张图，路由器就可以按照Dijkstra算法计算出以本地路由器为根的SPF树，通过这棵树路由器就可以生成自己的路由表。

编辑于 2019-11-08 14:37:36 回复(0)

求中个奖——狗头

选C

OSPF(Open Shortest Path First开放式最短路径优先)是一个内部网关协议(Interior Gateway Protocol，简称IGP)，用于在单一自治系统(Autonomous System,AS)内决策路由。是对链路状态路由协议的一种实现，隶属内部网关协议(IGP)，故运作于自治系统内部。著名的迪克斯加算法(Dijkstra)算法被用来计算最短路径树。OSPF分为OSPFv2和OSPFv3两个版本,其中OSPFv2用在IPv4网络，OSPFv3用在IPv6网络。OSPFv2是由RFC 2328定义的，OSPFv3是由RFC 5340定义的。与RIP相比，OSPF是链路状态协议，而RIP是距离矢量协议。

Dijkstra算法是典型的算法。Dijkstra算法是很有代表性的算法。Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表的方式，这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。

由于现在的题目除非需要判断负环，~~使用spfa很容易被卡~~，稠密图中更适用Dijkstrau算法

使用堆优化的Dijkstrau算法可优化到mlogn
这是代码

struct edge{int nx,to;}e[maxm<<1];
int cnt=0,h[maxn];
void add(int u,int v)
{
    e[++cnt]=(edge){h[u],v};
    h[u]=cnt;
}

typedef pair < int , int > author;
priority_queue < pr , vector < pr > , greater < pr > > q;
void Dij(int root,int h[],node e[],long long d[])
{
    q.push(make_pair(d[root]=0,root));
    int dis,u,v;
    while(!q.empty())
    {
        u=q.top().second;
        dis=q.top().first;
        q.pop();
        if(dis^d[u])
            continue;
        for(int i=h[u];i;i=e[i].next)
            if(d[v=e[i].to]>d[u]+e[i].value)
            {
                d[v]=d[u]+e[i].value;
                q.push(make_pair(d[u],u));
            }
    }
}

编辑于 2019-11-08 12:19:19 回复(0)

白驹之过隙

选C。考察的是OSPF的原理

OSPF组播的方式在所有开启OSPF的接口发送Hello包，用来确定是否有OSPF邻居。
若发现了，则建立OSPF邻居关系，形成邻居表，之后互相发送LSA（链路状态通告）相互通告路由，形成LSDB（链路状态数据库）。
再通过Dijkstra算法，计算最佳路径（cost最小）后放入路由表，Dijkstra算法是OSPF路由协议的基础

发表于 2019-11-07 17:46:01 回复(0)

一叶见秋

迪杰斯特拉算法又叫最短路径算法

发表于 2023-08-19 09:28:30 回复(0)

哈哈哈哈加油找工作

Dijkstra 算法计算最佳路由 Spanning tree 提供了网络状态的冗余切换机制

发表于 2022-08-13 23:00:13 回复(0)

想踩缝纫机的大学生在评审

迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。

发表于 2022-04-26 11:09:34 回复(0)

乾坤仍我行

<p>bellman-ford 是距离向量算法</p>

发表于 2020-12-13 21:12:43 回复(0)

提交观点

问题信息

网络基础

上传者：喵大人喵喵喵

难度：

7条回答 236收藏 5480浏览

开放最短路径优先协议（ OSPF ）采用（）算法计算最佳

问题信息

热门推荐

相关试题

开放最短路径优先协议（ OSPF ）采用 （） 算法计算最佳

问题信息

热门推荐

相关试题

开放最短路径优先协议（ OSPF ）采用（）算法计算最佳