Generic Dijkstra: correctness and tractability

04/28/2022
by   Ireneusz Szcześniak, et al.
0

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 it 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. We also argue the stated problem is tractable by analyzing the size of the search space in the worst-case.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset