我用权重函数 w 指示了图 G(V,E)。因此每个 (u,v) 的权重都是正值。我需要在图中找到顶点 k' 是其中一部分的最轻量级的圆。
我还给出了一种我可以使用的算法，它可以为具有正权重的图找到最轻量级的路径（我只能使用一次）。
我考虑过创建一个子图 G'，其中所有顶点和边都是强连通分量。找出其中 k' 是其中一部分的图。然后找到从 k' 到某些 v 个顶点的最轻量级的相邻边。从那个 vi 可以运行给定的算法并找到轻量级路径，然后添加丢失的顶点的权重（ (k',v) ）。
这似乎正确吗？我在这门课程的开始，我觉得我还没有到那里。
这是一个单源最短路径问题，您排除k->k自环作为解决方案，并找到从 k 到 k 的更长路径。诀窍始终是扩展最短路径线程。
鉴于此定义，您可以开始谷歌搜索......
我无法想象你为什么叫你的源顶点k'。反正...
添加一个与k'具有相同输出边的新 vetrex w。
然后使用 Dijkstra 算法找到从w到k'的最短路径。
将路径中的w替换为k' ，您将拥有包括k'在内的最小循环。
非常有趣的问题。我假设图中没有负值，否则以下解决方案需要首先对顶点进行归一化，使负值至少变为 0。第一种方法（简单）是检测从目标顶点开始的所有循环（k ）。然后计算所有这些循环的权重并取最小值。第二种方法是从目标节点 (k) 运行 Dijkstra 算法（再次注意负权重）。然后遍历 (k) 的所有传入边，并选择具有最小 Dijkstra 值的源节点。现在最轻的循环包括从 (k) 到所选节点的单条路径（由 Dijkstra 遍历形成）+ 返回到 (k) 的桥。我希望这会有所帮助:)