Reputation: 98
The problem is to find minimal value (weight of every edge is equal to 1) of path to every other node having free choice of starting node in undirected graph. Data is in form of adjacency relations. Nodes are numerated from 0 to max.
So in graph above correct solution is 3, because the longest path to every other node in this case is 3 as we choose node number 2 or 4.
My solution:
Algorithm works correctly hovever very slow, I tried one solutions to improve it, but it only slowed the algorithm further down:
Code:
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
})
}
Is whole idea flawed or some scala operations should be avoided (like filter, collect, transforming sets into collections)?
Maybe I should use some All-pairs shortest paths algorithm like Floyd–Warshall algorithm?
Upvotes: 2
Views: 728
Reputation: 3600
Use BFS
. Since edge cost is 1
it will give you shortest paths from vertex u
to all other vertices in O(V+E)
time. Now take maximum of those [u,v]
distances for all vertex v
from u
. Lets call this d
. Finally you need the vertex that gives minimum value of d
. Overall running time is O((V+E)*V)
.
Algorithm:
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
Upvotes: 1
Reputation: 345
I think you can just run BFS from every vertex, and for each vertex remember the length of longest path traveled using BFS. Your result is the minimum value among those. It would be O(n²).
You can also find shortest paths for each pair of vertices using Floyd–Warshall algorithm and then for each vertex v find vertex u so that dist[v][u] is maximum. Among all those values for each vertex the minimal one is your answer. It would be O(n³) because of Floyd-Warshall.
n - number of vertices
Upvotes: 1