BellmanFord and Dijkstra not working with undirected graphs.

[oschakravarthi]

var g = new jsgraphs.WeightedGraph(2); g.addEdge(new jsgraphs.Edge(0, 1, 5.0)); var dijkstra = new jsgraphs.Dijkstra(g, 0); var has0To1 = idijkstra.hasPathTo(1); // True.. as expected

    dijkstra1 = new jsgraphs.Dijkstra(g, 1);
    var has1To0 = idijkstra.hasPathTo(0); //It is returning false. But it should return true as the graph is a Undirected graph

[sp1r1t]

Hi oschakravarthi,

I can not reproduce your problem. For me the hasPathTo function returns true in both cases. Though I had to change your 4th line of code (and in the code block), as it says idijkstra, instead of dijkstra (as declared).

So this code prints true two times on my machine:

const jsgraphs = require('js-graph-algorithms');

var g = new jsgraphs.WeightedGraph(2); 
g.addEdge(new jsgraphs.Edge(0, 1, 5.0));
var dijkstra = new jsgraphs.Dijkstra(g, 0);
var has0To1 = dijkstra.hasPathTo(1); 

console.log(has0To1); // true

dijkstra1 = new jsgraphs.Dijkstra(g, 1);
var has1To0 = dijkstra.hasPathTo(0);

console.log(has1To0); //true

I suggest to close this issue.

Greetings, sp1r1t

[cxcorp]

I agree with the observation about Dijkstra. Example:

const g = new jsgraphs.WeightedGraph(2); 
g.addEdge(new jsgraphs.Edge(1, 0, 5.0));
const dijkstra = new jsgraphs.Dijkstra(g, 0);
const has0To1 = dijkstra.hasPathTo(1); 

console.log(has0To1); // false

However, when changing the Edge to be from 0->1 instead of 1->0, it works as expected:

const g = new jsgraphs.WeightedGraph(2); 
g.addEdge(new jsgraphs.Edge(0, 1, 5.0));
const dijkstra = new jsgraphs.Dijkstra(g, 0);
const has0To1 = dijkstra.hasPathTo(1); 

console.log(has0To1); // false

This is because the relax function always takes v to be e.from, so the order of the nodes in the Edge becomes significant. I have fixed it myself like so:

diff --git a/src/jsgraphs.js b/src/jsgraphs.js
index 5409240..0bcb196 100644
--- a/src/jsgraphs.js
+++ b/src/jsgraphs.js
@@ -955,7 +955,7 @@ var jsgraphs = jsgraphs || {};
             var adj_v = G.adj(v);
             for(var i = 0; i < adj_v.length; ++i) {
                 var e = adj_v[i];
-                this.relax(e);
+                this.relax(v, e);
             }
         }

@@ -964,10 +964,9 @@ var jsgraphs = jsgraphs || {};

-    Dijkstra.prototype.relax = function(e) {
+    Dijkstra.prototype.relax = function(v, e) {

-        var v = e.from();
-        var w = e.to();
+        var w = e.other(v)

         if(this.cost[w] > this.cost[v] + e.weight) {
             this.cost[w] = this.cost[v] + e.weight;

Additionally, I am quite surprised if the algorithm works at all, since there is a typo in the comparison function that is passed in Dijkstra (#15)