时间戳

首页 > 解决方案 > 如何使用 PostgreSQL pgrouting 函数找到具有 MOST K 边的两个几何点之间的最短路径？

postgresql - 如何使用 PostgreSQL pgrouting 函数找到具有 MOST K 边的两个几何点之间的最短路径？

问题描述

我已经设置了包含顶点和边的表格（代表机场和它们之间的路线）。使用以下查询，我可以获得两点之间的最短路径。

SELECT p.seq, p.node, p.cost, r.geom as edge_geom, c.name
FROM
pgr_dijkstra(
        'SELECT id, source, target, distance AS cost FROM airport_route',
        (SELECT id FROM airport WHERE code = 'HEL'),
        (SELECT id FROM airport WHERE code = 'LAS'),
        TRUE
    ) AS p
    LEFT JOIN airport_route AS r ON p.edge = r.id
    LEFT JOIN airport AS c ON p.node = c.id
ORDER BY
p.seq;

结果如下： 查询结果

问题是：

如何找到具有最多 K 个边的这两个点之间的最短路径？

安装了 postgis 和 pgrouting；网络拓扑已创建

标签： postgresqlshortest-pathdijkstrapgrouting

解决方案

经过大量研究，我注意到 Dijkstra 在本质上不能对边缘数量进行任何限制。所以我不得不创建一个受贝尔曼福特启发的算法。

有关详细信息，请查看以下存储库：

https://github.com/majidakbari/flight

推荐阅读