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];;
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.