通过特定顶点的有向图中最轻量级的圆
most lightweight circle in directed graph that goes through specific vertex
我用权重函数 w 指导了图 G(V,E)。因此每个 (u,v) 的权重都是正值。我需要在图中找到顶点 k' 是其中一部分的最轻的圆。
我还给出了一个我可以使用的算法，它可以为具有正权重的图找到最轻量级的路径（我只能使用一次）。
我想创建一个子图 G'，其中所有顶点和边都是强连通分量。找到 k' 是其中一部分的图。然后找到从 k' 到顶点 v 的最轻量级相邻边。从那个 v 我可以 运行 给定的算法并找到轻量级路径然后添加顶点缺失的权重（ (k',v) ）。
这看起来正确吗？我在这门课程的开头，我觉得我还没有到那儿。
这是一个单源最短路径问题，您排除 k->k 自循环作为解决方案，并找到从 k 到 k 的更长路径。诀窍总是扩展最短路径线程。
鉴于此定义，您可以开始谷歌搜索...
我无法想象你为什么将源顶点命名为 k'。无论如何...
添加一个新的 vetrex w 具有与 k'.
相同的出边
然后用Dijkstra算法求出从w到k'.
的最短路径
用k'代替路径中的w，得到最小的循环包括k'.
非常有趣的问题。我假设图中没有负值，否则以下解决方案需要首先对顶点进行归一化，使负值至少变为 0。第一种方法（平凡的）是检测从目标顶点开始的所有循环（k ).然后计算所有这些循环的权重并取最小值。第二种方法是从目标节点 (k) 开始 运行 Dijkstra 算法（再次注意负权重）。然后遍历 (k) 的所有传入边，select 具有最小 Dijkstra 值的源节点。现在最轻的循环包括从 (k) 到所选节点的单一路径（由 Dijkstra 遍历形成）+ 返回到 (k) 的桥。希望对您有所帮助:)
我用权重函数 w 指导了图 G(V,E)。因此每个 (u,v) 的权重都是正值。我需要在图中找到顶点 k' 是其中一部分的最轻的圆。
我还给出了一个我可以使用的算法，它可以为具有正权重的图找到最轻量级的路径（我只能使用一次）。
我想创建一个子图 G'，其中所有顶点和边都是强连通分量。找到 k' 是其中一部分的图。然后找到从 k' 到顶点 v 的最轻量级相邻边。从那个 v 我可以 运行 给定的算法并找到轻量级路径然后添加顶点缺失的权重（ (k',v) ）。
这看起来正确吗？我在这门课程的开头，我觉得我还没有到那儿。
这是一个单源最短路径问题，您排除 k->k 自循环作为解决方案，并找到从 k 到 k 的更长路径。诀窍总是扩展最短路径线程。
鉴于此定义，您可以开始谷歌搜索...
我无法想象你为什么将源顶点命名为 k'。无论如何...
添加一个新的 vetrex w 具有与 k'.
相同的出边然后用Dijkstra算法求出从w到k'.
的最短路径用k'代替路径中的w，得到最小的循环包括k'.
非常有趣的问题。我假设图中没有负值，否则以下解决方案需要首先对顶点进行归一化，使负值至少变为 0。第一种方法（平凡的）是检测从目标顶点开始的所有循环（k ).然后计算所有这些循环的权重并取最小值。第二种方法是从目标节点 (k) 开始 运行 Dijkstra 算法（再次注意负权重）。然后遍历 (k) 的所有传入边，select 具有最小 Dijkstra 值的源节点。现在最轻的循环包括从 (k) 到所选节点的单一路径（由 Dijkstra 遍历形成）+ 返回到 (k) 的桥。希望对您有所帮助:)