5

不确定我的设计是否足以随着时间的推移解决总线路由问题。这是我的解决方案，主要步骤如下：

步骤 1）有一个代表所有边的边表（源和目标代表顶点（公共汽车站）：

postgres=# select id, source, target, cost from busedges;
 id | source | target | cost
----+--------+--------+------
  1 |      1 |      2 |    1
  2 |      2 |      3 |    1
  3 |      3 |      4 |    1
  4 |      4 |      5 |    1
  5 |      1 |      7 |    1
  6 |      7 |      8 |    1
  7 |      1 |      6 |    1
  8 |      6 |      8 |    1
  9 |      9 |     10 |    1
 10 |     10 |     11 |    1
 11 |     11 |     12 |    1
 12 |     12 |     13 |    1
 13 |      9 |     15 |    1
 14 |     15 |     16 |    1
 15 |      9 |     14 |    1
 16 |     14 |     16 |    1

第 2 步）有一个表格，代表巴士的详细信息，如时间、时间、边缘等。

注意：我已经为“from”和“to”列使用整数格式以获得更快的结果，因为我可以进行整数查询，但如果可用，我可以用任何更好的格式替换它。

postgres=# select id, "busedgeId", "busId", "from", "to" from busedgetimes;
 id | busedgeId | busId | from  |  to
----+-----------+-------+-------+-------
 18 |         1 |     1 | 33000 | 33300
 19 |         2 |     1 | 33300 | 33600
 20 |         3 |     2 | 33900 | 34200
 21 |         4 |     2 | 34200 | 34800
 22 |         1 |     3 | 36000 | 36300
 23 |         2 |     3 | 36600 | 37200
 24 |         3 |     4 | 38400 | 38700
 25 |         4 |     4 | 38700 | 39540

步骤 3) 使用 dijkstra 算法找到最近的路径。

步骤 4) 以最早的一阶从 busedgetimes 表中获取即将到来的公共汽车，以获得由 dijkstra 算法检测到的最近路径。

问题：我发现很难查询第 4 步。

例如：如果我将路径作为边 2、3、4，在上述记录中从源顶点 2 行进到目标顶点 5。要获得第一条边的第一条总线，这并不难，因为我可以简单地查询，from < 'expected departure' order by from desc但对于第二条边，from条件需要to第一个结果行的时间。此外，查询需要边缘 ID 过滤器。

如何在单个查询中实现这一目标？另外，请建议我是否有更好的设计？

谢谢

4

1 回答 1

7

我不确定我是否正确理解了您的问题。但是从其他行获取值可以通过窗口函数（https://www.postgresql.org/docs/current/static/tutorial-window.html）来完成：

演示：db<>fiddle

SELECT
    id,
    lag("to") OVER (ORDER BY id) as prev_to,
    "from",
    "to",
    lead("from") OVER (ORDER BY id) as next_from
FROM bustimes;

该lag函数将前一行的值移动到当前行中。该lead函数对下一行执行相同的操作。因此，您可以计算上次到达和当前出发之间的差异或类似的东西。

结果：

id   prev_to   from    to      next_from
18             33000   33300   33300
19   33300     33300   33600   33900
20   33600     33900   34200   34200
21   34200     34200   34800   36000
22   34800     36000   36300

请注意“from”和“to”是 PostgreSQL 中的保留字。最好选择其他名称。

于 2018-09-27T13:22:48.550 回答