1 use petgraph::algo::k_shortest_path;
2 use petgraph::prelude::*;
3 use petgraph::Graph;
4 use std::collections::HashMap;
5 
6 #[test]
second_shortest_path()7 fn second_shortest_path() {
8     let mut graph: Graph<(), (), Directed> = Graph::new();
9     let a = graph.add_node(());
10     let b = graph.add_node(());
11     let c = graph.add_node(());
12     let d = graph.add_node(());
13     let e = graph.add_node(());
14     let f = graph.add_node(());
15     let g = graph.add_node(());
16     let h = graph.add_node(());
17     let i = graph.add_node(());
18     let j = graph.add_node(());
19     let k = graph.add_node(());
20     let l = graph.add_node(());
21     let m = graph.add_node(());
22 
23     graph.extend_with_edges(&[
24         (a, b),
25         (b, c),
26         (c, d),
27         (b, f),
28         (f, g),
29         (c, g),
30         (g, h),
31         (d, e),
32         (e, h),
33         (h, i),
34         (h, j),
35         (h, k),
36         (h, l),
37         (i, m),
38         (l, k),
39         (j, k),
40         (j, m),
41         (k, m),
42         (l, m),
43         (m, e),
44     ]);
45 
46     let res = k_shortest_path(&graph, a, None, 2, |_| 1);
47 
48     let expected_res: HashMap<NodeIndex, usize> = [
49         (e, 7),
50         (g, 3),
51         (h, 4),
52         (i, 5),
53         (j, 5),
54         (k, 5),
55         (l, 5),
56         (m, 6),
57     ]
58     .iter()
59     .cloned()
60     .collect();
61 
62     assert_eq!(res, expected_res);
63 }
64