-
Notifications
You must be signed in to change notification settings - Fork 1
/
shortest_route.rb
55 lines (38 loc) · 1.03 KB
/
shortest_route.rb
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#Question - https://www.interviewcake.com/question/ruby/mesh-message?section=trees-graphs&course=fc1
require 'pry'
def send_a_message(network, sender, receiver)
neighbours = network[sender]
already_seen = []
neighbours_to_check = []
path_to = {}
path_exists = false
neighbours_to_check << sender
already_seen << sender
path_to[sender] = nil
until neighbours_to_check.empty?
current = neighbours_to_check.pop
if current == receiver
path_exists = true
break
end
network[current].each do |person|
next if already_seen.include? person
already_seen << person
neighbours_to_check << person
path_to[person] = current
end
end
if path_exists
actual_path = []
current = receiver
while current
actual_path << current
current = path[current]
end
return actual_path
else
nil
end
end
test
#A better approach is to use a queue instead of an array. FIFO. O[1]. Array has O[1] insert but O[n] lookup.