首先，假设你已经有一个 2D 数组表示 DEM 数据，每个元素的值表示某个位置的高度。你可以根据特定的规则来决定哪些区域是障碍物或无效值。

1. Bellman-Ford 算法的实现

#include <iostream>
#include <vector>
#include <climits>
#include <queue>using namespace std;// 定义一个邻接列表表示图
struct Edge {int u, v, weight;
};class BellmanFord {
public:BellmanFord(int n) : V(n), dist(n, INT_MAX) {}void addEdge(int u, int v, int weight) {edges.push_back({u, v, weight});}// Bellman-Ford算法求最短路径void run(int start) {dist[start] = 0;// 放松所有边 V-1 次for (int i = 0; i < V - 1; ++i) {for (auto& edge : edges) {if (dist[edge.u] != INT_MAX && dist[edge.u] + edge.weight < dist[edge.v]) {dist[edge.v] = dist[edge.u] + edge.weight;}}}// 检查负权环for (auto& edge : edges) {if (dist[edge.u] != INT_MAX && dist[edge.u] + edge.weight < dist[edge.v]) {cout << "Negative weight cycle detected!" << endl;return;}}}int getDistance(int vertex) {return dist[vertex];}private:int V;vector<Edge> edges;vector<int> dist;
};int main() {int V = 5; // 假设图中有5个节点BellmanFord bf(V);// 示例: 添加一些边bf.addEdge(0, 1, 10);bf.addEdge(0, 2, 5);bf.addEdge(1, 2, 2);bf.addEdge(1, 3, 1);bf.addEdge(2, 1, 3);bf.addEdge(2, 3, 9);bf.addEdge(3, 4, 4);int start = 0;  // 指定起点bf.run(start);// 输出从起点到每个点的最短距离for (int i = 0; i < V; ++i) {cout << "Distance from " << start << " to " << i << ": " << bf.getDistance(i) << endl;}return 0;
}

2. SPFA (Shortest Path Faster Algorithm) 算法的实现

#include <iostream>
#include <vector>
#include <climits>
#include <queue>using namespace std;class SPFA {
public:SPFA(int n) : V(n), dist(n, INT_MAX), inQueue(n, false) {}void addEdge(int u, int v, int weight) {adj[u].push_back({v, weight});}void run(int start) {dist[start] = 0;queue<int> q;q.push(start);inQueue[start] = true;while (!q.empty()) {int u = q.front();q.pop();inQueue[u] = false;for (auto& edge : adj[u]) {int v = edge.first, weight = edge.second;if (dist[u] + weight < dist[v]) {dist[v] = dist[u] + weight;if (!inQueue[v]) {q.push(v);inQueue[v] = true;}}}}}int getDistance(int vertex) {return dist[vertex];}private:int V;vector<vector<pair<int, int>>> adj;  // 邻接表，存储边（目标节点，边的权重）vector<int> dist;vector<bool> inQueue;  // 判断节点是否已经在队列中
};int main() {int V = 5;  // 假设图中有5个节点SPFA spfa(V);// 示例: 添加一些边spfa.addEdge(0, 1, 10);spfa.addEdge(0, 2, 5);spfa.addEdge(1, 2, 2);spfa.addEdge(1, 3, 1);spfa.addEdge(2, 1, 3);spfa.addEdge(2, 3, 9);spfa.addEdge(3, 4, 4);int start = 0;  // 指定起点spfa.run(start);// 输出从起点到每个点的最短距离for (int i = 0; i < V; ++i) {cout << "Distance from " << start << " to " << i << ": " << spfa.getDistance(i) << endl;}return 0;
}

3. 处理 DEM 数据和障碍物
   你可以将 DEM 数据表示为一个二维数组，每个位置的值是该位置的高度。假设高度低于某个阈值的区域表示障碍物或无效值。

#include <iostream>
#include <vector>using namespace std;bool isObstacle(int height, int threshold) {return height <= threshold;
}void buildGraphFromDEM(const vector<vector<int>>& dem, int threshold, SPFA& spfa) {int rows = dem.size();int cols = dem[0].size();// 邻接表构建for (int i = 0; i < rows; ++i) {for (int j = 0; j < cols; ++j) {if (isObstacle(dem[i][j], threshold)) {continue;  // 如果是障碍物或无效值，则跳过}// 将四个方向的邻接节点添加到图中if (i > 0 && !isObstacle(dem[i - 1][j], threshold)) {  // 上spfa.addEdge(i * cols + j, (i - 1) * cols + j, 1);}if (i < rows - 1 && !isObstacle(dem[i + 1][j], threshold)) {  // 下spfa.addEdge(i * cols + j, (i + 1) * cols + j, 1);}if (j > 0 && !isObstacle(dem[i][j - 1], threshold)) {  // 左spfa.addEdge(i * cols + j, i * cols + (j - 1), 1);}if (j < cols - 1 && !isObstacle(dem[i][j + 1], threshold)) {  // 右spfa.addEdge(i * cols + j, i * cols + (j + 1), 1);}}}
}int main() {vector<vector<int>> dem = {{1, 1, 1, 0, 1},{1, 0, 1, 1, 1},{1, 1, 0, 1, 0},{1, 1, 1, 1, 1}};int threshold = 0;  // 假设 0 以下为障碍物int V = dem.size() * dem[0].size();SPFA spfa(V);buildGraphFromDEM(dem, threshold, spfa);int start = 0;  // 从 (0, 0) 点出发spfa.run(start);// 输出从起点到目标点的最短距离int target = 4;  // 比如目标点为 (0, 4)cout << "Distance from start to target: " << spfa.getDistance(target) << endl;return 0;
}

代码解释：
Bellman-Ford 算法：该算法是用于解决单源最短路径问题的经典算法。它逐步放松所有的边
𝑉
−
1
V−1 次，适用于带负权边的情况。
SPFA 算法：SPFA 是一种基于队列的改进算法，它在大多数情况下比 Bellman-Ford 快。
DEM 数据处理：通过 isObstacle 函数判断高度是否低于给定的阈值，从而判断是否为障碍物。如果是障碍物，则不添加边。
运行：
程序会自动过滤掉无效区域（障碍物）并计算从起点到终点的最短路径。
可以通过修改 dem 和 threshold 来适配不同的地图和障碍物条件。
如果你有特定的数据或者需要进一步的功能扩展，随时告诉我！