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)

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

最简单的修复方法是简单地删除此块，然后...就是这样。

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

Ocaml：使用 bfs 的最长路径

Ocaml: Longest path using bfs

ocaml

graph

path

breadth-first-search

weighted