下列算法中，通常用于计算最短路径的是：（）。

下列算法中，()算法用来求图中某顶点到其他顶点所有顶点之间的最短路径。

A.Dijkstra

B.Floyed

C.Prim

D.Kruskal

下列不属于起讫点不同的单一路径规划(最短路线问题)中的算法的是( )。

A．Dijkstra算法

B．逐次逼近法

C．Floyd算法

D．表上作业法

●迪杰斯特拉(Dijkstra)算法用于求解图上的单源点最短路径。该算法按路径长度递增次序产生最短路径，本质上说，该算法是一种基于(62)策略的算法。

(62)

A．分治

B．动态规划

C．贪心

D．回溯

迪杰斯特拉算法求最短路径时,是按照路径长度递增的顺序求解的。()

A、ARP

B、IGRP

C、RIP

D、OSPF

下列选项中代表，“开放路最短路径优先”路由协议是()

A.ARP

B.IGRP

C.RIP

D.OSPF

阅读下列算法说明和算法，将应填入(n)的字句写在对应的栏内。

[说明]

下列最短路径算法的具体流程如下：首先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择不使森林中产生回路的边加入到森林中去，直至该森林变成一棵树为止，这棵树便是连通网的最小生成树。该算法的基本思想是：为使生成树上总的权值之和达到最小，则应使每一条边上的权值尽可能地小，自然应从权值最小的边选起，直至选出 n-1条互不构成回路的权值最小边为止。

[算法]

/*对图定义一种新的表示方法，以一维数组存放图中所有边，并在构建图的存储结构时将它构造为一个“有序表”。以顺序表MSTree返回生成树上各条边。*/

typedef struct{

VertexType vex1;

VertexType vex2;

VRType weight;

} EdgeType;

typedef ElemType EdgeType;

typedef struct { //有向网的定义

VertexType vexs [MAX_VERTEX_N U M ]; //顶点信息

EdgeType edge[ MAX_EDGE_NUM]; //边的信息

int vexnum, arcnum; //图中顶点的数目和边的数目

I ELGraph;

void MiniSpanTree_Kruskal( ELGraph G,SqList& MSTree) {

//G, edge 中依权值从小到大存放有向网中各边

//生成树的边存放在顺序表MSTree中

MFSetF;

InitSet( F, G. vexnum ); //将森林F初始化为N棵树的集合

InitList (MSTree, G. vexnum); //初始化生成树为空树

i=0;k=1;

while(k＜(1)){

e = G. edge[i]; //取第i条权值最小的边

/*函数fix_mfset返回边的顶点所在树的树的根代号，如果边的两个顶点所在树的树根相同，则说明它们已落在同一棵树上。 */

ri = fix_mfset(F, LocateVex(e. vex1) );

r2=(2); //返回两个顶点所在树的树根

if(r1 (3) r2) { //选定生成树上第k条边

if(Listlnsert(MSTree,k,e){(4); //插入生成树

mix_mfset( E, r1,r2); //将两棵树归并为一棵树

}

(5); //继续考察下一条权值最小边

}

DestroySet (F); }

}

● 迪杰斯特拉(Dijkstra)算法用于求解图上的单源点最短路径。该算法按路径长度递增次序产生最短路径，本质上说，该算法是一种基于（61）策略的算法。 A.分治 B.动态规划 C.贪心 D.回溯

如果图中有一部分边的权为负值，那么用Dijkstra算法求图的最短路径是可行的。

用最短路径算法，求如图5—21中a到z的最短通路。