-
Notifications
You must be signed in to change notification settings - Fork 0
/
dijkstra.rb
137 lines (106 loc) · 3.09 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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
# https://gist.github.com/jithinabraham/63d34bdf1c94a01d6e91864d4dc583f4
#
class Graph
attr_reader :graph, :nodes, :previous, :distance #getter methods
INFINITY = 1 << 64
def initialize
# the graph // {node => { edge1 => weight, edge2 => weight}, node2 => ...
@graph = Hash.new { |hash, key| hash[key] = {} }
@nodes = Array.new
end
# connect each node with target and weight
def connect_graph(source, target, weight = 1)
if (!graph.has_key?(source))
graph[source] = {target => weight}
else
graph[source][target] = weight
end
if (!nodes.include?(source))
nodes << source
end
if (!nodes.include?(target))
nodes << target
end
end
# connect each node bidirectional
def add_edge(source, target, weight = 1)
connect_graph(source, target, weight) #directional graph
connect_graph(target, source, weight) #non directed graph (inserts the other edge too)
end
# based of wikipedia's pseudocode: http://en.wikipedia.org/wiki/Dijkstra's_algorithm
def dijkstra(source)
@distance={}
@previous={}
nodes.each do |node|#initialization
@distance[node] = INFINITY #Unknown distance from source to vertex
@previous[node] = -1 #Previous node in optimal path from source
end
@distance[source] = 0 #Distance from source to source
unvisited_node = nodes.compact #All nodes initially in Q (unvisited nodes)
while (unvisited_node.size > 0)
u = nil;
unvisited_node.each do |min|
if (not u) or (@distance[min] and @distance[min] < @distance[u])
u = min
end
end
if (@distance[u] == INFINITY)
break
end
unvisited_node = unvisited_node - [u]
graph[u].keys.each do |vertex|
alt = @distance[u] + graph[u][vertex]
if (alt < @distance[vertex])
@distance[vertex] = alt
@previous[vertex] = u #A shorter path to v has been found
end
end
end
end
# To find the full shortest route to a node
def find_path(dest)
@path ||= []
if @previous[dest] != -1
find_path @previous[dest]
end
@path << dest
end
# Gets all shortests paths using dijkstra
def shortest_paths(source)
@graph_paths=[]
@source = source
dijkstra source
nodes.each do |dest|
@path=[]
find_path dest
actual_distance=if @distance[dest] != INFINITY
@distance[dest]
else
"no path"
end
@graph_paths<< "Target(#{dest}) #{@path.join("-->")} : #{actual_distance}"
end
@graph_paths
end
# print result
def print_result
@graph_paths.each do |graph|
puts graph
end
end
end
if __FILE__ == $0
#sample input as per http://en.wikipedia.org/wiki/Dijkstra's_algorithm
gr = Graph.new
gr.add_edge("a", "c", 7)
gr.add_edge("a", "e", 14)
gr.add_edge("a", "f", 9)
gr.add_edge("c", "d", 15)
gr.add_edge("c", "f", 10)
gr.add_edge("d", "f", 11)
gr.add_edge("d", "b", 6)
gr.add_edge("f", "e", 2)
gr.add_edge("e", "b", 9)
gr.shortest_paths("a")
gr.print_result
end