RPCFN: Shortest Path (#3)
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
lib
spec
LICENSE
README.rdoc

README.rdoc

rpcfn-3-shortest_path

My submission for Ruby Challenge #3: Short Circuit

rubylearning.com/blog/2009/10/30/rpcfn-short-circuit-3/

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]]