diff --git a/rust/Cargo.lock b/rust/Cargo.lock
index 2435fd7..79bb4e2 100644
--- a/rust/Cargo.lock
+++ b/rust/Cargo.lock
@@ -2,6 +2,7 @@
 name = "advent_of_code"
 version = "0.1.0"
 dependencies = [
+ "permutohedron 0.2.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "regex 0.1.44 (registry+https://github.com/rust-lang/crates.io-index)",
  "rust-crypto 0.2.34 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
@@ -59,6 +60,11 @@ dependencies = [
  "libc 0.2.4 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
+[[package]]
+name = "permutohedron"
+version = "0.2.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
 [[package]]
 name = "rand"
 version = "0.3.12"
diff --git a/rust/Cargo.toml b/rust/Cargo.toml
index 8c4e34e..53c1691 100644
--- a/rust/Cargo.toml
+++ b/rust/Cargo.toml
@@ -6,3 +6,4 @@ authors = ["Alpha Chen <alpha.chen@gmail.com>"]
 [dependencies]
 regex = "0.1"
 rust-crypto = "^0.2"
+permutohedron = "0.2"
diff --git a/rust/input/day_09.txt b/rust/input/day_09.txt
new file mode 100644
index 0000000..df5432f
--- /dev/null
+++ b/rust/input/day_09.txt
@@ -0,0 +1,28 @@
+Faerun to Tristram = 65
+Faerun to Tambi = 129
+Faerun to Norrath = 144
+Faerun to Snowdin = 71
+Faerun to Straylight = 137
+Faerun to AlphaCentauri = 3
+Faerun to Arbre = 149
+Tristram to Tambi = 63
+Tristram to Norrath = 4
+Tristram to Snowdin = 105
+Tristram to Straylight = 125
+Tristram to AlphaCentauri = 55
+Tristram to Arbre = 14
+Tambi to Norrath = 68
+Tambi to Snowdin = 52
+Tambi to Straylight = 65
+Tambi to AlphaCentauri = 22
+Tambi to Arbre = 143
+Norrath to Snowdin = 8
+Norrath to Straylight = 23
+Norrath to AlphaCentauri = 136
+Norrath to Arbre = 115
+Snowdin to Straylight = 101
+Snowdin to AlphaCentauri = 84
+Snowdin to Arbre = 96
+Straylight to AlphaCentauri = 107
+Straylight to Arbre = 14
+AlphaCentauri to Arbre = 46
\ No newline at end of file
diff --git a/rust/src/day_09.rs b/rust/src/day_09.rs
new file mode 100644
index 0000000..fb3ffbf
--- /dev/null
+++ b/rust/src/day_09.rs
@@ -0,0 +1,112 @@
+use std::collections::{HashMap,HashSet};
+use std::hash::{Hash,Hasher};
+
+use permutohedron::Heap;
+
+#[test]
+fn test_day_09() {
+    let input = "London to Dublin = 464
+London to Belfast = 518
+Dublin to Belfast = 141";
+    let day = Day09::new(input);
+
+    assert_eq!(464,
+               day.distances[&LocationPair(Location("Dublin"),
+                                           Location("London"))]);
+    assert_eq!(464,
+               day.distances[&LocationPair(Location("London"),
+                                           Location("Dublin"))]);
+
+    let route = day.route(vec![Location("Dublin"),
+                               Location("London"),
+                               Location("Belfast")]);
+    assert_eq!(982, route.distance);
+
+    assert_eq!(6, day.routes().len());
+
+    assert_eq!(605, solve(input));
+}
+
+pub fn solve(input: &str) -> usize {
+    let day = Day09::new(input);
+    day.routes().iter().map(|r| r.distance).min().unwrap()
+}
+
+struct Day09<'a> {
+    locations: HashSet<Location<'a>>,
+    distances: HashMap<LocationPair<'a>, usize>,
+}
+
+impl<'a> Day09<'a> {
+    fn new(input: &str) -> Day09 {
+        let mut locations = HashSet::new();
+        let mut distances = HashMap::new();
+
+        for line in input.lines() {
+            let mut split_eq = line.split(" = ");
+            let mut split_to = split_eq.next().unwrap().split(" to ");
+            let a = Location(split_to.next().unwrap());
+            let b = Location(split_to.last().unwrap());
+            let distance = split_eq.last().unwrap().parse::<usize>().unwrap();
+
+            locations.insert(a);
+            locations.insert(b);
+            distances.insert(LocationPair(a, b), distance);
+        }
+
+        Day09 { locations: locations, distances: distances }
+    }
+
+    fn routes(&self) -> Vec<Route> {
+        let mut locations = self.locations.iter()
+            .map(|l| l.clone())
+            .collect::<Vec<Location>>();
+        let heap = Heap::new(&mut locations);
+        heap.map(|p| self.route(p)).collect()
+    }
+
+    fn route(&self, locations: Vec<Location<'a>>) -> Route {
+        let distance = locations.windows(2)
+                                .map(|w| self.distances[&LocationPair(w[0], w[1])])
+                                .fold(0, |sum, dist| sum + dist);
+        Route { locations: locations, distance: distance }
+    }
+}
+
+#[derive(Debug)]
+struct Route<'a> {
+    locations: Vec<Location<'a>>,
+    distance: usize,
+}
+
+#[derive(Clone,Copy,Debug,Eq,PartialEq,PartialOrd,Ord)]
+struct Location<'a>(&'a str);
+
+impl<'a> Hash for Location<'a> {
+    fn hash<H: Hasher>(&self, state: &mut H) {
+        self.0.hash(state);
+    }
+}
+
+#[derive(Debug,Eq)]
+struct LocationPair<'a>(Location<'a>, Location<'a>);
+
+impl<'a> PartialEq for LocationPair<'a> {
+    fn eq(&self, other: &LocationPair) -> bool {
+        let mut a = vec![&self.0, &self.1];
+        a.sort();
+
+        let mut b = vec![&other.0, &other.1];
+        b.sort();
+
+        a == b
+    }
+}
+
+impl<'a> Hash for LocationPair<'a> {
+    fn hash<H: Hasher>(&self, state: &mut H) {
+        let mut locations = vec![&self.0, &self.1];
+        locations.sort();
+        locations.hash(state);
+    }
+}
diff --git a/rust/src/lib.rs b/rust/src/lib.rs
index b1c89f5..e80acd3 100644
--- a/rust/src/lib.rs
+++ b/rust/src/lib.rs
@@ -1,7 +1,8 @@
-#![feature(box_syntax,slice_patterns)]
+#![feature(box_syntax, slice_patterns)]
 
 extern crate crypto;
 extern crate regex;
+extern crate permutohedron;
 
 pub mod day_01;
 pub mod day_02;
@@ -11,3 +12,4 @@ pub mod day_05;
 pub mod day_06;
 pub mod day_07;
 pub mod day_08;
+pub mod day_09;
diff --git a/rust/src/main.rs b/rust/src/main.rs
index 055df8c..d0e9c96 100644
--- a/rust/src/main.rs
+++ b/rust/src/main.rs
@@ -7,5 +7,5 @@ use advent_of_code::*;
 fn main() {
     let mut input = String::new();
     io::stdin().read_to_string(&mut input).ok();
-    println!("{}", day_08::solve(&input));
+    println!("{}", day_09::solve(&input));
 }