Implementation of Dijkstra with adjacency list and priority queue in Ruby

.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty margin-bottom:0;

up vote
0
down vote

favorite

require 'pqueue'
def dijkstra(source, edges, num_vertices)
 path_weights = Array.new(num_vertices, Float::INFINITY)
 previous_shortest_path = Array.new(num_vertices, nil)
 pq = PQueue.new([source])x,y
 path_weights[source] = 0

 while pq.size != 0
 min_node = pq.pop
 # Note: If we are interested only in shortest distance from source to a single target, we can break the for loop when the picked minimum distance vertex is equal to target

 (edges[min_node] || ).each do |neighbor, weight|
 if path_weights[neighbor] > path_weights[min_node] + weight
 path_weights[neighbor] = path_weights[min_node] + weight
 previous_shortest_path[neighbor] = min_node
 pq.push(neighbor)
 end
 end
 end

 return [path_weights, previous_shortest_path]
end

Assuming that the priority queue uses a binary heap, this should be O(E log V)

Would this work for all graphs without negative cycles? Any obvious improvements or edge cases missing?

edited May 14 at 4:24

Mast

7,32563484

asked May 13 at 22:03

bgcode

1012

add a commentÂ |Â

up vote
0
down vote

favorite

require 'pqueue'
def dijkstra(source, edges, num_vertices)
 path_weights = Array.new(num_vertices, Float::INFINITY)
 previous_shortest_path = Array.new(num_vertices, nil)
 pq = PQueue.new([source])x,y
 path_weights[source] = 0

 while pq.size != 0
 min_node = pq.pop
 # Note: If we are interested only in shortest distance from source to a single target, we can break the for loop when the picked minimum distance vertex is equal to target

 (edges[min_node] || ).each do |neighbor, weight|
 if path_weights[neighbor] > path_weights[min_node] + weight
 path_weights[neighbor] = path_weights[min_node] + weight
 previous_shortest_path[neighbor] = min_node
 pq.push(neighbor)
 end
 end
 end

 return [path_weights, previous_shortest_path]
end

Assuming that the priority queue uses a binary heap, this should be O(E log V)

Would this work for all graphs without negative cycles? Any obvious improvements or edge cases missing?

edited May 14 at 4:24

Mast

7,32563484

asked May 13 at 22:03

bgcode

1012

add a commentÂ |Â

up vote
0
down vote

favorite

require 'pqueue'
def dijkstra(source, edges, num_vertices)
 path_weights = Array.new(num_vertices, Float::INFINITY)
 previous_shortest_path = Array.new(num_vertices, nil)
 pq = PQueue.new([source])x,y
 path_weights[source] = 0

 while pq.size != 0
 min_node = pq.pop
 # Note: If we are interested only in shortest distance from source to a single target, we can break the for loop when the picked minimum distance vertex is equal to target

 (edges[min_node] || ).each do |neighbor, weight|
 if path_weights[neighbor] > path_weights[min_node] + weight
 path_weights[neighbor] = path_weights[min_node] + weight
 previous_shortest_path[neighbor] = min_node
 pq.push(neighbor)
 end
 end
 end

 return [path_weights, previous_shortest_path]
end

Assuming that the priority queue uses a binary heap, this should be O(E log V)

Would this work for all graphs without negative cycles? Any obvious improvements or edge cases missing?

edited May 14 at 4:24

Mast

7,32563484

asked May 13 at 22:03

bgcode

1012

require 'pqueue'
def dijkstra(source, edges, num_vertices)
 path_weights = Array.new(num_vertices, Float::INFINITY)
 previous_shortest_path = Array.new(num_vertices, nil)
 pq = PQueue.new([source])x,y
 path_weights[source] = 0

 while pq.size != 0
 min_node = pq.pop
 # Note: If we are interested only in shortest distance from source to a single target, we can break the for loop when the picked minimum distance vertex is equal to target

 (edges[min_node] || ).each do |neighbor, weight|
 if path_weights[neighbor] > path_weights[min_node] + weight
 path_weights[neighbor] = path_weights[min_node] + weight
 previous_shortest_path[neighbor] = min_node
 pq.push(neighbor)
 end
 end
 end

 return [path_weights, previous_shortest_path]
end

Assuming that the priority queue uses a binary heap, this should be O(E log V)

Would this work for all graphs without negative cycles? Any obvious improvements or edge cases missing?

edited May 14 at 4:24

Mast

7,32563484

asked May 13 at 22:03

bgcode

1012

edited May 14 at 4:24

Mast

7,32563484

edited May 14 at 4:24

Mast

7,32563484

edited May 14 at 4:24

Mast

7,32563484

asked May 13 at 22:03

bgcode

1012

asked May 13 at 22:03

bgcode

1012

asked May 13 at 22:03

bgcode

1012

add a commentÂ |Â

active

oldest

votes

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
);
);
, "mathjax-editing");

StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "196"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: false,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);

);

draft saved

draft discarded

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f194324%2fimplementation-of-dijkstra-with-adjacency-list-and-priority-queue-in-ruby%23new-answer', 'question_page');

);

Post as a guest

Name

active

oldest

votes

draft saved

draft discarded

draft saved

draft discarded

Post as a guest

Name

AJlsfiFzysI pcZx2,k3SfTQcxT,2Xq2LPLz0sJnGztdRl kqncHx7RUgc9NpaXkUN,qae52eYy g BAyVqo5ggeddmcGAMG W

搜尋此網誌

trjhtr