双向dijkstra c++

双向Dijkstra算法是一种从起点和终点同时进行搜索的双向搜索算法，用于寻找带权有向图的最短路径。相比传统的Dijkstra算法，双向Dijkstra算法可以大大减少搜索时间，将搜索时间缩短至原来的1/3[^1]。

以下是C++实现双向Dijkstra算法的代码示例[^1]：

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

using namespace std;

const int INF = 1e9;

// 定义图的边
struct Edge {
    int to;
    int weight;
};

// 双向Dijkstra算法
int bidirectionalDijkstra(vector<vector<Edge>>& graph, int start, int end) {
    int n = graph.size();
    
    // 定义起点到各个顶点的距离
    vector<int> dist_start(n, INF);
    // 定义终点到各个顶点的距离
    vector<int> dist_end(n, INF);
    
    // 定义起点到各个顶点的最短路径是否已经确定
    vector<bool> visited_start(n, false);
    // 定义终点到各个顶点的最短路径是否已经确定
    vector<bool> visited_end(n, false);
    
    // 定义起点到各个顶点的距离
    dist_start[start] = 0;
    // 定义终点到各个顶点的距离
    dist_end[end] = 0;
    
    // 定义起点到各个顶点的优先队列
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq_start;
    // 定义终点到各个顶点的优先队列
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq_end;
    
    // 将起点和终点分别加入起点和终点的优先队列
    pq_start.push({0, start});
    pq_end.push({0, end});
    
    while (!pq_start.empty() && !pq_end.empty()) {
        // 从起点开始搜索
        int u_start = pq_start.top().second;
        pq_start.pop();
        
        // 从终点开始搜索
        int u_end = pq_end.top().second;
        pq_end.pop();
        
        // 如果起点和终点相遇，则返回最短路径
        if (visited_start[u_end] || visited_end[u_start]) {
            return dist_start[u_end] + dist_end[u_start];
        }
        
        // 更新起点到相邻顶点的距离
        for (Edge& e : graph[u_start]) {
            int v = e.to;
            int weight = e.weight;
            
            if (!visited_start[v] && dist_start[u_start] + weight < dist_start[v]) {
                dist_start[v] = dist_start[u_start] + weight;
                pq_start.push({dist_start[v], v});
            }
        }
        
        // 更新终点到相邻顶点的距离
        for (Edge& e : graph[u_end]) {
            int v = e.to;
            int weight = e.weight;
            
            if (!visited_end[v] && dist_end[u_end] + weight < dist_end[v]) {
                dist_end[v] = dist_end[u_end] + weight;
                pq_end.push({dist_end[v], v});
            }
        }
        
        // 标记起点和终点已经确定最短路径
        visited_start[u_start] = true;
        visited_end[u_end] = true;
    }
    
    // 如果没有找到最短路径，则返回-1
    return -1;
}

int main() {
    int n = 5; // 图的顶点数
    int start = 0; // 起点
    int end = 4; // 终点
    
    // 定义图的邻接表表示
    vector<vector<Edge>> graph(n);
    
    // 添加边
    graph[0].push_back({1, 1});
    graph[0].push_back({2, 4});
    graph[1].push_back({2, 2});
    graph[1].push_back({3, 5});
    graph[2].push_back({3, 1});
    graph[2].push_back({4, 3});
    graph[3].push_back({4, 1});
    
    int shortestPath = bidirectionalDijkstra(graph, start, end);
    
    cout << "The shortest path from " << start << " to " << end << " is: " << shortestPath << endl;
    
    return 0;
}