分支限界法求解单源最短路径问题c++

### 使用分支限界法求解单源最短路径问题 分支限界法是一种用于解决组合优化问题的有效方法。它通过设置界限来减少搜索空间，从而提高效率。对于单源最短路径问题，可以利用优先队列（通常是一个最小堆）作为活结点表，并基于当前节点到起点的距离加上估计距离来进行剪枝。 以下是使用C++实现分支限界法求解单源最短路径问题的一个例子： #### 实现代码 ```cpp #include <iostream> #include <vector> #include <queue> #include <climits> using namespace std; struct Node { int vertex; int costSoFar; }; // 定义比较函数以便于构建最小堆 struct CompareNode { bool operator()(const Node& lhs, const Node& rhs) { return lhs.costSoFar > rhs.costSoFar; } }; void branchAndBoundSSSP(int startVertex, vector<vector<pair<int, int>>>& graph, int numVertices) { priority_queue<Node, vector<Node>, CompareNode> pq; vector<int> distance(numVertices, INT_MAX); // 初始化起始顶点 distance[startVertex] = 0; pq.push(Node{startVertex, 0}); while (!pq.empty()) { Node current = pq.top(); pq.pop(); int u = current.vertex; int costU = current.costSoFar; // 如果已经找到了更优的路径，则跳过此节点 if (costU > distance[u]) continue; // 遍历相邻节点 for (auto& edge : graph[u]) { int v = edge.first; int weightUV = edge.second; // 计算新的成本并更新如果找到更短路径 if (distance[u] + weightUV < distance[v]) { distance[v] = distance[u] + weightUV; pq.push(Node{v, distance[v]}); } } } // 输出结果 cout << "Shortest distances from source:" << endl; for (int i = 0; i < numVertices; ++i) { cout << "To vertex " << i << ": "; if (distance[i] == INT_MAX) { cout << "INF"; } else { cout << distance[i]; } cout << endl; } } int main() { int numVertices = 5; vector<vector<pair<int, int>>> graph(numVertices); // 构建图 graph[0].push_back({1, 2}); graph[0].push_back({3, 8}); graph[1].push_back({2, 7}); graph[1].push_back({3, 6}); graph[2].push_back({4, 1}); graph[3].push_back({4, 9}); int startVertex = 0; branchAndBoundSSSP(startVertex, graph, numVertices); return 0; } ``` 在这个实现中，我们定义了一个`Node`结构体表示每个状态中的顶点及其累计代价。为了加速寻找下一个最优候选者的过程，采用了优先队列存储这些状态。每次从队列取出具有最低累积开销的状态进行扩展，直到到达目标或者无法再改进为止[^1]。 #### 时间复杂度分析 该算法的时间复杂度主要取决于边的数量E以及顶点数量V。由于每条边最多被处理两次（一次正向，一次反向），因此总体时间复杂度接近O(E log V)，其中log V来源于维护最小堆的操作[^1]。 ---