我已经用权重函数 w 指示了图 G(V,E)。因此每个 (u,v) 的权重都是正值。我需要在图中找到顶点 k' 是其中一部分的最轻的圆。
我还给出了一个我可以使用的算法，它可以为具有正权重的图找到最轻量级的路径(我只能使用一次)。
我想创建一个子图 G'，其中所有顶点和边都是强连通分量。找到 k' 是其中一部分的图。然后找到从 k' 到顶点 v 的最轻量级相邻边。从那个 v 我可以运行给定的算法并找到轻量级路径然后添加顶点缺失的权重 ((k',v))。
这看起来正确吗？我刚开始学习这门类(class)，但我觉得我还没有到那一步。
最佳答案
这是一个单源最短路径问题，您排除 k->k 自循环作为解决方案，并找到从 k 到 k 的更长路径。诀窍总是扩展最短路径线程。
根据这个定义，您可以开始谷歌搜索...
关于algorithm - 通过特定顶点的有向图中最轻量级的圆，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/47424351/