1require "spec_helper"
 2require "ostruct"
 3
 4def dijkstra(graph, source, destination)
 5  heap = Heap.new
 6  heap.push(0, source)
 7  total_cost = 0
 8  until (heap.empty?) do
 9    top = heap.min
10    distance = graph.distance_between(source, top) || 0
11    total_cost += distance
12    p "#{source.name} -> #{top.name} (#{distance})"
13    return total_cost if top == destination
14    neighbors = graph.neighbors(top)
15    neighbors.each do |x|
16      heap.push(graph.distance_between(source, x) || 100, x)
17    end
18    source = top
19  end
20end
21
22describe "dijkstra" do
23  let(:a) { node(:name => "A") }
24  let(:b) { node(:name => "B") }
25  let(:c) { node(:name => "C") }
26  let(:d) { node(:name => "D") }
27  let(:e) { node(:name => "E") }
28  let(:graph) { Graph.new }
29
30  before :each do
31    graph.push(a)
32    graph.push(b)
33    graph.push(c)
34    graph.push(d)
35    graph.push(e)
36    graph.connect(a, b, 5)
37    graph.connect(a, d, 5)
38    graph.connect(a, e, 7)
39    graph.connect(b, c, 4)
40    graph.connect(c, d, 8)
41    graph.connect(c, e, 2)
42    graph.connect(d, c, 8)
43    graph.connect(d, e, 6)
44    graph.connect(e, b, 3)
45  end
46
47  it "A-B-C equals 9" do
48    expect(dijkstra(graph, a, c)).to eql(9)
49  end
50
51  it "A-D equals 5" do
52    expect(dijkstra(graph, a, d)).to eql(5)
53  end
54
55  def node(details)
56    OpenStruct.new(details)
57  end
58end
59
60class Edge
61  attr_reader :source, :destination, :distance
62
63  def initialize(source, destination, distance)
64    @source = source
65    @destination = destination
66    @distance = distance
67  end
68end
69
70class Graph < Array
71  attr_reader :edges
72
73  def initialize(edges = [])
74    @edges = []
75  end
76
77  def connect(source, destination, distance)
78    @edges.push(Edge.new(source, destination, distance))
79  end
80
81  def neighbors(vertex)
82    neighbors = []
83    @edges.each do |edge|
84      if edge.source == vertex
85        neighbors.push(edge.destination)
86      end
87    end
88    neighbors
89  end
90
91  def distance_between(source, destination)
92    @edges.each do |edge|
93      return edge.distance if edge.source == source and edge.destination == destination
94    end
95    nil
96  end
97end