Longhest path algorithm

147 views Asked by At

On OCaml, using the BFS, I have to make an algorithm that solve the Longhest Path Problem:

On an oriented weighted graph, I have a start node, a stop node and an integer K as input. I have to say if exist a path between start node and stop node with cost at least K. The cost is the sum of the edges weights.

Now, I'm not pretending the code but I can't find a good algorithm to implement this; with using the DFS, it would be easier but the BFS add nodes that are NOT on the same path.

That's the BFS code I'm using:

    let breadth_first_collect graph start =
        let rec search visited = function
             [] -> visited
             | n::rest -> if List.mem n visited
                then search visited rest
                else search (n::visited) (rest @ (succ graph n))
                (* new nodes are put into queue *)
in search [] [start];; 
1

There are 1 answers

0
Mr. Perfectionist On

Actually your question isn't clear. But I'm trying to help you whatever I had understood. You can try by the farthest node problem. You can measure all the distance from a node then you can maximize it.

bfs(first_node);
int max=dis[first_node];

for(int i=0; i<node; i++)
{
       if(dis[first_node]<dis[i])
       {
           max=dis[i];
           first_node=i;
       }
}