Shortest Path Queries - Query language

The shortest path between a source (from) node and destination (to) node can be found using the keyword shortest for the query block name. It requires the source node UID, destination node UID and the predicates (at least one) that have to be considered for traversal. A shortest query block returns the shortest path under _path_ in the query response. The path can also be stored in a variable which is used in other query blocks.

K-Shortest Path queries: By default the shortest path is returned. With numpaths: k, and k > 1, the k-shortest paths are returned. Cyclical paths are pruned out from the result of k-shortest path query. With depth: n, the paths up to n depth away are returned.

Note
  • If no predicates are specified in the shortest block, no path can be fetched as no edge is traversed.
  • If you’re seeing queries take a long time, you can set a gRPC deadline to stop the query after a certain amount of time.

For example:

curl localhost:8080/alter -XPOST -d $'
    name: string @index(exact) .
' | python -m json.tool | less
curl -H "Content-Type: application/rdf" localhost:8080/mutate?commitNow=true -XPOST -d $'
{
  set {
    _:a <friend> _:b (weight=0.1) .
    _:b <friend> _:c (weight=0.2) .
    _:c <friend> _:d (weight=0.3) .
    _:a <friend> _:d (weight=1) .
    _:a <name> "Alice" .
    _:a <dgraph.type> "Person" .
    _:b <name> "Bob" .
    _:b <dgraph.type> "Person" .
    _:c <name> "Tom" .
    _:c <dgraph.type> "Person" .
    _:d <name> "Mallory" .
    _:d <dgraph.type> "Person" .
  }
}' | python -m json.tool | less

The shortest path between Alice and Mallory (assuming UIDs 0x2 and 0x5 respectively) can be found with query:

curl -H "Content-Type: application/graphql+-" localhost:8080/query -XPOST -d $'{
 path as shortest(from: 0x2, to: 0x5) {
  friend
 }
 path(func: uid(path)) {
   name
 }
}' | python -m json.tool | less

Which returns the following results. (Note, without considering the weight facet, each edges’ weight is considered as 1)

{
  "data": {
    "path": [
      {
        "name": "Alice"
      },
      {
        "name": "Mallory"
      }
    ],
    "_path_": [
      {
        "uid": "0x2",
        "friend": [
          {
            "uid": "0x5"
          }
        ]
      }
    ]
  }
}

We can return more paths by specifying numpaths. Setting numpaths: 2 returns the shortest two paths:

curl -H "Content-Type: application/graphql+-" localhost:8080/query -XPOST -d $'{
 A as var(func: eq(name, "Alice"))
 M as var(func: eq(name, "Mallory"))
 path as shortest(from: uid(A), to: uid(M), numpaths: 2) {
  friend
 }
 path(func: uid(path)) {
   name
 }
}' | python -m json.tool | less
Note In the query above, instead of using UID literals, we query both people using var blocks and the uid() function. You can also combine it with GraphQL Variables.

Edges weights are included by using facets on the edges as follows.

Note Only one facet per predicate is allowed in the shortest query block.

curl -H "Content-Type: application/graphql+-" localhost:8080/query -XPOST -d $'{
 path as shortest(from: 0x2, to: 0x5) {
  friend @facets(weight)
 }
 path(func: uid(path)) {
  name
 }
}' | python -m json.tool | less
{
  "data": {
    "path": [
      {
        "name": "Alice"
      },
      {
        "name": "Bob"
      },
      {
        "name": "Tom"
      },
      {
        "name": "Mallory"
      }
    ],
    "_path_": [
      {
        "uid": "0x2",
        "friend": [
          {
            "uid": "0x3",
            "friend|weight": 0.1,
            "friend": [
              {
                "uid": "0x4",
                "friend|weight": 0.2,
                "friend": [
                  {
                    "uid": "0x5",
                    "friend|weight": 0.3
                  }
                ]
              }
            ]
          }
        ]
      }
    ]
  }
}

Constraints can be applied to the intermediate nodes as follows.

curl -H "Content-Type: application/graphql+-" localhost:8080/query -XPOST -d $'{
  path as shortest(from: 0x2, to: 0x5) {
    friend @filter(not eq(name, "Bob")) @facets(weight)
    relative @facets(liking)
  }
  relationship(func: uid(path)) {
    name
  }
}' | python -m json.tool | less

The k-shortest path algorithm (used when numpaths > 1) also accepts the arguments minweight and maxweight, which take a float as their value. When they are passed, only paths within the weight range [minweight, maxweight] will be considered as valid paths. This can be used, for example, to query the shortest paths that traverse between 2 and 4 nodes.

curl -H "Content-Type: application/graphql+-" localhost:8080/query -XPOST -d $'{
 path as shortest(from: 0x2, to: 0x5, numpaths: 2, minweight: 2, maxweight: 4) {
  friend
 }
 path(func: uid(path)) {
   name
 }
}' | python -m json.tool | less

Some points to keep in mind for shortest path queries:

  • Weights must be non-negative. Dijkstra’s algorithm is used to calculate the shortest paths.
  • Only one facet per predicate in the shortest query block is allowed.
  • Only one shortest path block is allowed per query. Only one _path_ is returned in the result. For queries with numpaths > 1, _path_ contains all the paths.
  • Cyclical paths are not included in the result of k-shortest path query.
  • For k-shortest paths (when numpaths > 1), the result of the shortest path query variable will only return a single path which will be the shortest path among the k paths. All k paths are returned in _path_.

This is a companion discussion topic for the original entry at https://dgraph.io/docs/query-language/kshortest-path-quries/

Nice article and examples!
I wonder, is there a syntax to query only the shortest path length?

Not really, you can query the shortest path and from the JSON respone get the path length.

All the examples use UIDs. How can I query the same but identify source and destination nodes by a specific attribute, say name?

You can store the nodes in the variable which matches the filter and then use that variable in from: and to:

Edit:
Here is the query example:

{ 
  var(func: eq(name, "A")){
   SOURCE as uid
  }
  var(func: eq(name, "L")){
   TARGET as uid
  }  

  path as shortest(from: uid(SOURCE), to: uid(TARGET)) {
    friend
  }
  
   path(func: uid(path)) {
    name
   } 
}

Hi Anurag,

Could you tell me which version of dgraph supports this kind of shortest Path query?

I used v20.11 dgraph, and got below error:

from variable(SOURCE) should only expand to 1uid.

Best Regards,
Gary

Is your source variable storing more than one nodes?

Above code snippet is for single source shortest path.

Thanks a lot for your reply!

Yes, source variable stores multiple nodes.

If I want to do shortest path query from multiple nodes to multiple nodes, how to write the query?

I would suggest to do that in multiple queries.

I see.

Hopefully dgraph could support it in one query in the next version.