解释用例

一个学校平面图，至少包括10个以上的场所，每个场所带有编号、坐标、名称、类别等信息，两个场所间可以有路径相通，路长（耗时）各有不同。要求读取该校园平面图，查询各个场所信息，找出从任意场所到达另一场所的最短路径（最佳路径）。

算法实现

1. 初始化数据结构

1
2
3
std::unordered_map<int, double> distances;
std::unordered_map<int, int> previous;
std::priority_queue<std::pair<double, int>, std::vector<std::pair<double, int>>, std::greater<>> minHeap;
  • distances：存储从起始地点到每个其他地点的当前已知最短距离，初始化为无穷大。
  • previous：用于记录在最短路径中每个地点的前一个地点，以便最终回溯得到路径。
  • minHeap：优先队列，用于选择当前已知最短距离的地点，以便继续搜索。

2. 初始化距离

1
2
3
4
5
for (const auto& place : places) {
    distances[place.first] = std::numeric_limits<double>::infinity();
}
distances[startId] = 0; // 起点到自己的距离为 0
minHeap.push({ 0, startId }); // 将起点加入优先队列
  • 遍历所有的场所 places，将起点以外的所有地点的距离初始化为无穷大。
  • 将起点 startId 的距离设置为 0，并将起点加入优先队列。

3. 主循环 - 寻找最短路径

1
2
3
4
while (!minHeap.empty()) {
    int currentId = minHeap.top().second;
    double currentDistance = minHeap.top().first;
    minHeap.pop();
  • 进入一个循环，直到优先队列为空。在每次循环中，取出距离最小的地点。
  • 用 currentId 存储当前地点的 ID，与其对应的距离存储在 currentDistance 中。

4. 提前结束条件

1
2
3
if (currentId == endId) {
    break;
}
  • 如果当前地点是目标地点 endId，则提前结束循环，因为我们找到了从起点到目标地点的最短路径。

5. 遍历邻接节点

1
2
3
4
5
6
7
8
9
10
11
for (const auto& neighbor : adjacencyList[currentId]) {
    int neighborId = neighbor.first;
    double edgeWeight = neighbor.second;

    double newDistance = currentDistance + edgeWeight; // 计算新距离
    if (newDistance < distances[neighborId]) {
        distances[neighborId] = newDistance; // 更新距离
        previous[neighborId] = currentId; // 更新 PATH
        minHeap.push({ newDistance, neighborId }); // 添加到优先队列
    }
}
  • 遍历所有当前节点的邻接节点（相连的节点）。
  • 对于每个邻接节点，计算从起点到该邻接节点的新距离 newDistance。
  • 如果该新距离小于之前记录的距离（即，更新的更短），则更新 distances 和 previous。
  • 将更新后的邻接节点的 ID 和新距离重新添加到优先队列 minHeap。

6. 检查路径是否存在

1
2
3
if (previous.find(endId) == previous.end()) {
    return Path(places[startId], places[endId], std::numeric_limits<double>::infinity());
}
  • 如果在结束时没有找到目标节点的前一个节点，说明不存在从起点到目标节点的路径，返回一个无效路径。

7. 回溯生成路径

1
2
3
4
5
6
7
8
9
std::vector<Place> pathPlaces;
for (int at = endId; at != startId; at = previous[at]) {
    pathPlaces.push_back(places[at]);
    if (previous.find(at) == previous.end()) {
        return Path(places[startId], places[endId], std::numeric_limits<double>::infinity());
    }
}
pathPlaces.push_back(places[startId]); // 添加起点
std::reverse(pathPlaces.begin(), pathPlaces.end()); // 反转路径顺序
  • 创建一个向量 pathPlaces 用于存储最终的路径。
  • 从目标节点开始，通过 previous 回溯到起点，依次将经过的地点存储在 pathPlaces 中。
  • 在完成回溯后，添加起点，并反转 pathPlaces，使其顺序从起点到目标点。

8. 返回路径

1
return Path(pathPlaces.front(), pathPlaces.back(), distances[endId]);
  • 创建并返回一个 Path 对象，其中包含起点、终点和计算得到的最短距离。

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
Path findShortestPath(int startId, int endId) {
    // Dijkstra 算法
    std::unordered_map<int, double> distances; // 存储从起点到各点的距离
    std::unordered_map<int, int> previous; // 记录经过的路径
    std::priority_queue<std::pair<double, int>, std::vector<std::pair<double, int>>, std::greater<>> minHeap;
    
    // 初始化距离
    for (const auto& place : places) {
        distances[place.first] = std::numeric_limits<double>::infinity(); // 初始化为无穷大
    }
    distances[startId] = 0; // 起点到自己的距离为 0
    minHeap.push({ 0, startId }); // 将起点加入优先队列
    
    while (!minHeap.empty()) {
        int currentId = minHeap.top().second;
        double currentDistance = minHeap.top().first;
        minHeap.pop();
        
        // 提前结束的条件
        if (currentId == endId) {
            break;
        }
        
        // 遍历邻接节点
        for (const auto& neighbor : adjacencyList[currentId]) {
            int neighborId = neighbor.first;
            double edgeWeight = neighbor.second;
            
            double newDistance = currentDistance + edgeWeight; // 计算新距离
            if (newDistance < distances[neighborId]) {
                distances[neighborId] = newDistance; // 更新距离
                previous[neighborId] = currentId; // 更新 PATH
                minHeap.push({ newDistance, neighborId }); // 添加到优先队列
            }
        }
    }
    
    // 回溯路径
    if (previous.find(endId) == previous.end()) {
        return Path(places[startId], places[endId], std::numeric_limits<double>::infinity()); // 返回无效路径
    }
    
    std::vector<Place> pathPlaces;
    for (int at = endId; at != startId; at = previous[at]) {
        pathPlaces.push_back(places[at]);
        if (previous.find(at) == previous.end()) {
            return Path(places[startId], places[endId], std::numeric_limits<double>::infinity()); // 如果没有路径，返回无效路径
        }
    }
    pathPlaces.push_back(places[startId]); // 添加起点
    std::reverse(pathPlaces.begin(), pathPlaces.end()); // 反转路径顺序

    // 创建并返回 Path 对象
    return Path(pathPlaces.front(), pathPlaces.back(), distances[endId]);
}