Shortest Path Queries

How do I query the shortest paths for different types of nodes?
For example:kim have a lot of friends, and these friends also have friends, all of whom may have K-Box. Now I want to check with Kim’s closest relation, who has K-Box.

2

The blue nodes: dgraph type is “Person”, predicate is “name”
The edge between the blue nodes is “friend”
The green nodes: dgraph type is “GameBox”, predicate is “box_name”
The edge between blue node and green node is “has_box”

How do I know what the order of closest relationships is 1–>4–>8.And not1–>2–>5–>9

Hi @Soultrans,

Using shortest path queries, a user can get path(nodes and edges) from a given node A to node B. I see that you want to find the shortest path from node 1 to any node of type "Gamebox" . One way this could be done is by adding an edge from each node of type "Gamebox" to a dummy node, say of type "AllGameBoxes" . Now, you could use a shortest path query to find shortest path from node 1 to this dummy node.
As all nodes of type "Gamebox" are connected to the dummy node. The path returned by query will be the shortest path going from node 1 to any of the Gamebox. By applying filters on the obtained path, you could then find the closest relation who has a K-box.

Note that the shortest path query does not have a limitation on node type, you just need to specify all the predicates (edges) that have to be considered for traversal.

Reference: https://dgraph.io/docs/query-language/kshortest-path-quries/

Thanks a lot.I’ll try it.

1 Like