当前位置：首页 > article >正文

Bellman-Ford 和 SPFA 算法的实现DEM路径搜索

article 2024/11/20 14:23:48

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

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;
}

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;
}

处理 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 来适配不同的地图和障碍物条件。
如果你有特定的数据或者需要进一步的功能扩展，随时告诉我！

查看全文

http://www.kler.cn/a/401615.html