最短路径
标签: 数据结构
学习人数: 6793


全屏播放
赞赏支持

最短路径算法是在图中求两点(或多点)之间的最短路径,我们最常见的最短路径算法有三种:Bellman-ford、Dijkstra、Floyd。

Bellman-ford算法可以用于有负边权的图,如果途图中有负环,算法也可以检验出来,时间复杂度为O(VE)。

Dijkstra算法只能用于边权为正的图中,时间复杂度为O(n^2)

Floyd可以用于有负权的图中,即使有负环,算法也可以检测出来,可以求任意点的最短路径,有向图和无向图的最小环和最大环。时间复杂度O(n^3)

 

Dijkstra算法求单源最短路径问题

大概就是这样一个有权图,Dijkstra算法可以计算任意节点其他节点的最短路径

算法思路

1.指定一个节点,例如我们要计算 'A' 到其他节点的最短路径
2.引入两个集合(S、U),S集合包含已求出的最短路径的点(以及相应的最短长度),U集合包含未求出最短路径的点(以及A到该点的路径,注意 如上图所示A->C由于没有直接相连 初始时为∞
3.初始化两个集合,S...

登录查看完整内容


课后作业

课后习题

 

【2016年真题】使用迪杰斯特拉(Dijkstra)算法求下图中从顶点1到其他各顶点的最短路径,依次得到的各最短路径的目标顶点是()
A.5,2,3,4,6    B.5,2,3,6,4
C.5,2,4,3,6    D.5,2,6,3,4

参考答案:B

 

【2012年真题】对如下有向带权图,若采用迪杰斯特拉(Dijkstra)算法求从源点 a 到其他各顶点的最短路径,则得到的第一条最短路径的目标顶点是 b,第二条最短路径的目标顶点是 c,后续得到的其余各最短路径的目标顶点依次是()。 

A.d,e,f 
B.e,d,f 
C.f,d,e 
D.f,e,d 

参考答案:C
答案解析:考查 Dijkstra 算法最单源最短路径。 
从 a 到各顶点的最短路径的求解过程: 

【排除法】 对于 A,若下一个顶点为 d,路径 a,b,d 的长度 5,而 a,b,c,f 的长度仅为 4,显然错误。 
同理可以排除 B。将 f 加入集合 S 后,采用上述的方法也可以排除 D。 

 

【2014年真题】某网络中的路由器运行 OSPF 路由协议,题 42 表是路由器 R1 维护的主要链路状态信息(LSI),题 42 图是根据题 42 表及 R1 的接口名构造出来的网络拓扑。 

请回答下列问题。 

1)本题中的网络可抽象为数据结构中的哪种逻辑结构? 

2)针对题 42 表中的内容,设计合理的链式存储结构,以保存题 42 表中的链路状态信 
息(LSI)。要求给出链式存储结构的数据类型定义,并画出对应题 42 表的链式存储结构示意 
图(示意图中可仅以 ID 标识结点)。 

3)按照迪杰斯特拉(Dijikstra)算法的策略,依次给出 R1 到达题 42 图中子网 192.1.x.x 
的最短路径及费用。 

参考答案:
考察在给出具体模型时,数据结构的应用。该题很多考生乍看之下以为是网络的题目, 
其实题本身并没有涉及太多的网络知识点,只是应用了网络的模型,实际上考察的还是数据 
结构的内容。 
(1)图
题中给出的是一个简单的网络拓扑图,可以抽象为无向图。 
(2)链式存储结构的如下图所示

其数据类型定义如下:

typedef struct{  
    unsigned int ID, IP;  
}LinkNode; //Link 的结构  
typedef struct{  
    unsigned int Prefix, Mask;  
}NetNode; //Net 的结构  
typedef struct Node{  
    int Flag; //Flag=1 为 Link;Flag=2 为 Net  
    union{  
        LinkNode Lnode;  
        NetNode Nnode  
    }LinkORNet;  
    unsigned int Metric;  
    struct Node *next;  
}ArcNode; //弧结点  
typedef struct HNode{  
    unsigned int RouterID;  
    ArcNode *LN_link;  
    Struct HNode *next;  
}HNODE; //表头结点  

对应题 42 表的链式存储结构示意图如下。

(3)计算结果如下表所示。

 

【2009年真题】带权图(权值非负,表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假设从初始顶点到目标顶点之间存在路径,现有一种解决该问题的方法: 
① 设最短路径初始时仅包含初始顶点,令当前顶点u为初始顶点; 
② 选择离u最近且尚未在最短路径中的一个顶点v,加入到最短路径中,修改当前顶点u=v; 
③ 重复步骤②,直到u是目标顶点时为止。 
请问上述方法能否求得最短路径?若该方法可行,请证明之;否则,请举例说明。 

参考答案:
该方法不一定能(或不能)求得最短路径。 
例如,对于下图所示的带权图,如果按照题中的原则,从 A 到 C 的最短路径是 A->B->C,事实上其最短路径是 A->D->C。 


登录后发布评论

暂无评论,来抢沙发