完善一下182行195行两个遍历，时间越短越好，一直没有优化成功

Question

完善一下182行195行两个遍历，时间越短越好，一直没有优化成功，下面是代码和要求

Answer 1

引自免费微信小程序：皆我百晓生

首先，我们需要分析提供的代码片段，确定哪些部分可以优化。然后，我们将讨论如何根据给定的问题需求改进代码。

1. 首先，让我们检查代码中的主要瓶颈。在这个情况下，代码片段没有提供，所以我将假设它是一个标准的Dijkstra算法实现。在这种情况下，一个可能的优化是使用优先队列（如std::priority_queue），而不是简单的队列。优先队列可以保证每次弹出的都是距离起点最近的节点，从而减少搜索次数。

2. 另外，为了加速查找和插入操作，可以考虑使用哈希集合（如std::unordered_set或std::unordered_map）来存储已经访问过的节点，而不是线性遍历整个节点列表。

3. 对于问题中的其他部分，例如路网数据的存储和遍历，我们可以选择邻接表来表示图，因为它更节省空间，对于稀疏图来说效率更高。而邻接矩阵则适用于稠密图。

以下是针对这些优化的代码改进：

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <string>
#include <sstream>

struct Node {
    int id;
    double lon;
    double lat;
};

struct Edge {
    int from;
    int to;
    double weight;
};

using namespace std;

vector<Node> readNodes(const string& filename) {
    // Read and parse node data...
}

vector<Edge> readEdges(const string& filename) {
    // Read and parse edge data...
}

unordered_map<int, vector<Edge>> createGraph(vector<Node>& nodes, vector<Edge>& edges) {
    unordered_map<int, vector<Edge>> graph;
    for (const auto& edge : edges) {
        graph[edge.from].push_back(edge);
        graph[edge.to].push_back({edge.to, edge.from, edge.weight}); // Add reverse edge for undirected graph
    }
    return graph;
}

pair<vector<int>, double> dijkstra(unordered_map<int, vector<Edge>>& graph,
                                   const unordered_set<int>& visited,
                                   int start, int end) {
    priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> pq;
    pq.push({0, start});

    while (!pq.empty()) {
        double dist = pq.top().first;
        int curr = pq.top().second;
        pq.pop();

        if (visited.find(curr) != visited.end()) continue;
        visited.insert(curr);

        if (curr == end) break;

        for (const auto& edge : graph[curr]) {
            double newDist = dist + edge.weight;
            if (newDist < DijkstraDistanceMap[edge.to]) {
                DijkstraDistanceMap[edge.to] = newDist;
                pq.push({newDist, edge.to});
            }
        }
    }

    vector<int> path;
    int curr = end;
    while (curr != -1) {
        path.push_back(curr);
        curr = prevNodeMap[curr];
    }
    reverse(path.begin(), path.end());

    return {path, DijkstraDistanceMap[end]};
}

int main() {
    vector<Node> nodes = readNodes("wuhanroad_node.csv");
    vector<Edge> edges = readEdges("wuhanroad.csv");

    unordered_map<int, vector<Edge>> graph = createGraph(nodes, edges);
    unordered_set<int> visited;
    unordered_map<int, double> DijkstraDistanceMap; // Distance from start to each node
    unordered_map<int, int> prevNodeMap; // Previous node in the shortest path

    // Initialize all distances to infinity and set previous nodes to -1
    for (const auto& node : nodes) {
        DijkstraDistanceMap[node.id] = numeric_limits<double>::max();
        prevNodeMap[node.id] = -1;
    }
    DijkstraDistanceMap[nodes[0].id] = 0; // Assuming nodes[0] is the start node

    pair<vector<int>, double> result = dijkstra(graph, visited, nodes[0].id, nodes[1].id); // Assuming nodes[1].id is the end node
    cout << "Shortest path: ";
    for (const auto& node_id : result.first) {
        cout << node_id << " -> ";
    }
    cout << "Total distance: " << result.second << endl;

    return 0;
}

这段代码包含了一个简化版的Dijkstra算法实现，以及一些基本的数据结构。注意，这里假设了输入文件的格式是正确的，并且在readNodes和readEdges函数中进行了适当的解析。此外，我们还需要定义路网数据文件的读取函数。

关于问题(2)，要计算一天内所有最短路径长度并与其实际行驶长度进行比较，你需要读取GPS轨迹数据，从中提取所有的出发点和目的地对，然后对每一对执行Dijkstra算法。这个过程可能非常耗时，因此你可能需要考虑使用多线程或者并行处理来提高性能。

对于问题(1)，你可以通过读取路网文件来计算节点数和边数。至于存储方式，由于武汉三环内的路网很可能是稀疏的，所以使用邻接表更为合适。邻接矩阵的优点在于可以通过索引快速查询相邻节点，但缺点是当图变得非常大时，会占用大量内存。而邻接表则只存储实际存在的边，更适合稀疏图，但在查询相邻节点时可能会慢一些。