CODEWITHSUNDEEP
algorithmscalagraph-algorithm
majesiu
majesiu

Reputation: 98

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

Graph

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:

  1. Iterate over every node and find it path cost to next node, the biggest of those values is our result It's achieved using findRoad that searches recursively level by level to find connection.
  2. Acc keeps value of current iteration that equals to longest path that this vertex have to travel
  3. If acc is greater than previously finded value (min) we stop iterating this node, because this node won't give us better result
  4. Algorithm end after iteration on last node is finished

Algorithm works correctly hovever very slow, I tried one solutions to improve it, but it only slowed the algorithm further down:

  1. in recursive call to findRoad replacing first parameter that is always a full list of edges to filtered list (without already checked ones)

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

Answers (2)

xashru
xashru

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

Badf
Badf

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

Related Questions