问题：
如何在python中生成两节点间长最短路径的有向无环图
养慈
你知道如何克服这个问题吗？
共有1个答案
龙嘉玉
让你的图是一个路径和一个“半完全图”的并集。“half complete graph”（抱歉，这个名字很傻）是一个图，在这个图中，您将每个节点连接到所有其他具有更高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
类似资料：
-
我需要帮助在一个未加权无向图中找到两个节点之间的所有最短路径。 我能够使用BFS找到一条最短路径，但到目前为止，我还不知道如何找到并打印出所有路径。 知道我可以使用的算法/伪代码吗？
-
我正在寻找最有效的算法，根据大O符号，在未加权有向图中找到两个节点之间的最短路径。 我主要分为带堆的Dijkstra和呼吸优先搜索，如果图加权，我通常会使用堆。 在这种情况下，未加权的图是否会使Dijkstra的使用效率低于BFS？
-
我有一个有向加权图
-
我有一个一般性的问题，关于如何在边没有权的无向图中找到最短路径和最长路径。 我们需要使用DFS算法来寻找图中的最长路径，而我们需要使用BFS算法来寻找图中的最短路径，这是一个正确的结论吗？
-
给出了一个有向无环图G=(V，E)，如果需要，可以假定它是拓扑有序的。G中的边有两种类型的成本--名义成本w(e)和尖峰成本p(e)。 目标是找到从节点s到节点t的最短路径，使以下代价最小:sum_e(w(e))+max_e(p(e))，其中和和最大值在路径的所有边上取值。 标准动态规划方法表明，该问题在O(e^2)时间内是可解的。有没有更高效的办法解决？理想情况下，一个O(E*polylog(E