Skip to main content
 首页 » 编程设计

python之如何在python中生成具有两个节点之间的长最短路径的有向无环图

2025年05月04日17落叶无声

我想根据在有向无环图 (DAG) 中找到两个节点之间的最短路径所需的时间来比较几种路由算法。

我为算法编写了代码,但我在生成 DAG 时遇到问题,因为要找到最短路径在计算上很复杂。例如,当我按照 this 生成 100 节点 DAG 时方法,该图非常连接,对于源节点和目标节点的任意组合,我在“最佳”情况下获得了三跳长路由。

知道如何解决这个问题吗?

请您参考如下方法:

让您的图成为路径和“半完整图”的联合。 “半完整图”(抱歉这个名字很傻)是一个图,您可以在其中将每个节点连接到具有更高 ID 的所有其他节点(例如 1 -> 2, 1 -> 3, 2 -> 3)。这保证了大量的边(由于“半完整图”)和由于路径的最短路径。您可以将路径中的一些节点连接到“半完整图中的节点”。

示例

具有 14 个节点的图:

1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10 
11 - 12 
11 - 13 
11 - 14 
12 - 13 
12 - 14 
13 - 14 
2 - 13 
4 - 14 
You can continue adding edges from nodes 1-9 to nodes 11-14 

找到 1 到 10 之间的路径。