我已经可以使用Dijkstra的算法找到两个顶点之间的最短路径：wiki Dijkstra's .
但 . 我的一些边缘意味着用作“检查点”，因为您必须经过至少一个检查点才能使路线可用 .
有时，算法会找到一条不包含这些边缘检查点的路径 . 在那种情况下，我想找到第二个 . 最短路线 - 如果该路线也不包含检查点，则找到第3个路线 . 最短的路线，等等 .
有什么想法让我入手？
编辑：
是否有可能通过第一条路线上的所有前辈，然后从前任到目的地运行Dijkstras（并排除前任下一个goto顶点的原始选择） . 通过这种方式，我可以找到所有可能的路线，然后将它们相互比较？
例 .
A =源Z =目的地
最短路径：A - > B - > C - > D - > Z.
第2位 . 最短路径：A - > B - > C - > D - >“成本最低的顶点，非Z”（如果在当前尝试中找不到可用路径，则通过所有D的未访问邻居循环）
如果是第二最短路径也不包含检查点，尝试第3个最短路径
3 . 最短路径：A - > B - > C - >顶点成本最低，不是D
或者这种解决方案无论如何都不可能？
编辑2：
可能很难看到，但紫色的1x3像素是顶点 . 黄色的道路是边缘，粉红色的3x3像素也是如此 . 粉红色的也是所谓的检查站 . 所以我必须找到最短的路线并至少经过一个检查站 .
5 回答
有几种方法可以尝试使这项工作 .
我们称S为起始节点，D为目标节点，I为中间节点 .
[单个中间节点]一个简单但次优的解决方案是使用从S到I的Dijkstra然后将Dijkstra的结果从I添加到D.
[多个中间节点]正如Niklas B.指出的可行方法是“从S和D构建最短路径树 . 对于每个中间节点A，检查d（S，A）d（T，A） . 最小值是解决方案 . 运行时间是Dijkstra的两倍，例如带有二进制堆的O（（nm）log n“ .
对于每个节点，您的成本最低，而不是成本最低，其中n是访问所需的检查点数 . 假设你说你需要N / M和订单，哪个N无关紧要 .
然后，当您传播成本时，您将跟踪检查点并更新相应的n插槽以获取所需信息 . 您可能希望将n限制为最小值，因为如果您需要2个检查点并传递3，则仍然有2个，但额外值没有值 .
您还可以将其转换为TSP问题以获得最佳路线：
对起始节点S和中间节点I使用正常权重
使用从S到节点E的无限权重（我们只想删除/忽略连接开始和结束点的往返）
使用0权重连接终点E和起点S.
现在为每个检查点：
将检查点添加为基本行程的中间点
使用TSP计算巡回长度，使用Dijkstra计算节点之间的距离并记住通过此检查点的长度
这些旅行中最短的是最佳旅行，并且只通过一个检查点 .
我的建议是 - 添加更多维度来存储chekpoints传递的内容 .
因此，状态
(x1,x2)将替换为：(x1,x2,c1...c_n)其中c1..cn是每个检查点的布尔标志 .边缘
(x1,x2)->(y1,y2)将被替换为：(x1,x2, c1..cn)->(y1,y2, c1..cn)表示非检查点状态(x1,x2, c1..cn)->(y1,y2, c1..c(x-1), true ,c(x+1)..cn)用于检查点状态cx任何
c1..cn搜索算法本身是相同的，但状态的数量将乘以
2^nedit: 此外，如果需要匹配至少一个（不是很少的不同）检查点，矢量
c1..cn可以被一个标志替换，该标志将描述至少一个检查点通过 .根据图表更改的频率，您可以尝试使用Floyd Warshall算法 . 它将帮助您构建一个矩阵，显示任何节点对之间的最短路径 . 一旦你有了这个，你可以使用Saverio Terracciano的答案迭代你的检查点，找出哪个检查点是最好的检查点 .