Instantly share code, notes, and snippets.

# rpcfn-3-shortest_path

My submission for Ruby Challenge #3: Short Circuit

## Features

• 100% RSpec test coverage

• Works in both Ruby 1.8 and 1.9

## Explanation

I decided to play with a couple different concepts in this submission:

• Rather than using a known shortest path algorithm such as Dijkstra’s, I wanted to write my own from scratch with the goal of it being simple (even if it meant being computationally expensive).

• I wanted to make the algorithm recursive because I so rarely use recursion when building websites (my day job).

• I wanted to use Ruby's infinity to represent the distance of an empty/dead-end path. It had a nice side effect of allowing me to remove all nil checks from the code.

## Usage

```require 'shortest_path'
include ShortestPath
shortest_path('A', 'B', [['A', 'B', 40], ['A', 'B', 50]]) => [['A', 'B', 40]]
unused_paths('A', 'B', [['A', 'B', 40], ['A', 'B', 50]]) => [['A', 'B', 50]]```
 module ShortestPath NODES = 0..1 # Nodes are in positions 0 and 1 ['A', 'B', 20] LENGTH = 2 # Length is in position 2 INFINITY = 1.0/0 # http://weblog.jamisbuck.org/2007/2/7/infinity # Adds distance method to compute the distance of the current path class Path < Array def distance (any?)? inject(0) { | sum, edge | sum += edge[LENGTH] } : INFINITY end end # Returns the unused edges between start_node and end_node # unused_paths('A', 'B', [['A', 'B', 40], ['A', 'B', 50]]) => ['A', 'B', 50] def unused_paths(start_node, end_node, graph) graph - shortest_path(start_node, end_node, graph) end # Returns the shortest path between start_node and end_node # shortest_path('A', 'B', [['A', 'B', 40], ['A', 'B', 50]]) => ['A', 'B', 40] def shortest_path(start_node, end_node, graph) adjacent_edges = graph.select{ | edge | edge[NODES].include?(start_node) } remaining_edges = graph - adjacent_edges shortest_path = Path.new adjacent_edges.each do | edge | path = Path.new [edge] neighbor_node = (edge[NODES] - [start_node])[0] # ['A', 'B'] - ['A'] => ['B'] unless neighbor_node == end_node path_ahead = shortest_path(neighbor_node, end_node, remaining_edges) (path_ahead.empty?)? path.clear : path.concat(path_ahead) end shortest_path = path if path.distance < shortest_path.distance end shortest_path end end
 require File.dirname(__FILE__) + '/spec_helper.rb' describe ShortestPath do include ShortestPath describe "when testing with the RPCFN 3 example graph" do before(:each) do @rpcfn_graph = [ ['A', 'B', 50], ['A', 'D', 150], ['B', 'C', 250], ['B', 'E', 250], ['C', 'E', 350], ['C', 'D', 50], ['C', 'F', 100], ['D', 'F', 400], ['E', 'G', 200], ['F', 'G', 100] ] end it "should find the unused paths" do unused_paths('A', 'G', @rpcfn_graph).should eql([ ["A", "B", 50], ["B", "C", 250], ["B", "E", 250], ["C", "E", 350], ["D", "F", 400], ["E", "G", 200] ]) end it "should find the shortest path" do path = shortest_path('A', 'G', @rpcfn_graph) path.should eql([["A", "D", 150], ["C", "D", 50], ["C", "F", 100], ["F", "G", 100]]) path.distance.should eql(400) end end # This is where my TDD process started, trying to solve the simplest case and building on it it "should return an empty path if we can't complete the path" do shortest_path('A', 'X', [[ 'A', 'B', 50]]).empty?.should be_true end it "should find the shortest path with only 2 nodes and 1 edge" do graph = [[ 'A', 'B', 50]] shortest_path('A', 'B', graph).should eql(graph) end it "should find the shortest path with multiple legs strung together" do graph = [[ 'A', 'B', 50], ['B', 'C', 50], ['C', 'D', 50]] path = shortest_path('A', 'D', graph) path.should eql(graph) path.distance.should eql(150) end it "should find the shortest path with 2 nodes and 2 edges" do short = [['A', 'B', 40]] long = [['A', 'B', 50]] path = shortest_path('A', 'B', short + long) path.should eql(short) path.distance.should eql(40) end it "should choose a shortest path when 2 paths are equal" do path_a = [['A', 'B', 10], ['B', 'D', 20]] path_b = [['A', 'C', 20], ['C', 'D', 10]] path = shortest_path('A', 'D', path_a + path_b) path.should eql(path_a) path.distance.should eql(30) end it "should find the shortest path with multiple legs, multiple routes, and a dead end" do short = [['A', 'D', 20], ['D', 'E', 5]] # 25 long = [[ 'A', 'B', 10], ['B', 'C', 10], ['B', 'Z', 1], ['C', 'E', 10]] # 30 path = shortest_path('A', 'E', short + long) path.should eql(short) path.distance.should eql(25) end end