You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
27 lines
830 B
Ruby
27 lines
830 B
Ruby
# Will find the shortest path between a source node and any other node in the graph.
|
|
# https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Using_a_priority_queue
|
|
|
|
def dijkstra(graph, source_node)
|
|
priority_queue = PriorityQueue.new
|
|
distance = Hash.new(Float::INFINITY)
|
|
distance[source_node] = 0
|
|
|
|
path = {}
|
|
|
|
graph.nodes.each { |node| priority_queue.add_with_priority(node, distance[node]) }
|
|
|
|
while priority_queue.count > 0
|
|
current_node = priority_queue.extract_min
|
|
current_node.neighbors.each do |node|
|
|
current_distance = distance[current_node] + 1
|
|
if current_distance < distance[node]
|
|
distance[node] = current_distance
|
|
path[node] = current_node
|
|
priority_queue.decrease_priority(node, current_distance)
|
|
end
|
|
end
|
|
end
|
|
|
|
[distance, path]
|
|
end
|