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

Question

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

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

我的解决方案:

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

---

算法工作正常，但悬停速度非常慢，我尝试了一种解决方案来改进它，但它只会进一步减慢算法的速度:

1. 在对 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。由于边成本为 1，它将在 O(V+E) 时间内为您提供从顶点 u 到所有其他顶点的最短路径。现在，取所有顶点 v 距 u 的 [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