Expand description
可检测负环的SP(最短路径)算法
§使用
use algorithms_fourth::{digraph::{edge_weighted::EdgeWeigtedDigraph, bellman_for_sp::BellmanFordSP}, add_edge_weighted_for_digraph};
let mut g = EdgeWeigtedDigraph::new(8);
add_edge_weighted_for_digraph!(g,4,5,0.35);
add_edge_weighted_for_digraph!(g,5,4,0.35);
add_edge_weighted_for_digraph!(g,4,7,0.37);
add_edge_weighted_for_digraph!(g,5,7,0.28);
add_edge_weighted_for_digraph!(g,7,5,0.28);
add_edge_weighted_for_digraph!(g,5,1,0.32);
add_edge_weighted_for_digraph!(g,0,4,0.38);
add_edge_weighted_for_digraph!(g,0,2,0.26);
add_edge_weighted_for_digraph!(g,7,3,0.39);
add_edge_weighted_for_digraph!(g,1,3,0.29);
add_edge_weighted_for_digraph!(g,2,7,0.34);
add_edge_weighted_for_digraph!(g,6,2,-1.20);
add_edge_weighted_for_digraph!(g,3,6,0.52);
add_edge_weighted_for_digraph!(g,6,0,-1.40);
add_edge_weighted_for_digraph!(g,6,4,-1.25);
let sp = BellmanFordSP::new(&g, 0);
assert!(!sp.has_negative_cycle());
assert!(sp.has_path_to(4));
assert_eq!(sp.dist_to(4) as f32,0.26);
for e in sp.path_to(4).unwrap(){
println!("{:?}",e) ;
}
let mut g = EdgeWeigtedDigraph::new(8);
add_edge_weighted_for_digraph!(g,4,5,0.35);
add_edge_weighted_for_digraph!(g,5,4,-0.66);
add_edge_weighted_for_digraph!(g,4,7,0.37);
add_edge_weighted_for_digraph!(g,5,7,0.28);
add_edge_weighted_for_digraph!(g,7,5,0.28);
add_edge_weighted_for_digraph!(g,5,1,0.32);
add_edge_weighted_for_digraph!(g,0,4,0.38);
add_edge_weighted_for_digraph!(g,0,2,0.26);
add_edge_weighted_for_digraph!(g,7,3,0.39);
add_edge_weighted_for_digraph!(g,1,3,0.29);
add_edge_weighted_for_digraph!(g,2,7,0.34);
add_edge_weighted_for_digraph!(g,6,2,0.40);
add_edge_weighted_for_digraph!(g,3,6,0.52);
add_edge_weighted_for_digraph!(g,6,0,0.58);
add_edge_weighted_for_digraph!(g,6,4,0.93);
let sp = BellmanFordSP::new(&g,0);
assert!(sp.has_negative_cycle());
for e in sp.negative_cycle().as_ref().unwrap(){
println!("{:?}",e);
}