dijkstra与floyd方法求最短路径实验报告.docx_floyd算法求最短路径c

需积分: 40 185 浏览量更新于2023-05-18 评论 1 收藏 103KB DOCX 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

实验报告

一、实验名称

求最短距离及最短路线。

二、实验目的

（1）掌握最短路径的基础知识，掌握求最短路径的方法。

（2）充分了解 Dijkstra 算法与 Floyd 算法的性质与原理。

（3）利用编程的方法求出一个无向图（有向图）中的最短路径。

三、实验内容与要求

求最短距离及最短路线。

1、用 Dijkstra 算法求从节点 1 到节点 8 的最短路，并用程序实现；

2、用 Floyd 算法求任意两点之间的最短路，并用程序实现；

3、程序实现所用语言不限；

①

②

③

④

⑤

⑥

⑦

⑧

四、实验原理与步骤

（一）Dijkstra 算法

1、实验原理：

Dijstra 为了算出图中某点到其它点的最短路径，提出了按路径的长度递增次序，逐步产

生最短路径的算法，被称为 Dijstra 算法。Dijkstra 算法采用的是一种贪心的策略，声明一个

数组 dis 来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合：

T，初始时，原点 s 的路径权重被赋为 0 （dis[s] = 0）。若对于顶点 s 存在能直接到达的边

（s,m），则把 dis[m]设为 w（s, m）,同时把所有其他（s 不能直接到达的）顶点的路径长

度设为无穷大。初始时，集合 T 只有顶点 s，然后，从 dis 数组选择最小值，则该值就是源

点 s 到该值对应的顶点的最短路径，并且把该点加入到 T 中，此时完成一个顶点，然后，

我们需要看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径

长度是否比源点直接到达短，如果是，那么就替换这些顶点在 dis 中的值。然后，又从 dis

中找出最小值，重复上述动作，直到 T 中包含了图的所有顶点。

2、实验步骤：

此程序使用了 visual studio2010 进行编写，程序参考了《数据结构 C++版》课本

中的原有程序以及相关知识，并进行了一些改动。

(1) 建立一个 class Dis 类，用来记录起点到每个顶点的最短路径的信息。

(2) 建立一个 Graph_DG 类，存放图的顶点和边数、存储图的邻接矩阵以及程序中使用到

的函数。

Graph_DG 类中的主要函数：

①　析构函数：用于初始化顶点数和边数。

②　构造函数：用于释放程序中开辟的内存空间。

③　check_edge_value 函数：判断输入边的数据是否是合法的。

④　creatGraph 函数：创造一个新的图表。

⑤　print 函数：打印出图的邻接矩阵。

⑥　Dijkstra 函数：Dijkstra 算法的具体实现（利用实验原理中的算法进行程序设

计）。

⑦　Print_path 函数：打印出最小路径以及最小路径的长度。

关于表的输入、打印等函数此处不再赘述。下面主要叙述 Dijkstra 函数的建立：

①　首先初始化 dis 数组并设置当前的路径；

for (i = 0; i < this->vexnum; i++) {

dis[i].path = "v" + to_string(static_cast<long long>(begin)) + "-->v" +

to_string(static_cast<long long>(i + 1));

dis[i].value = arc[begin - 1][i];

}

②　设置起点到起点的路径为 0；

dis[begin - 1].value = 0;

③　接下来利用 count 计算剩余顶点的最短路径，temp 用于保存当前 dis 数组中最

小的下标，min 记录当前的最小值；

④　把 temp 对应的顶点加入到已经找到的最短路径的集合中；

⑤　为防止内存泄漏，此处我们选择加入条件 arc[temp][i]!=INT_MAX 的方法；

⑥　不断更新最短路径和长度总和，直到算出最后结果；

(3) 使用一个 check 函数判断输入的顶点个数和边的条数是否是合法的。

(4) 在主函数中建立表类的一个对象，要求用户输入图的顶点、边、边的权值等信息，并

使用建立的对象调用上面所写的函数。

（二）Floyd 算法

1、实验原理：

利用 Floyd 计算图 G=(V,E)中各个顶点的最短路径时，需要引入两个矩阵，矩阵 S 中

的元素 a[i][j]表示顶点 i(第 i 个顶点)到顶点 j(第 j 个顶点)的距离。矩阵 P 中的元素 b[i]

[j]，表示顶点 i 到顶点 j 经过了 b[i][j]记录的值所表示的顶点。假设图 G 中顶点个数为 N，

则需要对矩阵 D 和矩阵 P 进行 N 次更新。初始时，矩阵 D 中顶点 a[i][j]的距离为顶点 i 到

顶点 j 的权值；如果 i 和 j 不相邻，则 a[i][j]=∞，矩阵 P 的值为顶点 b[i][j]的 j 的值。接

下来开始，对矩阵 D 进行 N 次更新。第 1 次更新时，如果 ” a[i][j] 的距离 ” > “a[i]

[0]+a[0][j]”(a[i][0]+a[0][j]表示”i 与 j 之间经过第 1 个顶点的距离”)，则更新 a[i][j]

为”a[i][0]+a[0][j]”,更新 b[i][j]=b[i][0]。同理，第 k 次更新时，如果”a[i][j]的距离”>

剩余18页未读，继续阅读

小灏灏同学

粉丝: 17
资源: 4

会员权益专享

dijkstra与floyd方法求最短路径实验报告.docx

评论0

会员权益专享

最新资源

dijkstra与floyd方法求最短路径实验报告.docx

评论0

Floyd算法求任意两点间的最短路径

C例子：最短路径（floyd算法）

最短路径算法实验报告

c语言最短路径Dijkstra算法要求 1. 实现最短路径算法 2. 避开一个指定点 3. 必经一个指定点 4. 推广到多个点

floyd算法求最短路径

floyd算法求最短路径问题

在求多个最短路径时dijkstra与floyd哪一个更好

编写m文件,构造上图的邻接矩阵, 调用Dijkstra算法求出C1到C6的最短路径及最短路径长度，调用Floyd算法求出C2到C5的最短路径及最短路径长度。

dijkstra最短路径算法java

c语言中根据Dijkstra算法，实现求最短路径并输出最短路径的代码

如何保存调用Dijkstra每一次计算最短路径长度和最短路径信息？

优化dijkstra算法同时输出所有最短路径

dijkstra算法求单源最短路径

城市公共交通站点，站点之间的道路，及道路长度实际构成数学意义上的无向加权图。现请设计实现一个算法，求任意两站点间最短路径距离且输出该最短路径上的每个站点，然后给一个乘车换乘方案。

根据实际情况，先建立交通网络图的存储结构。 )．求某个城市到达其余各城市的最短路径。 )．任一输入两个城市，要求求出他们之间的最短路径C语言

dijkstra算法求最短路径c

Dijkstra算法如何求最短路径

dijkstra算法求最短路径

优化dijkstra算法同时输出所有最短路径matlab

会员权益专享

最新资源