# 求图中任意两点间的最短路径-QT

**Repository Path**: cclex/qt_Floyd_Dijkstra

## Basic Information

- **Project Name**: 求图中任意两点间的最短路径-QT
- **Description**: 使用QT作为开发环境，运用Dijkstra和Floyd算法解决图中任意两点间的最短路径问题，并动态绘制路径的寻找过程和绘制过程
- **Primary Language**: C++
- **License**: MulanPSL-2.0
- **Default Branch**: master
- **Homepage**: https://www.esw.ink
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 2
- **Created**: 2022-07-01
- **Last Updated**: 2022-07-01

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 求图中任意两点间的最短路径动态演示

#### 问题描述

在如今快节奏的生活里，人们开始追求速度，争分夺秒与时间赛跑。如何快速达到目的地已经成为了现在所要解决的问题。从某一地点到另一地点，花最少的时间，跑最短的距离俨然成为了当代打工人的追求。最短路径算法的提出与运用，将会大幅度减少用户到达目的地的所用时间。

#### 功能描述

##### 算法功能

利用Floyd和Dijkstra算法计算最短路径，并返回相应的坐标给绘制模块。

##### 绘制功能

对目的坐标信息进行处理，并绘制连线，实现动态绘制最短路径。

##### 提示功能

对程序的运行以及绘制时间进行记录，并将其显示在交互窗口，便于用户知晓大致的运行时间。

##### 记录功能

在软件的专门的控制台窗口显示运行信息和结果，并且让用户知晓最短路径的距离和所要经过的中间点。

##### 介绍功能

显示算法介绍窗口，让用户对本软件所使用的算法有大致的了解和认识。

#### 性能描述

仅能够处理已经计划的数据，无法从外部重新录入数据
仅能处理有连线的坐标数据，无法自主重新连线
本系统算法的两个时间复杂度分别为：o(n3)和o(n2)，计算坐标时间均在毫秒级，为显示动态查找过程，使用定时器控制绘制的速度。
绘制速度可由用户自行控制，默认线程计时器时间为500ms。由于绘制过程中存在图片缓存和窗口缓存问题，当线程计时器较大时（例如5000ms-10000ms）会出现假死状态。

#### 方案描述

该软件设计目的旨在解决地图间路径最短距离，通过算法计算出最短路径，随后对地图上的最短路径进行标注，并为用户展示最短路径所经过的地点以及最到达终点的距离，解决了用户在路径选择上的问题。

#### 项目设计

##### 软件结构设计

##### 数据结构设计

###### 数据存储结构

Floyd和Dijkstra算法所使用的的线性表采用数组来实现顺序表

###### 原因和合理性

由于本次项目的实现不需要对数据进行频繁的插入和删除，并且不需要对数据进行大规模的移动，所以在这种情况下不用考虑使用链表。并且本项目的所有数据都是由导入的地图所规定的，所以数据是固定的，而数组的优势则在此充分的展现出来，较高的存储效率和快速的随机存储的能力使得系统运行的速度加快。
总的来说，在本项目中，使用数组的效率要远高于链表。

#### 关键算法设计

##### FLOYD算法

###### 流程图
![Floyd](sources/floyd.png)

###### 时间效率分析

对Floyd算法的主要过程进行分析，包含状态转移方程的整体循环次数最多，所以最为分析对象。共有3层循环，每次循环n次，通过计算可得该算法的时间复杂度为O(n3)。由于该算法的时间复杂度较高，所以不适合计算大量数据。

###### 空间效率分析

同理，通过对主要过程的分析，该算法的空间复杂度为O(n2)。算法实现所使用的存储结构为数组，所以有较高的存储效率和快速的随机存取的能力。

###### 整体分析

优点：可以计算负权值，表达和实现较为简单，对于稠密图，效率要高于执行|V|次Dijkstra算法。
缺点：时间复杂度较高，不适合对大量数据进行计算。

##### DIJKSTRA算法

###### 流程图

![DIJKSTRA](sources/DIJKSTRA.png)
###### 时间效率分析

通过对主要算法过程的分析，以及算法实现搜索地图中最小路径的集合，计算可以得到本算法的时间复杂度为O(n2)

###### 空间效率分析

同理，通过对主要过程的分析，该算法的空间复杂度为O(n)。分析情况均在在通常情况下的结果。

###### 整体分析

优点：它可以确保扩展节点必须是从起始点到当前点的成本最小的路径。因此，根据这一原则进行搜索。当它找到目标节点时，回溯路径一定是代价最小的路径，并且具有完备性
缺点：不知道目标节点的位置，只能保证每一步扩展的节点的累计代价是最小的，所以如下图所示，它必须向所有方向扩展，目的不强，算法效率较低


#### 项目测试

##### 绘制测试
![地图绘制](sources/%E5%9B%BE1.png)

###### 测试步骤：
1. 正常运行软件
2. 显示DEMO窗口，自动连线完成
3. 地图绘制完成，如图1显示
- 测试结论：测试通过，符合预期




##### 算法测试
![Floyd算法](sources/%E5%9B%BE2.png)
![Dijkstra算法](sources/%E5%9B%BE3.png)

###### 测试步骤：
1. 随机选择起始点，例如广东和泸州；
2. 选择使用Floyd和Dijkstra算法；
3. 计算完毕，开始绘图
4. 绘图结束，如图2和图3
- 测试结论：测试通过，符合预期结果

##### 异常拦截测试
未选择算法时，或者为选择起点和终点，弹出图4提示，并提醒用户选择

![异常拦截](sources/%E5%9B%BE4.png)
###### 测试步骤：
1. 起始点与终点只选其一
2. 点击Floyd或Dijkstra算法
3. 等待异常触发，如图4
- 测试结论：异常拦截测试通过，符合预期结果




##### 交互测试

![控制台窗口信息交互](sources/%E5%9B%BE5.png)
![粘贴功能](sources/%E5%9B%BE6.png)


###### 测试步骤：

1. 选择起始点；
2. 任选算法之一，进行计算绘制
3. 控制台信息窗口输出，如图5
4. 信息窗口文本置剪切板，粘贴测试如图6
- 测试结论：交互测试通过，符合预期结果。

#### 参考文献
- 严蔚敏,吴伟民.数据结构[M].北京:清华大学出版社,2007.
- 托马斯·科尔曼、查尔斯·雷瑟尔森、罗纳德·李维斯 《算法导论》 麻省理工学院出版社
- QT Creator开发文档 Qt Company
- C++程序设计 清华大学出版社,2018-04-23