Skip to content
Create a gist now

Instantly share code, notes, and snippets.


My submission for Ruby Challenge #3: Short Circuit


  • 100% RSpec test coverage

  • Works in both Ruby 1.8 and 1.9


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.


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 #
# 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
# 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)
# 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 ={ | edge | edge[NODES].include?(start_node) }
remaining_edges = graph - adjacent_edges
shortest_path =
adjacent_edges.each do | edge |
path = [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)
shortest_path = path if path.distance < shortest_path.distance
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]
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]
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)
# 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
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)
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)
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)
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)
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.