当前位置: 首页 > 知识库问答 >
问题:

求无向未加权图中给定长度的路的个数

邢华清
2023-03-14

路径的“length”是路径中的边数。

给定一个源和一个目的顶点,我想求出给定长度k的从源顶点到目的顶点的路径数。

>

  • 我们可以任意多次访问每个顶点,因此,如果从ab的路径如下:A->C->B->C->b被认为是有效的。这意味着可以有循环,我们可以通过目的地不止一次。

    由于答案可能很大,所以要以模的形式报告。

    以下是我到目前为止的想法:

    我们可以使用广度优先搜索而不将任何顶点标记为已访问的,在每次迭代中,我们跟踪该路径所需的边数'N_E',以及路径中每个边的重复边数的乘积'P'。

    所以我需要一个不同的方法来解决这个问题;任何帮助都将不胜感激。

  • 共有1个答案

    都沈浪
    2023-03-14

    所以,这里有一个漂亮的图论技巧,我记得这一个。

    使邻接矩阵成为。其中,如果ij之间存在边,a[i][j]为1,否则为0。

    那么,在ij之间长度k的路径数就是a^k的[i][j]项。

     类似资料:
    • 我知道Bellman Ford算法使用负权值,但我希望我可以修改我现有的最短路径方法。

    • 我遇到了一个问题,我必须找出给定图形中的最长路径。我有一个边列表(例如,{AB,BC}),它表明在顶点/节点(A,B,C)之间有一条边。现在我想计算出可能的最长路径(不重复顶点),这样它可以覆盖从任何顶点/节点开始的最大节点。 解决这个问题的最佳方法是什么?我必须把它作为一个计划来实施。 我在谷歌上查找最小生成树、Dijkstra的算法等等。但我想不出什么最适合解决这个问题。 任何帮助或阅读参考资

    • 我需要找到图中最长的路径基于边权值。对于图像上的图,它应该是4,5,3,2,1(顺序无关紧要),最好的算法是什么?如果您知道,在您的图中,每个节点都有一个对图中任何其他节点的引用(边)。算法应该改变吗?

    • 我能够使用这个算法在一个加权DAG中找到最长的路径(使用拓扑排序,然后放松每个边)。我现在的问题是,是否有一个算法来找到DAG的前3个最长的路径?或者,有没有实现这种算法的javascript或java库?

    • 我试图将这个问题概念化,然后为它编写Java代码。我知道这里有一些讨论,但我没有看到很多回答者,所以我想通过写下我的想法来重申这个问题,我希望从你们那里得到一些反馈。谢谢 我的想法:对于每个叶节点,找到从根节点到它的最长路径。对于所有路径,找到最大路径长度 然而,这不就是蛮力吗,对此还有更优雅的解决方案吗? 我听说过使用Djikstra的负权重算法,但在某些地方它说这只适用于特定情况?我也看到了关

    • 给定一个无权无向图的邻接矩阵,是否有一种有效的方法(多项式算法)来扩展或增加任意给定的两个结点s和T之间的最短路径长度? 示例: 在下面的例子中,从顶点S=1到顶点T=5有5条不同的“最短路径”,每个路径的长度为3。我想去除最少的边数,这样最短的路径长度被迫变成4或更多。(断开图形连接是可以的。) 表示此图形: 强制最短路径长度从3增加到4的最小代价是去除两条边(1,2)和(5,9) 目标: