"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](https://dgraph.io#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/](https://dgraph.io/docs/query-language/kshortest-path-quries/)
---
### Author:  [@greatvovan](https://discuss.dgraph.io/u/greatvovan)
#### Post date: [October 8, 2020, 8:04pm UTC](https://discuss.dgraph.io/t/shortest-path-queries-query-language/9793/2 "2020-10-08T20:04:10Z")
Nice article and examples!
I wonder, is there a syntax to query only the shortest path **length**?
---
### Author:  [@Anurag](https://discuss.dgraph.io/u/Anurag)
#### Post date: [October 9, 2020, 5:25am UTC](https://discuss.dgraph.io/t/shortest-path-queries-query-language/9793/3 "2020-10-09T05:25:35Z")
Not really, you can query the shortest path and from the JSON respone get the path length.
---
### Author:  [@greatvovan](https://discuss.dgraph.io/u/greatvovan)
#### Post date: [October 10, 2020, 8:43pm UTC](https://discuss.dgraph.io/t/shortest-path-queries-query-language/9793/4 "2020-10-10T20:43:47Z")
All the examples use UIDs. How can I query the same but identify source and destination nodes by a specific attribute, say `name`?
---
### Author:  [@Anurag](https://discuss.dgraph.io/u/Anurag)
#### Post date: [October 10, 2020, 8:51pm UTC](https://discuss.dgraph.io/t/shortest-path-queries-query-language/9793/5 "2020-10-10T20:51:57Z")
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:
```auto
{
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
}
}
```
---
### Author:  [@doushubao1984](https://discuss.dgraph.io/u/doushubao1984)
#### Post date: [February 18, 2021, 6:37am UTC](https://discuss.dgraph.io/t/shortest-path-queries-query-language/9793/6 "2021-02-18T06:37:56Z")
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
---
### Author:  [@Anurag](https://discuss.dgraph.io/u/Anurag)
#### Post date: [February 18, 2021, 7:09am UTC](https://discuss.dgraph.io/t/shortest-path-queries-query-language/9793/7 "2021-02-18T07:09:28Z")
Is your source variable storing more than one nodes?
Above code snippet is for single source shortest path.
---
### Author:  [@doushubao1984](https://discuss.dgraph.io/u/doushubao1984)
#### Post date: [February 18, 2021, 7:36am UTC](https://discuss.dgraph.io/t/shortest-path-queries-query-language/9793/8 "2021-02-18T07:36:25Z")
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?
---
### Author:  [@Anurag](https://discuss.dgraph.io/u/Anurag)
#### Post date: [February 18, 2021, 7:57am UTC](https://discuss.dgraph.io/t/shortest-path-queries-query-language/9793/9 "2021-02-18T07:57:30Z")
I would suggest to do that in multiple queries.
---
### Author:  [@doushubao1984](https://discuss.dgraph.io/u/doushubao1984)
#### Post date: [February 18, 2021, 8:14am UTC](https://discuss.dgraph.io/t/shortest-path-queries-query-language/9793/10 "2021-02-18T08:14:11Z")
I see.
Hopefully dgraph could support it in one query in the next version.
---
### Author:  [@farid](https://discuss.dgraph.io/u/farid)
#### Post date: [November 18, 2021, 9:05am UTC](https://discuss.dgraph.io/t/shortest-path-queries-query-language/9793/12 "2021-11-18T09:05:39Z")
when doing the shortest path, how can I return all the “names” the path has traversed through, rather than just getting the UID
another question would be if I want to find the with numpaths of 2 or greater, but for 3 nodes
somehow numpaths does not work in this scenario
{
A as var(func: eq(name, “Alice”))
E as var(func: eq(name, “Ethan”))
C as var(func: eq(name, “Chow”))
AEpath as shortest(from: uid(A), to: uid(E), numpaths: 2) {
friend
}
ACpath as shortest(from: uid(A), to: uid(C), numpaths: 2) {
friend
}
CEpath as shortest(from: uid(C), to: uid(E), numpaths: 2) {
friend
}
sp1path(func: uid(AEpath)) {
name
uid
}
sp2path(func: uid(ACpath)) {
name
uid
}
sp3path(func: uid(CEpath)) {
name
uid
}
}