Shortest path computes wrong path

[campoy]

What version of Dgraph are you using?

v1.1.0

Have you tried reproducing the issue with the latest release?

yes

What is the hardware spec (RAM, OS)?

n/a

Steps to reproduce the issue (command/config used to run Dgraph).

Given this data and assuming a name has an exact index:

{
  set {
    _:a <name> "A" .
    _:b <name> "B" .
    _:c <name> "C" .
    _:d <name> "D" .

    _:a <connects> _:b  (weight=10) .
    _:a <connects> _:c  (weight=1) .
    _:a <connects> _:d  (weight=10) .

    _:c <connects> _:a  (weight=10) .
    _:c <connects> _:b  (weight=10) .
    _:c <connects> _:d  (weight=1) .

    _:b <connects> _:a  (weight=10) .
    _:b <connects> _:c  (weight=10) .
    _:b <connects> _:d  (weight=10) .

    _:d <connects> _:a  (weight=10) .
    _:d <connects> _:b  (weight=1) .
    _:d <connects> _:c  (weight=10) .
  }
}

We try to get the shortest path from A to B using the weight facet for it and limiting to D depth.

{
  a as var(func: eq(name, "A"))
  b as var(func: eq(name, "B"))
  
  path as shortest(from: uid(a), to: uid(b), depth: D) {
    connects @facets(weight)
  }
  
  path(func: uid(path)) {
    uid
    name
  }
}

Expected behaviour and actual result.

This table explains what I expect to see vs what I got:

D	expected path (cost)	got path (cost)	ok
0	N/A	A - B (10)	❌
1	A - B (10)	A - C - D - B (3)	❌
2	A - B (10)	A - B (10)	✔️
> 3	A - C - D - B (3)	A - B (3)	❌

[pawanrawal]

So for depth 2, the shortest path that should be returned should be the path (A->C->D->B) even though the actual path has length 3. This is because depth represents how many times we expand out the graph.

1st expansion
Start = [ A ]
Reach = [ B, C, D ]

2nd expansion
Start = [ B C D ]
Reach = [ E ] (we also reach other old nodes)

The thing to note is we don't just expand the node that we are processing currently but all the nodes that were the result of the last expansion (think query processing in Dgraph). So we only expand out the graph twice but still get the shortest path here. @campoy let me know what do you think about this.

[campoy]

Based on the documentation:

With depth: n, the shortest paths up to n hops away are returned.

I'd say that paths with length longer than depth should be ignored. That would fix the issue for D=1.
Otherwise, we'd be exposing an implementation detail.

How about D=0 and D>3?

[pawanrawal]

The path is still technically only 2 hops away, note a hop (a graph expansion) is different from the length of the path. The response for D=0, D=1 and D>3 is same as what you have proposed above. Only for D=2, the correct solution seems to be A-C-D-B.