数据结构第七次作业·第四题·北京地铁线路查询&Dijkstra算法

2023-10-11 09:52| 来源: 网络整理| 查看: 265

一.Dikjstra算法：

（部分内容出自博客Dijkstra算法（迪杰斯特拉算法）_持之以恒2016-CSDN博客）

基本思想：

Dikjstra算法采用广度优先策略，从起始点v0开始，层层向外拓展。正是如此，导致其搜索成功率较高但是时间复杂度较大为O(n²)。

将顶点划分为两种：集合S：已经确定最短路径的顶点；集合U：没有确定最短路径的顶点。

操作步骤

1.初始：从s开始，S中只有元素S，其他元素都在U中。且U中顶点与s的距离定义为：若U，s直接连接，则其距离就为其邻接矩阵定义的距离。若U，s不直接连接，则其距离为无穷大（INF）。这样定义是因为可以优先考虑与D相邻的顶点，实现BFS。

2.从U中选出距离最小的顶点k，并把k加入到S中。且k的前序就是v0。

3.更新距离：以k为依托，与k直接连接的顶点到v0的距离（但不一定最小）就等于其到k的距离加上k到v0的距离。若这个距离小于当前记录的距离，则这个顶点的前序就是k。

4.重复2，3到遍历结束。

图解示例

在这里插入图片描述

----- S是已计算出最短路径的顶点的集合 ----- U是未计算出最短路径的顶点的集合 ----- C(3)表示顶点C到起点D的最短距离为3

选择顶点D S={D(0)} U={A(∞), B(∞), C(3), E(4), F(∞), G(∞)}

在这里插入图片描述

选取顶点C S={D(0), C(3)} U={A(∞), B(13), E(4), F(9), G(∞)}

在这里插入图片描述

选取顶点E S={D(0), C(3), E(4)} U={A(∞), B(13), F(6), G(12)}

在这里插入图片描述

选取顶点F S={D(0), C(3), E(4), F(6)} U={A(22), B(13), G(12)}

在这里插入图片描述

选取顶点G S={D(0), C(3), E(4), F(6), G(12)} U={A(22), B(13)}

在这里插入图片描述

选取顶点B S={D(0), C(3), E(4), F(6), G(12), B(13)} U={A(22)}

在这里插入图片描述

选取顶点A S={D(0), C(3), E(4), F(6), G(12), B(13), A(22)} U={}

在这里插入图片描述

代码如下：

void Dijkstra(int v0){ int minweight,minv; int wfound[MAXVEX]={0};//to sign if the shortest path from i to v0 is found for(int i=0;i

【本文地址】

今日新闻