Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Typo in Dijkstra's priority queue comparison function breaks Dijkstra #15

Open
cxcorp opened this issue Jul 10, 2024 · 0 comments
Open

Comments

@cxcorp
Copy link

cxcorp commented Jul 10, 2024

When creating the min priority queue, the Dijkstra function passes in return cost1, cost2 as the function, causing it to always return cost2:

this.pq = new jss.IndexMinPQ(V, function(cost1, cost2){
return cost1, cost2;
});

It should probably be cost1 - cost2, like:

diff --git a/src/jsgraphs.js b/src/jsgraphs.js
index 5409240..1392673 100644
--- a/src/jsgraphs.js
+++ b/src/jsgraphs.js
@@ -936,7 +936,7 @@ var jsgraphs = jsgraphs || {};
         this.edgeTo = [];
         this.cost = [];
         this.pq = new jss.IndexMinPQ(V, function(cost1, cost2){
-            return cost1, cost2;
+            return cost1 - cost2;
         });
         
         for(var v =0; v < V; ++v){
@cxcorp cxcorp changed the title Typo in Dijkstra's priority queue comparison function Typo in Dijkstra's priority queue comparison function breaks Dijkstra Jul 10, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant