Ocaml：使用bfs的最长路径

Question

问题如下：给定定向加权图，起始节点，终止节点和数字k，请验证从起始节点到终止节点的路径是否存在长度至少为k的路径。这是我编写的代码，它是正确的，但仅在特定图中显示。例如，g1和weights1如下：

let weights1 = [(2,1,1);(2,1,3);(2,1,4);(1,1,5);(5,1,2);(5,1,6);(3,1,6);(6,1,7);(4,1,3)];;

let f1 = function
1 -> [5]
| 2 -> [1;3;4]
| 3 -> [6]
| 4 -> [3]
| 5 -> [2;6]
| 6 -> [7]
| _ -> [];;

type 'a graph = Graph of ('a -> 'a list);;
let g1 = Graph f1;;

let weights2 = [(1,3,2);(1,9,5);(2,2,3);(5,4,6);(3,1,6);(3,7,4);(6,2,7);(4,4,6);(6,1,2)];;

let f2 = function
1 -> [2;5]
| 2 -> [3]
| 3 -> [4;6]
| 4 -> [6]
| 5 -> [6]
| 6 -> [2;7]
| _ -> [];;

let g2 = Graph f2;; 


exception NotFound;;
exception Errore;;


(* Function that return the weight of an edge given 2 nodes*)
let rec get_k x y = function
    [] -> 0
    |(a,b,c)::rest -> if((a=x && c=y))then b else get_k x y rest;;


(* Function that calculate the total cost of a given path*)
let cost_of_path path weight = 
    let rec sum cost = function
        []->raise Errore
        |x::y::rest -> sum (cost + get_k x y weight) (y::rest)
        |_::[]->cost 
in sum 0 path;;

(*this function print the list of the path*)
let rec printList = function [] -> print_newline()
    | x::rest -> print_int(x); print_string("; "); printList rest;;

(* Simple bfs function, return only 1 path that connect the start node to the final node*)
let bfs start last_node (Graph succ) =
    let extends path = printList path;
        List.map (function x -> x::path) (List.filter (function x -> not (List.mem x path)) (succ (List.hd path)))
        in let rec aux last_node = function
            [] -> raise Not_found 
            | path::rest -> 
                if (last_node = List.hd path) then List.rev path
                else aux last_node (rest @ (extends path))                     
in aux last_node [[start]];; 


let loghest_path start final_node k weight (Graph succ)=
    let extends path = printList path;
        List.map (function x -> x::path)(succ (List.hd path))    
        in let rec aux final_node = function
            [] -> raise NotFound 
            | path::rest -> 
                (*if the cost of this path is >= k and the last node is the final node, return that path.*)
                if ((cost_of_path (List.rev path) weight >= k) && (List.hd path == final_node)) then List.rev path 

                (*HERE IS THE ERROR: if the total weight of the singole path is >= k but the last node is not the final node,
                find a path that connect the last node of this path to the final node using bfs. It can happen that the path exists
                but it return "Not_Found".*)
                else if((cost_of_path (List.rev path) weight) >= k)
                then (List.rev (List.tl path)) @ bfs (List.hd path) (final_node) (Graph succ)

                (* If the weight is not yet k than extend the path and try another one in list 'rest' *)
                else aux final_node (rest @ (extends path))
in aux final_node [[start]];;


(*Function that calls the other function 'loghest_path' and print the result *)
let find_path start final_node k weigths (Graph succ)=
    let result = (loghest_path start final_node k weigths (Graph succ)) in 
    print_string("Final Path:"); printList result ;
    print_string("The weight is:"); print_int (cost_of_path result weigths); print_newline();;

并且使用weights1和g1执行我的代码是：

现在，如果我在另一张图中执行我的代码，例如：

let weights3 =[(1,1,2);(1,1,3);(1,1,4);(2,1,5);(2,1,6);(3,1,7);(3,1,8);(4,1,9);(4,1,10);(10,1,1)];;
let f3 = function
1 -> [2;3;4]
| 2 -> [5;6]
| 3 -> [7;8]
| 4 -> [9;10]
| 10 -> [1]
| _ -> [];;
let g3 = Graph f3;;

通过以下执行，我的代码失败：

这是因为在找到至少为k的路径之前的最后一条路径以节点2开头，并且不存在可以将2与10相连的路径，但是存在权重为10的1和10之间的路径，并且没有选择。有人可以向我解释如何更改代码以确保在每种类型的图中都能解决问题吗？

Answer 1

正如您自己说的，街区

    else if((cost_of_path (List.rev path) weight) >= k)
    then (List.rev (List.tl path)) @ bfs (List.hd path) (final_node) (Graph succ)

可能会失败，因为无法确保存在从当前路径的最后一个元素到最终节点的路径。

最简单的解决方法是简单地删除此块，然后就是它。

[当一条局部路径大于长度阈值时，并没有迫切需要切换算法（并且这不是尝试优化的正确算法）。