Generic Dijkstra is a novel algorithm for finding the optimal shortest path in both wavelength-division multiplexed networks (WDM) and elastic optical networks (EON), claimed to outperform known algorithms considerably. Because of its novelty, it has not been independently implemented and verified. Its time complexity also remains unknown. In this paper, we perform run-time analysis and show that Generic Dijkstra running time grows quadratically with the number of graph vertices and logarithmically with the number of edge units. We also discover that the running time of the Generic Dijkstra algorithm in the function of network utilization is not monotonic, as peak running time is at approximately 0.25 network utilization. Additionally, we provide an independent open source implementation of Generic Dijkstra in the Python language. We confirm the correctness of the algorithm and its superior performance. In comparison to the Filtered Graphs algorithm, Generic Dijkstra is approximately 2.3 times faster in networks with 25 to 500 nodes, and in 90% of calls its computation takes less time.
翻译:通用 Dijkstra 是一个新奇的算法, 用于寻找波长分布多维网络( WDM) 和弹性光学网络( EON) 中的最佳最短路径, 据称其效果大大超过已知的算法。 由于它的新颖性, 它尚未独立实施和验证。 它的时间复杂性仍然未知。 在本文中, 我们进行运行时间分析, 并显示通用 Dijkstra 运行时间随着图形脊椎数和边端单位数的对数增长四进制。 我们还发现, 通用 Dijkstra 算法在网络使用功能中的运行时间不是单调的, 因为峰值运行时间大约为0. 25 个网络的使用时间。 此外, 我们提供了Python 语言中通用 Dijkstra 的独立的开放源执行。 我们确认算法的正确性及其优性。 与过滤式图形算法相比, 通用 Djkstra 在有 25 到 500 节点的网络中, 其计算速度大约是 2.3 的2.3 倍 。