怎样在C++中使用A*或Dijkstra算法进行路径规划？

在C++中使用A*（A-Star）或Dijkstra算法进行路径规划涉及到图形搜索和图论的概念。这两种算法都是用于寻找从起点到终点的最短路径，但A*算法通常更快，因为它利用启发式信息加速搜索。

**1. Dijkstra算法**：
- 它是一种广度优先搜索（BFS），适合于所有边的权重非负的情况。
- 首先，设置起点的距离为0，其余节点距离无穷大。然后逐层扩展，每次选择当前未访问节点中最短距离的那个节点，更新其相邻节点的距离并标记已访问。

#include <queue>
#include <limits>

// 假设Graph是一个邻接列表表示的图结构
void dijkstra(Graph& graph, int start, std::vector<int>& distances, std::vector<bool>& visited) {
    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<> > pq;
    distances[start] = 0;
    pq.push({0, start});
    
    while (!pq.empty()) {
        int current = pq.top().second;
        pq.pop();
        if (visited[current]) continue;

        visited[current] = true;

        for (const auto& neighbor : graph.neighbors(current)) {
            int newDistance = distances[current] + graph.distance(current, neighbor);
            if (newDistance < distances[neighbor]) {
                distances[neighbor] = newDistance;
                pq.push({newDistance, neighbor});
            }
        }
    }
}

**2. A*算法**：
- 基于Dijkstra，引入了一个启发式函数h(n)估计从当前节点n到目标节点的“直接”距离。
- 搜索过程中同时考虑了已经走过的代价(g值)和剩余的估算代价(f值)。

#include <iostream>
#include <queue>
using namespace std;

struct Node {
    int node;
    int g;
    int h;
    int f;
    bool operator<(const Node &other) const { return f < other.f; }
};

void aStar(Graph& graph, int start, int end, std::vector<int>& distances, std::vector<Node>& path) {
    // 初始化
    Node startNode{start, 0, heuristic(start, end), heuristic(start, end)};
    Node current;
    distances[start] = 0;
    path[start] = startNode;
    
    priority_queue<Node> pq;
    pq.push(startNode);

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

        if (current.node == end)
            break;

        for (const auto& neighbor : graph.neighbors(current.node)) {
            int newG = current.g + graph.distance(current.node, neighbor);
            if (newG < distances[neighbor]) {
                distances[neighbor] = newG;
                path[neighbor] = Node(neighbor, newG, heuristic(neighbor, end), newG + heuristic(neighbor, end));
                pq.push(path[neighbor]);
            }
        }
    }
}

// 假设heuristic(node, target)返回两点之间的曼哈顿距离或欧几里得距离等
int heuristic(int node, int target) {
    // ...
}

**相关问题--:**
1. 如何定义和实现启发式函数？
2. 当图中存在负权重边时，应如何修改上述算法？
3. 对于大型图，这些算法的空间复杂度是多少？
4. 如何处理没有直达连接的目标节点的情况？