-
Notifications
You must be signed in to change notification settings - Fork 1
/
dijkstra.rb
116 lines (90 loc) · 2.53 KB
/
dijkstra.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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
require 'pry'
class Edge
def initialize(destination, weight)
@destination = destination
@weight = weight
end
attr_accessor :destination, :weight
end
lines = File.open("./dijkstraData.txt", "r").readlines
edges = {}
lines.each do |line|
line_items = line.split(" ")
vertex = line_items[0].to_i
unless line_items[1...line_items.length].nil?
line_items[1...line_items.length].each do |pair|
destination, weight = pair.split(",").map(&:to_i)
edges[vertex] ||= []
edges[vertex] << Edge.new(destination, weight)
edges[destination] ||= []
edges[destination] << Edge.new(vertex, weight)
end
end
end
def vertex_with_min_distance(edges, distances, unvisited)
min = Float::INFINITY
node_to_visit = nil
unvisited.each do |unvisited_node|
if distances[unvisited_node] < min
min = distances[unvisited_node]
node_to_visit = unvisited_node
end
end
node_to_visit
end
def dijkstra(edges, source)
distances = {}
previous = {}
unvisited = []
distances[source] = 0
previous[source] = nil
edges.each do |node, edge_array|
unless source == node
distances[node] = Float::INFINITY
previous[node] = nil
end
unvisited.push node
end
u = source
while unvisited.any?
u = vertex_with_min_distance(edges, distances, unvisited)
puts "#{u} is closest. Deleteing #{u}"
unvisited.delete(u)
puts "#{unvisited.count} left unvisited"
if edges[u]
edges[u].each do |edge|
alt = distances[u] + edge.weight
if alt < distances[edge.destination]
distances[edge.destination] = alt
previous[edge.destination] ||= []
previous[edge.destination] << u
end
end
end
end
return [distances, previous]
end
def output_format(distances_hash, paths_hash)
distances_hash.each do |node, distance_traveled|
path = paths_hash[node] ? paths_hash[node] - [1]: []
puts "#{node} #{distance_traveled} #{path}"
end
end
def big_output_format(distances_hash, paths_hash)
nodes_to_output = [7,37,59,82,99,115,133,165,188,197]
nodes_to_output.each do |node|
path = node ? paths_hash[node] - [1]: []
puts "#{node} #{distances_hash[node]} #{path}"
end
end
def big_output_format_dist(distances_hash, paths_hash)
nodes_to_output = [7,37,59,82,99,115,133,165,188,197]
nodes_to_output.each do |node|
path = node ? paths_hash[node] - [1]: []
puts "#{node} #{distances_hash[node]}"
end
end
x = dijkstra(edges, 1)
binding.pry
big_output_format_dist(x.first, x[1])
binding.pry