我有一个加权图 G={V,E,ETW}，其中 V 是节点集，E 是边集，ETW 是一组边时间窗口。边缘时间窗口是一个 3-Tuple (edge, starttime, endtime)，其含义是在区间 [starttime, endtime] 中给定的边缘不可用。现在的问题是找到一条从开始节点到结束节点的最短路径，在该路径中允许在节点处等待（在其时间窗口之后使用边）。
有人知道这个问题的算法吗？（最好是发表该算法的论文）
问问题
408 次
1 回答
0
假设边缘值是非负的，这仍然是dijkstra 的算法。你只需要稍微修改一下。
您必须进行以下修改 - 如果您正在查看的当前节点 v 具有传出边 e，由于边的时间窗口，这是不允许的，请添加从当前节点到达时间窗口末尾所需的时间时刻（到达节点 v 的时刻）到边的权重。否则算法保持不变。
于 2012-04-19T08:52:48.673 回答