c++实现最短路径问题

在C++中实现最短路径问题，常用的数据结构包括优先队列（通常使用`std::priority_queue`）和邻接表（`std::vector`或`std::unordered_map`等）。这里以Dijkstra算法为例，这是寻找无权图中最短路径的标准方法。

以下是一个简化的C++代码片段，展示了如何使用Dijkstra算法找到两个顶点之间的最短路径：

#include <iostream>
#include <vector>
#include <queue>
#include <limits>

// 边的结构体
struct Edge {
    int src, dest, weight;
};

bool compareEdges(const Edge &a, const Edge &b) { return a.weight < b.weight; }

void dijkstra(std::vector<Edge> edges, std::vector<int> &dist, std::vector<bool> &visited, int start) {
    dist.resize(edges.size(), std::numeric_limits<int>::max());
    dist[start] = 0;

    std::priority_queue<Edge, std::vector<Edge>, decltype(compareEdges)> pq(compareEdges);
    visited.assign(edges.size(), false);

    pq.push({start, -1, 0}); // push with negative destination for priority queue

    while (!pq.empty()) {
        Edge currentEdge = pq.top();
        pq.pop();

        if (visited[currentEdge.src]) continue;
        visited[currentEdge.src] = true;

        for (const Edge &nextEdge : edges) {
            if (nextEdge.dest == currentEdge.src && nextEdge.weight + currentEdge.weight < dist[nextEdge.dest]) {
                dist[nextEdge.dest] = nextEdge.weight + currentEdge.weight;
                pq.push({nextEdge.dest, currentEdge.src, dist[nextEdge.dest]});
            }
        }
    }
}

int main() {
    // ... (添加你的边和顶点数据)
    std::vector<Edge> edgeList = ...;
    std::vector<int> dist(edgeList.size());
    std::vector<bool> visited(edgeList.size());

    dijkstra(edgeList, dist, visited, 0); // 从顶点0开始
    // ... (获取并打印结果)
    return 0;
}

在这个例子中，`edgeList`是包含每个边的信息的边列表，`dist`数组用于存储每个顶点到起始顶点的最短距离，`visited`数组则标记哪些顶点已被处理。