Shortest Path

The Shortest Path algorithm finds the shortest path from a source node to the other reachable nodes in a graph.

Shortest Path Syntax

Graph algorithms are accessed from an internal SPARQL service endpoint. To incorporate the Shortest Path algorithm in a query, include a SERVICE statement in the WHERE clause. The service call specifies the name of the algorithm and defines the required and optional property values for that algorithm.

Use the following syntax to find the shortest path between two nodes in a graph. The table below describes each property.

SERVICE <csi:shortest_path> {
  [] <csi:binding-source-vertex>   ?source_vertex_variable_name ;
     <csi:binding-vertex>          ?binding_vertex_variable_name ;
     <csi:binding-predecessor>     ?predecessor_variable_name ;
     <csi:graph>                   <graph_uri> ;
     <csi:source-vertex>           <source_node_uri> ;
     <csi:edge-label>              <edge_uri> ;
   [ <csi:binding-distance>        ?binding_distance_variable_name ; ]
   [ <csi:weighted>                boolean_value ; ]
}

Property	Description	Range & Default Value
<csi:binding-source-vertex>	Required property that defines the name to use for the column in the results that lists the source nodes or vertices.	Range: Must be a variable name Default: none
<csi:binding-vertex>	Required property that defines the name to use for the column in the results that lists the nodes that are reachable by the source vertex.	Range: Must be a variable name Default: none
<csi:binding-predecessor>	Required property that defines the name to use for the column in the results that list the nodes that are on the path between the source and destination nodes.	Range: Must be a variable name Default: none
<csi:graph>	Required property that specifies the graph to query.	Range: Must be a URI Default: none
<csi:source-vertex>	Required property that specifies the URI of the source node.	Range: Must be a URI Default: none
<csi:edge-label>	Required property that lists the edge URI that defines the graph to operate on. The graph is the set of vertices that are connected by this URI.	Range: Must be a URI Default: none
<csi:binding-distance>	Optional property that, when included, adds a column that lists the number of hops in the path between the source node and the destination node (listed in the binding-vertex column in the results). Note: If the data has weighted edges, the binding-distance is the sum of the weights in the path.	Range: Must be a variable name Default: none
<csi:weighted>	Optional property that specifies whether to use a predefined edge property to determine the shortest path. Enable this option only if a property named weight is defined for the edge URI specified in edge-label. If the edge does not include a weight property and csi:weighted is true, the algorithm returns no results. For more information about edge properties, see Labeled Property Graphs (RDF*).	Range: true or false Default: false