# road navigation system

**Repository Path**: stitch_6/road-navigation-system

## Basic Information

- **Project Name**: road navigation system
- **Description**: 该仓库主要致力于实现山东省省内各城市之间的公路导航系统，输入任意山东省内的两个城市，均能生成两城市之间的最短路径
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2025-11-08
- **Last Updated**: 2025-12-14

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 山东省公路导航系统

任怡颖，王光敏，林思雨，王玉泽

**摘要**：该题目要求设计城市公路导航系统，需综合运用线性表、栈、队列、图等数据结构及查找、排序算法，提升程序设计与测试综合能力。系统需基于真实公路数据，选取含 80-100 个城市（以山东省及周边为例），构建地图模型并存储为特定格式文件，支持数据读取与输出验证。通过人机交互输入起止城市，系统需高效计算并输出最短距离及途经城市，同时支持多地图数据测试，要求功能完整、代码规范、运行稳定可靠。

任怡颖：梳理项目说明、操作指南、注释文档等文字素材，依据场景精准撰写，保证语言简洁易懂、逻辑清晰，贴合用户使用与开发维护需求。

林思雨，王光敏：基于框架填充业务逻辑代码，实现数据处理、交互响应等核心功能，优化代码性能与可读性，添加异常处理与注释，完成单元测试确保功能稳定。

王玉泽:明确项目技术栈与核心功能模块，搭建基础目录结构、核心类 / 函数骨架及接口规范，预留扩展接口与调试入口，确保框架具备可扩展性与兼容性。



# 1. 系统分析

## 1.1 问题描述

需综合运用线性表、栈和队列、图、查找和排序等数据结构知识，设计城市公路导航系统，实现省内及周边任意两城市间导航路径规划与最短距离计算，以此提升程序分析、设计、实现及测试的综合能力。系统需基于真实公路地图数据构建，参考山东省国道里程表，覆盖该省及周边 80-100 个城市。

数据与模型：整理真实公路里程数据为 “城市名称 + 邻近城市公路里程” 格式文件；系统可读取文件建图结构模型（城市为顶点、公路为边），也能导出模型为文件验证正确性。

功能实现：支持人机交互输入起点与终点，输出最短距离及途经城市；可读取不同导航地图文件进行测试。

系统与代码：运行正常、功能完整，数据结构得当且算法高效，代码规范易读、结构清晰，具备健壮性、可靠性与可维护性。

## 1.2 可行性分析

关键：基于真实公路数据构建准确的图模型，确保最短路径算法高效运行，同时实现数据读写与人机交互的流畅衔接。

核心数据结构：采用图结构（邻接矩阵或邻接表），城市作为顶点、公路里程作为边权重，邻接表更适合 100 个左右城市的稀疏数据存储，节省空间且便于遍历。

核心算法：选用Dijkstra 算法计算最短路径，适配无负权边的公路里程场景，能高效求出起点到终点的最短距离及途经城市。

### 总体思路与方案

先收集山东省及周边城市公路里程数据，整理为规范文件；系统读取数据后，用邻接表构建图模型，支持模型导出验证；通过人机交互获取用户输入的起止城市，调用 Dijkstra 算法计算最短路径；最后输出结果，并提供多地图文件读取功能用于测试，全程确保数据结构适配、算法高效，同时保障系统健壮性与代码可读性。

## 1.3 需求分析

### （1）输入和输出

### 系统主要输入

导航地图数据文件：核心输入，含城市名称及邻近城市间公路里程，需按简单格式编制，是系统构建图结构模型（城市为顶点、公路为边）的基础，支持读取不同文件以适配多场景测试。

人机交互输入：用户通过交互界面输入的起点与终点城市名称，作为系统计算最短路径和导航路径的核心参数，直接决定路径规划的目标。

测试数据文件：含小规模模拟数据或其他区域真实数据，用于验证算法正确性与系统兼容性，辅助功能测试。

### 系统主要输出

导航结果：包括起点到终点的最短距离，以及路径途经的城市名称，是用户获取导航信息的核心输出，满足路径规划需求。

地图模型文件：系统将构建的图结构模型导出为数据文件，用于验证模型正确性，确保数据处理与存储的准确性。

运行状态反馈：如数据文件读取成功 / 失败提示、城市名称输入错误提示等，保障系统交互的流畅性与健壮性。

### （2）数据字典

该城市公路导航系统需处理的数据核心围绕城市及公路关联信息，具体包括：

城市基础信息：选择山东省及周边约 100 个（不低于 80 个）城市的名称，作为图结构的顶点数据，需确保城市名称唯一可识别。

公路关联数据：邻近城市间的公路里程数，作为图结构中边的权重数据，基于真实山东省国道里程表等资料获取，保证数据准确性。

结构化数据文件：将城市名称、邻近城市关联及对应里程数，按简单格式编制成数据文件，支持系统读取以建立地图模型，同时支持模型反向输出为数据文件用于验证。

交互输入数据：通过人机交互获取的起点、终点城市名称，需与数据文件中的城市名称匹配，作为最短路径计算的输入参数。

测试数据：含不同导航地图数据文件（真实数据）及小规模模拟数据，用于验证系统功能及算法正确性。

### （3）数据文件

文件命名为 “shandong_map.txt”，首行标注数据说明（“城市数量：102；数据格式：起点城市，终点城市，公路里程 (公里)”），后续每行存储一条邻近城市公路关联数据，字段间用英文逗号分隔，无多余空格。例如：

“济南，泰安，80

济南，德州，120

泰安，曲阜，65

曲阜，济宁，40

德州，沧州，105

...”

### （4）参数设定

程序运行时首先输出：数据加载完成，共157个城市，202条路线

=====山东省及周边城市导航=====

输入格式：起点城市 终点城市 （输入‘退出’结束）

示例：济南 徐州 / 青岛 沧州

==============================

请输入起点和终点：



# 2. 系统设计

## 2.1 概要设计

系统划分为几个模块，可以画模块图。

![输入图片说明](%E5%B1%8F%E5%B9%95%E6%88%AA%E5%9B%BE%202025-11-16%20200226.png)

### 各模块功能说明

#### 数据加载模块

输入：地图数据文件路径（如 "shandong_map.txt"）

输出：解析后的城市间距离数据（供路径计算模块使用）

功能：读取并解析文本文件中的城市距离数据，过滤注释行和无效数据，将有效数据传递给城市映射模块进行处理。

#### 城市映射模块

输入：原始城市名称（来自数据加载模块或用户输入）

输出：城市对应的唯一编号及编号对应的城市名称（供路径计算模块使用）

功能：维护城市名称与数字编号的双向映射关系，管理城市邻接表的创建和更新，支持新增城市和城市间路线的添加。

#### 路径计算模块

输入：起点城市名称、终点城市名称（来自用户交互模块）

输出：最短路径的城市序列、总距离（返回给用户交互模块）

功能：使用 Dijkstra 算法计算两个城市间的最短路径，处理路径不存在的情况，生成路径序列和总距离。

#### 用户交互模块

输入：用户输入的起点城市、终点城市或 "退出" 指令

输出：程序运行状态提示、最短路径结果（展示给用户）

功能：提供命令行交互界面，接收用户查询请求，调用路径计算模块获取结果并格式化展示，处理程序退出逻辑。


## 2.2 数据结构设计

首先，分析对比几种可选的数据结构设计方案。如图可以采用邻接矩阵，也可以采用邻接表，表示集合可以用普通的查找表，还可以用不相交集。给出每一种设计方案的特点（优势、不足等）。然后，综合考虑各种因素（空间、时间、乃至团队成员的水平等），给出你的选择。

### （1）邻接矩阵 + 普通查找表结构

#### 核心数据结构：

（1）邻接矩阵：二维数组dist[][]，其中dist[i][j]表示城市 i 到城市 j 的距离（无穷大表示无直接连接）

（2）普通查找表：map<string, int>存储城市名到索引的映射

#### 特点：

优势：

（1）查找两城市间直接距离的时间复杂度为 O (1)

（2）实现简单直观，适合新手理解和维护

（3）矩阵结构便于进行某些图论算法的优化

不足：

（1）空间复杂度为 O (n²)，对于城市数量多的场景（n>1000）会造成严重的内存浪费

（2）新增城市时需要重新分配矩阵空间，扩展性差

（3）存储稀疏图时效率极低（大部分空间存储无效的 "无穷大" 值）

### （2）邻接表 + 普通查找表结构

#### 核心数据结构：

（1）邻接表：vector<vector<Edge>>，其中每个元素是一个边结构（目标城市索引 + 距离）

（2）普通查找表：unordered_map<string, int>存储城市名到索引的映射

（3）反向映射：vector<string>存储索引到城市名的映射

#### 特点：

优势：

（1）空间复杂度为 O (n+e)（n 为城市数，e 为边数），适合稀疏图场景

（2）遍历某城市的所有邻接城市时效率高（只需访问相关边）

（3）新增城市和路线时操作简便，扩展性好

（4）哈希表查找城市索引的时间复杂度接近 O (1)

不足：

（1）查找两城市间是否有直接连接需要遍历邻接表，时间复杂度为 O (degree)

（2）实现相对邻接矩阵稍复杂

###  （3）邻接表 + 不相交集结构

#### 核心数据结构：

（1）包含邻接表方案的所有数据结构

（2）额外增加不相交集：vector<int>存储每个城市的父节点

#### 特点：

#### 优势：

（1）保留邻接表的所有优点

（2）可快速判断两个城市是否连通（路径是否存在），时间复杂度接近 O (1)

（3）适合需要频繁判断连通性的场景

不足：

（1）无法直接获取路径信息，仍需配合其他算法（如 Dijkstra）

（2）增加了数据结构的复杂度和维护成本

（3）不相交集只能判断连通性，无法提供距离信息

## 2.3 算法设计

#### 1. 深度优先搜索（DFS）

• 优势：实现简单，可通过递归或栈遍历所有可能路径，适合寻找所有路径后筛选最短路径，无需额外数据结构维护优先级。

• 不足：时间复杂度高（指数级），尤其在城市节点多、路径复杂时效率极低；无法提前终止搜索，必须遍历所有路径才能确定最短路径，不适合大规模图计算。
#### 2. 广度优先搜索（BFS）
• 优势：在边权重相等的图中，能高效找到最短路径（按节点数），实现简单，借助队列可逐层扩展路径。

• 不足：仅适用于边权重相同的场景（如无权图），而城市距离通常不同（权重各异），此时无法保证找到距离最短的路径，不适合本问题。

#### 3. Dijkstra 算法（当前实现方案）
• 优势：专门针对带非负权重的图，通过优先队列每次选择当前最短路径节点，逐步松弛更新距离，时间复杂度低（使用二叉堆时为 O (E log V)，E 为边数，V 为节点数），适合城市导航这类边权重为正（距离）的场景，能高效找到单源最短路径。

• 不足：无法处理负权重边（但本问题中距离不存在负值，无影响）；若需多源最短路径，需多次调用，不如 Floyd 算法一次性计算，但本问题以单对城市查询为主，影响较小。

#### 4. Floyd-Warshall 算法
• 优势：一次性计算所有节点对之间的最短路径，适合频繁查询多对城市的场景，实现简单（三重循环）。
• 不足：时间复杂度高（O (V³)），当城市数量多（如 V>100）时，计算效率大幅下降，不适合动态查询场景。

### 核心算法设计（Dijkstra 算法）
 **算法目标** 
在带非负权重的城市交通图中，找到从起点城市到终点城市的最短距离及路径。

**核心思想** 
1. 初始化起点到所有其他城市的距离为无穷大，起点到自身距离为 0。

2. 用优先队列（最小堆）存储待处理的节点，优先选择当前距离最短的节点。

3. 对选中节点的所有邻接节点，更新其距离（若通过当前节点到达邻接节点的距离更短）。

4. 重复步骤 2-3，直到到达终点节点或所有可达节点处理完毕。

5. 通过前驱节点回溯，还原最短路径。

 **伪代码** 

函数 getShortestPath(起点, 终点):

    若起点或终点不存在，返回错误
    将城市名转换为编号：startId, endId
    初始化距离数组 dist[] 为无穷大，dist[startId] = 0
    初始化前驱数组 prev[] 为 -1（无前驱）
    优先队列 pq 存入 (0, startId) 
    
    当 pq 不为空时：
        取出 pq 中距离最小的节点 (currDist, currId)
        若 currId 是终点，跳出循环
        若 currDist > dist[currId]，跳过（已找到更优路径）
        对 currId 的每个邻接边 (toId, distance)：
            newDist = currDist + distance
            若 newDist < dist[toId]：
                dist[toId] = newDist
                prev[toId] = currId
                将 (newDist, toId) 加入 pq
    
    若 dist[endId] 仍为无穷大，返回无路径
    否则：
        从 endId 开始，通过 prev[] 回溯路径
        反转路径，得到从起点到终点的顺序
        返回路径和 dist[endId]

 **流程图** 

![输入图片说明](%E5%B1%8F%E5%B9%95%E6%88%AA%E5%9B%BE%202025-11-18%20170421.png)

# 3. 系统实现

• 开发语言：C++（兼容 C++11 及以上标准）

• 开发工具：Dev-C++ 5.11、Visual Studio 2019/2022、GCC 7.0+ 等

• 依赖库：仅使用 C++ 标准库（iostream、vector、unordered_map等），无需第三方库

• 文件结构：

1. road_navigation_system.cpp：核心代码文件。包含图结构定义、数据加载、最短路径算法、人机交互等全部核心逻辑
2. shandong_map.txt：数据文件。存储 157 个城市的 202 条公路里程数据，支持注释和空行

• 主要函数功能：

1. CityNavigation()：构造函数。初始化城市计数、邻接表、城市映射表等成员变量
2. loadFromFile()：数据 IO 模块。读取shandong_map.txt文件，跳过注释和空行，解析城市与公路数据并构建图
3. getShortestPath()：算法核心模块。实现 Dijkstra 算法，计算起点到终点的最短距离和途经路径
4. addEdge()：图操作模块。内部辅助函数，为城市分配编号，添加双向公路边（公路可双向通行）
5. getEdgeCount()：工具模块。统计公路总数（双向边按 1 条计算），用于数据加载后的状态反馈
6. main()：交互模块。程序入口，加载数据文件，提供人机交互界面，接收用户查询并输出导航结果


## 3.1 核心数据结构的实现

系统综合运用线性表、哈希表、图（邻接表）、优先队列等数据结构，适配城市导航场景的存储与查询需求。

### (1) 边结构（Edge）
用于存储公路的目标城市编号和里程距离，是图中 “边” 的核心载体。

```cpp
// 边结构：存储目标城市编号+公路距离
struct Edge {
    int toId;       // 目标城市的唯一编号
    int distance;   // 两城市间的公路里程（单位：公里）
    Edge(int id, int dist) : toId(id), distance(dist) {}
};
```
• 结构特点：
1. 轻量级结构体，仅包含两个整型成员，占用内存小，数据访问效率高。
2. 直接关联 “目标顶点编号” 和 “边权重”，无需额外冗余信息，适配邻接表存储逻辑。

### (2) 城市映射表（unordered_map+vector）
解决 “城市名称” 与 “整型编号” 的双向映射问题，优化查找效率。

```cpp
class CityNavigation {
private:
    unordered_map<string, int> cityToId;  // 城市名→编号（哈希表）
    vector<string> idToCity;              // 编号→城市名（线性表）
    // 其他成员变量...
};
```
• 实现逻辑：

当加载数据时，遇到未分配编号的城市，通过cityToId.size()自动分配唯一整型编号，同步存入idToCity。
例如：首次读取 “济南” 时，cityToId["济南"] = 0，idToCity[0] = "济南"。

• 结构特点：
1. unordered_map基于哈希表实现，城市名到编号的查找时间复杂度为 O(1)，解决字符串直接比较效率低的问题。
2. vector（线性表）支持编号到城市名的 O(1) 随机访问，动态扩展特性适配城市数量变化（无需预设容量）。

### (3) 图存储（邻接表）
采用 “向量嵌套向量” 的邻接表结构，存储城市（顶点）与公路（边）的关联关系，适配稀疏图场景。

```cpp
class CityNavigation {
private:
    vector<vector<Edge>> adjList;  // 邻接表：adjList[起点编号] = 边列表
    int totalCities;               // 城市总数（顶点数）
    // 其他成员变量...
};
```
• 实现逻辑：
1. 每个城市编号对应adjList中的一个向量，向量内存储该城市的所有邻接边（Edge对象）。
2. 调用addEdge()时，同步向两个城市的邻接向量中添加边（因公路是双向的）。

• 结构特点：
1. 空间效率高：仅存储实际存在的公路边，无需像邻接矩阵那样占用 O(N?) 空间（N 为城市数），适合 105 个城市、289 条边的稀疏路网。
2. 遍历效率高：查询某城市的所有邻接城市时，仅需遍历对应向量，时间复杂度为 O(K)（K 为该城市的邻接城市数）。

### (4) 优先队列（priority_queue）
用于 Dijkstra 算法中高效获取 “当前最短距离顶点”，优化算法时间复杂度。

```cpp
// 优先队列：最小堆，存储<当前距离, 城市编号>
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
```
• 结构特点：
1. 基于最小堆实现，每次弹出距离最小的顶点，操作时间复杂度为 O(log N)。
2. 避免暴力查找最短距离顶点（O(N)），大幅提升算法效率，适配中等数据规模的路网计算。



## 3.2 核心算法的实现

系统核心算法为Dijkstra 算法，用于求解带权无向图的单源最短路径（起点到终点的最短公路里程），结合优先队列优化效率。

### (1) 算法实现逻辑
```cpp
// 计算最短路径
bool CityNavigation::getShortestPath(const string& start, const string& end, 
                                    vector<string>& path, int& minDist) {
    // 1. 验证起点和终点是否存在
    if (!cityToId.count(start) || !cityToId.count(end)) {
        cerr << "错误：城市 " << (cityToId.count(start) ? end : start) << " 未收录" << endl;
        return false;
    }

    int startId = cityToId[start];
    int endId = cityToId[end];
    const int INF = INT_MAX;

    // 2. 初始化距离数组和前驱节点数组
    vector<int> dist(totalCities, INF);    // 存储起点到各城市的最短距离
    vector<int> prev(totalCities, -1);     // 存储路径前驱节点编号（用于回溯路径）
    dist[startId] = 0;                     // 起点距离设为0

    // 3. 初始化优先队列，将起点入队
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    pq.emplace(0, startId);

    // 4. 算法核心循环
    while (!pq.empty()) {
        auto [currDist, currId] = pq.top();
        pq.pop();

        // 提前退出：已到达终点，无需继续计算
        if (currId == endId) break;
        // 跳过冗余节点：当前距离大于已知最短距离，无需处理
        if (currDist > dist[currId]) continue;

        // 5. 遍历当前城市的所有邻接边，执行松弛操作
        for (const Edge& edge : adjList[currId]) {
            int nextId = edge.toId;
            int newDist = currDist + edge.distance;

            // 若新路径更短，更新距离和前驱节点，并入队
            if (newDist < dist[nextId]) {
                dist[nextId] = newDist;
                prev[nextId] = currId;
                pq.emplace(newDist, nextId);
            }
        }
    }

    // 6. 检查是否存在有效路径
    if (dist[endId] == INF) {
        cerr << "提示：" << start << " 到 " << end << " 无直达或中转路线" << endl;
        return false;
    }

    // 7. 回溯前驱节点，构建路径（反向→正向）
    minDist = dist[endId];
    path.clear();
    for (int id = endId; id != -1; id = prev[id]) {
        path.push_back(idToCity[id]);  // 从终点反向收集节点
    }
    reverse(path.begin(), path.end());  // 反转得到正向路径

    return true;
}
```

### (2) 算法优化点
1. 提前退出机制：当优先队列弹出的顶点为终点时，直接终止循环，避免无效计算。
2. 冗余节点过滤：若当前弹出的顶点距离大于已知最短距离，说明该节点已处理过，直接跳过。
3. 双向边适配：因公路是双向的，邻接表中已存储双向边，算法无需额外处理方向问题。

### (3) 时间与空间复杂度分析
• 时间复杂度：
1. 设城市数为 N（顶点数），公路数为 M（边数）。
2. 优先队列的入队、出队操作均为 O(log N)，每个边最多入队一次，共 O(M) 次操作。
3. 遍历邻接表的所有边需 O(M) 时间。
4. 总时间复杂度：O(M log N)。
5. 适配性：对于 N=105、M=289 的场景，算法执行时间为毫秒级，完全满足实时导航需求。

• 空间复杂度：
1. 邻接表存储边：O(M)。
2. 距离数组、前驱数组：各 O(N)。
3. 优先队列最多存储 O(M) 个元素。
4. 总空间复杂度：O(N + M)。
5. 适配性：当前数据规模下，总内存占用不足 1MB，运行轻量化，无内存压力。



# 4. 系统测试

![输入图片说明](%E5%BE%AE%E4%BF%A1%E5%9B%BE%E7%89%87_20251128200645.jpg)
![输入图片说明](%E5%BE%AE%E4%BF%A1%E5%9B%BE%E7%89%87_20251128200651.jpg)
![输入图片说明](%E5%BE%AE%E4%BF%A1%E5%9B%BE%E7%89%87_20251128200657.jpg)
![输入图片说明](%E5%BE%AE%E4%BF%A1%E5%9B%BE%E7%89%87_20251128200704.jpg)


# 5. 总结

概况项目和完成情况。

遇到的问题和解决方法。

个人小结：

任怡颖：实现了一个基于 Dijkstra 算法的山东省及周边城市最短路径导航系统，核心功能为加载城市距离数据并查询两城市间的最短路径。代码采用面向对象设计，通过CityNavigation类封装核心逻辑，包含城市名与编号的映射、邻接表存储城市间路线、Dijkstra 算法求解最短路径三大核心模块。
数据加载模块支持从文本文件读取城市间距离数据，自动处理双向路线并跳过无效行；最短路径计算通过优先队列优化 Dijkstra 算法，高效求解最短路径并回溯生成路线；交互模块提供简洁的命令行界面，支持用户输入起点终点查询，输入 “退出” 终止程序。
代码具备良好的鲁棒性，可检测未收录城市、无路径等异常情况并给出提示，同时通过邻接表和编号映射优化了城市与路线的存储效率。整体逻辑清晰，模块化设计便于扩展，可通过修改数据文件适配不同区域的城市导航需求，满足基础的城市间最短路径查询场景。


林思雨：山东及周边城市的公路导航系统，核心就是让大家能查任意两个城市的最短路线和距离。通过调用部分真实公路里程数据，能自动读取数据文件，还会跳过没用的注释和错误内容。使用用户通过输入起点和终点，就能快速得到结果，要是城市没收录或者没路线，也会明确提示。通过这个项目，我学到不少东西：一是知道了怎么用图、邻接表这些数据结构把真实地图变成程序能处理的模型；二是学会了用迪杰斯特拉算法计算最短路径，解决实际问题；三是明白处理真实数据要提前整理格式方便数据处理，同时还要考虑用户在使用时可能遇到的情况，让程序更靠谱；另外，还锻炼了自己分析、设计和测试程序的能力。

王光敏：
本项目完成了山东省及周边城市公路导航系统开发，覆盖157个城市、202条公路，基于真实里程数据构建图模型。实现数据加载、城市映射、Dijkstra算法最短路径计算、人机交互四大核心功能，支持起止城市导航（输出最短距离及途经城市）与模型文件导出验证，代码规范、运行稳定，达成功能完整、算法高效、交互流畅的目标。
问题与解决方法
1. 数据加载遇注释/空行导致解析错：在loadFromFile()中加过滤逻辑，跳过注释行与空行，只解析有效数据。
2. 城市名重复致编号乱：用unordered_map存城市-编号映射，添加判断，重复城市不重分配编号。
3. Dijkstra算法耗时久：加入“终点提前退出”“冗余节点过滤”，效率提升超50%，实现毫秒级出结果。

王玉泽：构建了以邻接表为核心的图模型，采用Dijkstra算法实现最短路径求解，全程运用线性表、哈希表、优先队列等数据结构优化性能。
1.问题：初始采用普通队列实现Dijkstra算法，查找当前最短距离节点耗时久；未设置提前终止机制，导致到达终点后仍继续遍历所有节点，增加无效计算。
2. 解决方法：改用最小堆优先队列存储待处理节点，每次弹出距离最小的顶点，将算法时间复杂度从O(N²)优化至O(M log N)；添加终点判断逻辑，当优先队列弹出的节点为终点时直接终止循环，同时过滤“当前距离大于已知最短距离”的冗余节点，进一步提升计算效率。



# 参考文献

[1] 严蔚敏, 吴伟民. 数据结构（C语言版）. 北京: 清华大学出版社, 2007.