Add benchmark for dijkstra algo
diff --git a/benches/dijkstra.rs b/benches/dijkstra.rs
new file mode 100644
index 0000000..0d53ced
--- /dev/null
+++ b/benches/dijkstra.rs
@@ -0,0 +1,33 @@
+#![feature(test)]
+
+extern crate petgraph;
+extern crate test;
+
+use petgraph::prelude::*;
+use std::cmp::{ max, min };
+use test::Bencher;
+
+use petgraph::algo::dijkstra;
+
+#[bench]
+fn dijkstra_bench(bench: &mut Bencher) {
+ static NODE_COUNT: usize = 10_000;
+ let mut g = Graph::new_undirected();
+ let nodes: Vec<NodeIndex<_>> = (0..NODE_COUNT).into_iter().map(|i| g.add_node(i)).collect();
+ for i in 0..NODE_COUNT {
+ let n1 = nodes[i];
+ let neighbour_count = i % 8 + 3;
+ let j_from = max(0, i as i32 - neighbour_count as i32 / 2) as usize;
+ let j_to = min(NODE_COUNT, j_from + neighbour_count);
+ for j in j_from..j_to {
+ let n2 = nodes[j];
+ let distance = (i + 3) % 10;
+ g.add_edge(n1, n2, distance);
+ }
+ }
+
+ bench.iter(|| {
+ let _scores = dijkstra(&g, nodes[0], None, |e| *e.weight());
+ });
+}
+
