0 algorithm dijkstra shortest-path graph-algorithm
Dijkstra的传统*实现并不能很好地处理这种情况.我想我已经提出了一些可行的解决方案,但它们并不是特别优雅**.这是标准解决方案的已知问题吗？
这是假设非平凡的解决方案,即类似A-> B-> C-> A的路径,而不仅仅是A-> A.
*当我说传统时,我的意思是将每个节点标记为已访问.
**存储每个节点的访问次数,并根据终端节点是否为起始节点的终止条件.
将A拆分为两个节点,称为START和GOAL.
对于任何边A-> x,添加边START-> x
对于任何边y-> A添加边y-> GOAL
保持所有其他边缘不变.
然后使用普通的Dijkstra来求解从START到GOAL的路径