Dijkstra的（或其他最短路径算法），其中终端节点可以启动节点 [英] Dijkstra's (or other shortest path algorithm) where end node can be start node

问题描述

传统的*实现Dijkstra的不处理好这种情况。我想我已经想出了一些解决方案，将工作，但他们不是特别优雅**。这是一个已知的问题与标准的解决方案？

The traditional* implementation of Dijkstra's does not handle this case well. I think I've come up with some solutions that will work, but they are not particularly elegant**. Is this is a known problem with a standard solution?

这是假设的不平凡的解决方案，即一个路径像A-> B-> C-> A，而不只是A->一个。

This is assuming the non-trivial solution i.e. a path like A->B->C->A rather than just A->A.

*当我说传统的我的意思是标记每个节点所访问。

* When I say traditional I mean marking each node as visited.

**存储的时间和每一节点已被访问的数目和基础终止条件对端节点是否是开始节点

** Storing the number of times each node has been visited and basing the terminating conditions on whether the end node is the start node.

推荐答案

拆分为两个节点，所谓的START和目标。

Split A into two nodes, called START and GOAL.

对于任何边缘A-系列> X添加一个边缘开始 - > X

For any edge A->x add an edge START->x

对于任何边缘Y-> a添加边缘Y->目标

For any edge y->A add an edge y->GOAL

请所有其他边缘不变。

然后使用常规Dijkstra解决从开始的路径，目标

Then use normal Dijkstra to solve for the path from START to GOAL

这篇关于Dijkstra的（或其他最短路径算法），其中终端节点可以启动节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！