最小生成树和最短路径
给了我一个问题，上面写着：
给定一个具有整数权值（正负两种）的连通有向图，发展一种求两顶点之间最短路径的算法。
我想我可以使用最小生成树算法，比如Kruskal的算法，然后用Dijkstra的算法来证明，因为在MST中，每个顶点只有一条内边，Dijkstra的算法即使在负权值下也能工作。
这听起来像是共食吗？
附注。我很难证明MST包含有向图的每个顶点的最短路径。
共有1个答案
首先，你应该注意你的图不应该有任何负循环。
其次，通常Dikstra不会处理负权值的图。
Tirst,Bellman-Ford算法可用于求有向负权图的最短路径。
-
在一个具有不同正边的无向图中，是否可能有一个MST与最短路径树没有公共边？ 我一直试图引出不同的例子，但似乎这是不可能的。最短路径树中的最短路径边似乎也应该包括在MST中。
-
(b)假设图的最小生成树是唯一的。无向图的最小生成树中一对顶点之间的路径一定是最短（最小权）路径吗？ 我的回答是 (a)
-
主要内容：生成树,最小生成树数据结构提供了 3 种存储结构，分别称为线性表、树和图，如图 1 所示。 图 1 3 种存储结构 a) 是线性表，b) 是树，c) 是图。 在图存储结构中，a、b、c 等称为顶点，连接顶点的线称为边。 线性表是最简单的存储结构，很容易分辨。树和图有很多相似之处，它们的区别是：树存储结构中不允许存在环路，而图存储结构中可以存在环路（例如图 1 c) 中，c-b-f-c、b-a-f-b 等都是环路）。
-
对于最小生成树问题的求解，geotools graph包中是否有Prim的算法或任何其他算法的实现？
-
假设我选择V(H)={a,e,f}和e(H)={ae,af,fe} 现在，对于每条边e∈e(H)，我们用e'记下了（来自原始图G的） 达到这个最小值的边。所以E'={bc,df,eg},因为bc=4,df=9,eg=8,是连接我的元件的最小边。我在H中有一个相对于代价函数C′的最小生成树，而a′是这棵树的边集。 但是我的A'的边和E'的没有一条是一样的。
-
这个问题是NetworkX特有的。我可以创建自己的函数来完成所有我需要的事情，但是这需要更长的时间，所以我想避免它。 情况： 我有一个未加权图，由NetworkX无向图表示。从这个图中，我寻找“最短循环”——也就是说，对于给定的节点k，我正在寻找最短的简单路径（只通过一个节点一次），它离开k，然后返回k。 为了实现这一点，我想使用任何NetworkX最短路径算法，并从节点k到节点k进行搜索。问题是