在图中找到最安全的路线，但要防止将最快路线的旅行时间加倍？
Find safest route in graph but prevent doubling the travel time of the fastest route?
我的大学项目是为我居住的城市设计一个路线规划器，计算街道之间的最短路线。 （旅行推销员）
在 C# 中，我使用图形来存储所有街道。目前我可以使用 Dijkstra 算法在加权图中找到两条街道之间的最短路线，第一部分完成:)
我的下一个任务是计算最安全的转弯路线。每条街道上都有一个事故百分比（例如，根据道路事故历史，发生车祸的几率为 0.4%）。我需要计算最安全的路线，但是要解决用户是否希望尽可能走最安全的路线，但不要将他们的旅行时间加倍而不是最快路线的问题。
谁能告诉我他们认为最好的方法是什么？
我想出的一个方法是在到达最终目的地之前取最后访问过的街道，删除该节点并计算没有该节点的路线，对 10 条路线这样做并选择累积事故最少的一条百分比，但这听起来也是最糟糕的做法。
你们能给我什么maths/logic/algorithms？用户应该输入什么？例如他们愿意慢多少的门槛？ C#，java，伪代码
非常感谢大家
您可以从 运行 一个普通的 Dijkstra 算法开始，这样您就知道最快的路线是什么，这样您就知道什么时候最安全的路线超过了这个成本。
然后您可以再次 运行 它以安全作为主要成本函数，但也可以计算距离以排除一些路线。起初我认为这可以像普通的 Dijkstra 算法一样完成，但是通过为每个节点（前一个节点、成本和安全值）存储一个有序列表。问题在于，距离和安全显然是独立的（实际上存在某种相关性，但我们不知道如何建模）。这是一个问题，因为您需要防止路线早期的长距离错误地导致您拒绝路线后期的选择。
如果您可以在部分路线上应用距离限制，这就不是问题。也就是说，如果它的长度超过从起点到该节点的最短路线的两倍，则您不接受到任何中间节点的路由。我知道这与您所说的不完全一样，因为您询问的是仅限制到最终节点的路由长度，但也许它仍然可以帮助您考虑整体解决方案。对于它的价值，它也可能更现实。
记得正确组合崩溃概率，不能只加起来。如果我们假设旅程在第一次碰撞时停止，那么您将计算碰撞概率为道路 1 碰撞概率加上（道路 1 不碰撞概率 * 道路 2 碰撞概率）加上（得到概率安全地到达 3 号道路 * 3 号道路上发生碰撞的概率) 等（抱歉，如果这是显而易见的）。
鉴于您的评论，我将详细解释概率（您最好查看概率而不是赔率）
如果你想要一个允许在撞车后继续进行的整体安全措施，那么它会变得更加复杂。
如果您在发生碰撞时停下来，那么这就是计算碰撞恰好一次的概率的问题。
因此，如果出现以下情况，路线会发生崩溃：
你在第一条路上撞车（概率 p1）或
你不会在第一条路上撞车（概率 1-p1），但你会在第二条路上撞车（概率 p2）。或者
...
你不会在 n-1 路上撞车（1-运行ning 总计如上所述）但你确实在 n 路上撞车（概率 pn）
这样一来，您就不会遇到 50% 的道路 1 和 2 发生碰撞的可能性加起来不等于 100% 的总体可能性的情况 - 而且您也永远不会比这更大。
现实中很多车祸发生在路口，根据你是左转还是右转，车祸的概率会有所不同 - 所以概率（实际上）不仅仅取决于道路的安全系数在路口之间以及路线如何将它们结合起来。
概率应根据使用情况加权（查找条件概率），因此如果在可能需要建模的很少使用的道路上发生 20 起事故，则事故概率更高，因为繁忙的道路上有 50 起事故同一时间段。
我的大学项目是为我居住的城市设计一个路线规划器，计算街道之间的最短路线。 （旅行推销员）
在 C# 中，我使用图形来存储所有街道。目前我可以使用 Dijkstra 算法在加权图中找到两条街道之间的最短路线，第一部分完成:)
我的下一个任务是计算最安全的转弯路线。每条街道上都有一个事故百分比（例如，根据道路事故历史，发生车祸的几率为 0.4%）。我需要计算最安全的路线，但是要解决用户是否希望尽可能走最安全的路线，但不要将他们的旅行时间加倍而不是最快路线的问题。
谁能告诉我他们认为最好的方法是什么？
我想出的一个方法是在到达最终目的地之前取最后访问过的街道，删除该节点并计算没有该节点的路线，对 10 条路线这样做并选择累积事故最少的一条百分比，但这听起来也是最糟糕的做法。
你们能给我什么maths/logic/algorithms？用户应该输入什么？例如他们愿意慢多少的门槛？ C#，java，伪代码
非常感谢大家
您可以从 运行 一个普通的 Dijkstra 算法开始，这样您就知道最快的路线是什么，这样您就知道什么时候最安全的路线超过了这个成本。
然后您可以再次 运行 它以安全作为主要成本函数，但也可以计算距离以排除一些路线。起初我认为这可以像普通的 Dijkstra 算法一样完成，但是通过为每个节点（前一个节点、成本和安全值）存储一个有序列表。问题在于，距离和安全显然是独立的（实际上存在某种相关性，但我们不知道如何建模）。这是一个问题，因为您需要防止路线早期的长距离错误地导致您拒绝路线后期的选择。
如果您可以在部分路线上应用距离限制，这就不是问题。也就是说，如果它的长度超过从起点到该节点的最短路线的两倍，则您不接受到任何中间节点的路由。我知道这与您所说的不完全一样，因为您询问的是仅限制到最终节点的路由长度，但也许它仍然可以帮助您考虑整体解决方案。对于它的价值，它也可能更现实。
记得正确组合崩溃概率，不能只加起来。如果我们假设旅程在第一次碰撞时停止，那么您将计算碰撞概率为道路 1 碰撞概率加上（道路 1 不碰撞概率 * 道路 2 碰撞概率）加上（得到概率安全地到达 3 号道路 * 3 号道路上发生碰撞的概率) 等（抱歉，如果这是显而易见的）。
鉴于您的评论，我将详细解释概率（您最好查看概率而不是赔率）
如果你想要一个允许在撞车后继续进行的整体安全措施，那么它会变得更加复杂。 如果您在发生碰撞时停下来，那么这就是计算碰撞恰好一次的概率的问题。 因此，如果出现以下情况，路线会发生崩溃：
你在第一条路上撞车（概率 p1）或
你不会在第一条路上撞车（概率 1-p1），但你会在第二条路上撞车（概率 p2）。或者
... 你不会在 n-1 路上撞车（1-运行ning 总计如上所述）但你确实在 n 路上撞车（概率 pn）
这样一来，您就不会遇到 50% 的道路 1 和 2 发生碰撞的可能性加起来不等于 100% 的总体可能性的情况 - 而且您也永远不会比这更大。
现实中很多车祸发生在路口，根据你是左转还是右转，车祸的概率会有所不同 - 所以概率（实际上）不仅仅取决于道路的安全系数在路口之间以及路线如何将它们结合起来。
概率应根据使用情况加权（查找条件概率），因此如果在可能需要建模的很少使用的道路上发生 20 起事故，则事故概率更高，因为繁忙的道路上有 50 起事故同一时间段。