我使用矩阵d
来呈现图表。表示和d.(i).(j)
之间的距离;表示图中的节点数。i
j
v
该图中可能存在负循环。
我想检查是否存在负循环。我从Floyd-Warshall的变体中写了如下内容:
let dr = Matrix.copy d in
(* part 1 *)
for i = 0 to v - 1 do
dr.(i).(i) <- 0
done;
(* part 2 *)
try
for k = 0 to v - 1 do
for i = 0 to v - 1 do
for j = 0 to v - 1 do
let improvement = dr.(i).(k) + dr.(k).(j) in
if improvement < dr.(i).(j) then (
if (i <> j) then
dr.(i).(j) <- improvement
else if improvement < 0 then
raise BreakLoop )
done
done
done;
false
with
BreakLoop -> true
我的问题是
- 上面的代码正确吗?
part 1
有用吗?
因为我经常调用这个函数,所以我真的想让它尽可能快。所以我的 3) 问题是其他算法(尤其是Bellman-Ford
)是否可以比这更快?