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 倍 。

0
下载
关闭预览

相关内容

Networking:IFIP International Conferences on Networking。 Explanation:国际网络会议。 Publisher:IFIP。 SIT: http://dblp.uni-trier.de/db/conf/networking/index.html
专知会员服务
52+阅读 · 2020年9月7日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
【深度学习视频分析/多模态学习资源大列表】
专知会员服务
91+阅读 · 2019年10月16日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
条件GAN重大改进!cGANs with Projection Discriminator
CreateAMind
8+阅读 · 2018年2月7日
gan生成图像at 1024² 的 代码 论文
CreateAMind
4+阅读 · 2017年10月31日
自然语言处理 (NLP)资源大全
机械鸡
35+阅读 · 2017年9月17日
【推荐】SLAM相关资源大列表
机器学习研究会
10+阅读 · 2017年8月18日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
0+阅读 · 2021年5月28日
Arxiv
0+阅读 · 2021年5月28日
Music Generation using Three layered LSTM
Arxiv
0+阅读 · 2021年5月27日
Arxiv
0+阅读 · 2021年5月25日
Arxiv
5+阅读 · 2018年5月31日
VIP会员
相关VIP内容
专知会员服务
52+阅读 · 2020年9月7日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
【深度学习视频分析/多模态学习资源大列表】
专知会员服务
91+阅读 · 2019年10月16日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
条件GAN重大改进!cGANs with Projection Discriminator
CreateAMind
8+阅读 · 2018年2月7日
gan生成图像at 1024² 的 代码 论文
CreateAMind
4+阅读 · 2017年10月31日
自然语言处理 (NLP)资源大全
机械鸡
35+阅读 · 2017年9月17日
【推荐】SLAM相关资源大列表
机器学习研究会
10+阅读 · 2017年8月18日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
相关论文
Top
微信扫码咨询专知VIP会员