albertorestifo/node-dijkstra

Limitation on cost 0

atanarro opened this issue · 3 comments

atanarro commented

Looking at the function isValidNode I see that a cost of 0 is forbidden.

function isValidNode(val) {
  const cost = Number(val);

  if (isNaN(cost) || cost <= 0) {
    return false;
  }

  return true;
}

I think a cost of 0 is a valid situation meaning that there is a connection between 2 nodes while it is costless.

Is there any reason for this limitation?

albertorestifo commented

The cost in the Dijkstra algorithm is expected to be a factor of the distance between nodes. If a node cost in 0, it means that node is in the same position as the neighboring node. This means the node will always be visited, no matter what.

Supposing the two nodes have the same connections, this means the node will always appear in the result. Suppose we have:

a:
   b: 3
   c: 2

b:
   a: 0
   c: 2

c:
   d: 1
   a: 2
   b: 2

If we start from A to D, the path will be A - B - C - D, despite A - B being in the same spot.

Supposing the two nodes have a different connection. If the cost between them is 0, it means they are in the same spot. Consequentially they should be merged into one.

Maybe I'm missing a use-case where you want a connection with cost 0? It would not break the algorithm but might lead to results containing more nodes than necessary, which is why there is the check.

atanarro commented

The problem I was solving is this one.

Basically the solution is using graphs like:

1:
   2: 1
2:
   1: 0
   3: 2
3:
   2: 0
   4: 3
   5: 1
4:
   3: 0
   6: 1
   5: 4
5:
   4: 0
   6: 5
6:
   5: 0

It has a cost to move from 1 to 2 but it is free to move the other way around (2 to 1). On this case the nodes are different and it is ok to include them on the path. For instance moving from 1 to 6 is faster 1-2-3-5-4-6 than 1-2-3-4-5-6.

lucasjvw commented

I agree that costs of 0 should be valid.
https://stackoverflow.com/questions/49460439/can-dijkstras-algorithm-work-on-a-graph-with-weights-of-0

Dijkstra's algorithm doesn't necessarily mean distance - just cost. Maybe it is free to move from node A to node B, but not free to move from node A to node C