无向图中自由选择起始节点的最长路径的最小值

Question

问题是在无向图中找到到每个可以自由选择起始节点的其他节点的路径的最小值（每条边的权重等于1）。数据以邻接关系的形式存在。节点从 0 到 max.

所以在上图中正确的解决方案是 3，因为在这种情况下到每个其他节点的最长路径是 3，因为我们选择节点号 2 或 4。

我的解决方案：

遍历每个节点并找到它到下一个节点的路径成本，这些值中最大的就是我们的结果它是使用 findRoad 实现的，该 findRoad 逐级递归搜索以查找连接。
Acc 保持当前迭代的值等于该顶点必须经过的最长路径
如果 acc 大于先前找到的值 (min)，我们将停止迭代此节点，因为此节点不会给我们更好的结果
最后一个节点上的迭代完成后算法结束

算法运行正常但速度很慢，我尝试了一种解决方案来改进它，但它只会进一步降低算法速度：

在对 findRoad 的递归调用中，将始终是边的完整列表的第一个参数替换为过滤列表（没有已经检查过的）

代码：

val a: List[(Int,Int)] //list of all edges
val c: Set[(Int,Int)] //set of all edges
val max //maximum index of node

//main loop that manages iterations and limits their number
def loop(it: Int, it2: Int, acc: Int,min: Int): Int = {
    if(it > max) min
    else if(it2 > max) if(min<acc)loop(it+1,0,0,min)
    else loop(it+1,0,0,acc)
    else if(acc >= min) loop(it+1,0,0,min)
    else if(it == it2) loop(it,it2+1,acc,min)
    else {
        val z = findRoad(b,List(it),it2,1,min)
        if(z > acc) loop(it,it2+1,z,min)
        else loop(it,it2+1,acc,min)
    }
}
//finding shortest path from node s to node e
def findRoad(a: List[(Int,Int)], s: List[Int], e: Int, lev: Int,min: Int): Int = {
    if(lev > min) Int.MaxValue
    else if(s.exists( s => (a.exists(p => p == (s,e) || p == (e,s))))) lev
    else findRoad(a,connectEdges(s,Set()),e,lev+1,min)
}
//finding all predecessor and successors
def connectEdges(a: List[Int], acc: Set[Int]): List[Int] = {
    if(a.isEmpty) acc.toList
    else connectEdges(a.tail, acc++c.collect{
        case (b,c) if(b == a.head) => c
        case (b,c) if(c == a.head) => b
    })
}

整个想法是否存在缺陷或应避免某些 Scala 操作（如过滤、收集、将集合转换为集合）？

也许我应该使用一些全对最短路径算法，比如 Floyd–Warshall 算法？

Answer 1

我认为你可以从每个顶点运行 BFS，并且对于每个顶点，记住使用 BFS 行进的最长路径的长度。您的结果是其中的最小值。这将是 O(n²)。

您还可以使用 Floyd–Warshall 算法为每对顶点找到最短路径，然后为每个顶点 v 找到顶点 u所以 dist[v][u] 是最大的。在每个顶点的所有这些值中，最小值就是您的答案。由于 Floyd-Warshall，它将是 O(n³)。

n - 顶点数

Answer 2

使用BFS。由于边成本是 1，它将在 O(V+E) 时间内为您提供从顶点 u 到所有其他顶点的最短路径。现在从 u 中取所有顶点 v 的 [u,v] 距离的最大值。让我们称之为 d。最后，您需要给出最小值 d 的顶点。总体运行时间是 O((V+E)*V).

算法：

min = infinity
result = -1 // which vertex yields minimum result
for all vertices u in V:
    dist = [|V|]  // array of size |V| initialized to 0 
    fill dist using BFS starting from u
    max = max(dist)
    if max < min:
        min = max
        result = u
return result

无向图中自由选择起始节点的最长路径的最小值

Minimal value of longest path with free choice of starting node in undirected graph

algorithm

scala

graph-algorithm