论文标题
通用Dijkstra：正确性和障碍性
Generic Dijkstra: correctness and tractability
论文作者
论文摘要
最近提供的通用Dijkstra算法在具有连续和连续资源的网络中找到了最短的路径。该算法是在光网络的背景下提出的，但适用于具有有限和离散资源的网络。该算法没有正确的证明，并且存在较小的缺点。我们提供了缺少的证据，并为缺点提供了更正。为了证明正确的算法，我们将Bellman的最佳原则推广到具有部分排序的代数结构。我们还认为，可以通过分析最坏情况下的搜索空间的大小来解决问题。
The recently-proposed generic Dijkstra algorithm finds shortest paths in networks with continuous and contiguous resources. The algorithm was proposed in the context of optical networks, but is applicable to networks with finite and discrete resources. The algorithm was published without a proof of correctness, and with a minor shortcoming. We provide that missing proof and offer a correction to the shortcoming. To prove the algorithm correct, we generalize the Bellman's principle of optimality to algebraic structures with a partial ordering. We also argue the stated problem is tractable by analyzing the size of the search space in the worst-case.
