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 in the SERVICE clause to find the shortest path between 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:weight>                  <property_uri> ; ]
     [ <csi:destination-vertex>      <destination_node_uri> ; ]
}

Property	Range	Description
<csi:binding-source-vertex>	variable	Required property that defines the name to use for the result column that lists the source nodes or vertices.
<csi:binding-vertex>	variable	Required property that defines the name to use for the result column that lists the nodes that are reachable by the source-vertex.
<csi:binding-predecessor>	variable	Required property that defines the name to use for the result column that lists the nodes that are on the path between the source and destination vertices.
<csi:graph>	URI	Required property that specifies the graph to query.
<csi:source-vertex>	URI	Required property that specifies the URI of the source node.
<csi:edge-label>	URI	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.
<csi:binding-distance>	variable	Optional property that adds a result column that lists the number of hops in the path between the source node and destination nodes. If csi:weight is specified, the binding-distance column displays the weight value.
<csi:weight>	URI	Optional property that specifies an edge property URI whose value can be used to determine the shortest path. When you do not specify a weight, the algorithm calculates the shortest path according the number of hops required to reach the destination vertex (or all nodes identified by the edge-label if destination-vertex is not specified). When weight is specified, the weight value is used as the shortest path measurement instead of the number of hops. For more information about properties, see Creating Labeled Property Graphs (RDF-star).
<csi:destination-vertex>	URI	Optional property that specifies the URI of the destination node. Include the destination-vertex URI when you want to find the shortest path between two specific vertices. When destination-vertex is excluded, AnzoGraph DB returns the shortest path between all vertices that are accessible by the edge-label. The value for this property is only applied when <csi:weight> is included in the query. It is ignored when <csi:weight> is excluded.

Shortest Path Examples

The examples below are run against a sample flight network data set, which contains data about flights, airlines, and airport locations. For instructions on downloading the sample data and loading it to AnzoGraph DB so that you can run the example queries, see Sample Data for Graph Algorithm Examples.

The following example finds the shortest path for flights from Boston (BOS) to Honolulu (HNL). In the query, the starting point or source node (csi:source-vertex) is the URI for BOS. To find the shortest path between BOS and HNL instead of the shortest path between BOS and all other airports that are reachable by the edge-label, the query includes the csi:destination-vertex property, which specifies the URI for HNL. The csi:weight property is also included and specifies the URI for the distanceMiles edge property. That tells the algorithm to calculate the shortest path by distance rather than number of hops.

prefix : <http://anzograph.com/data#>
prefix fl: <http://anzograph.com/flights/>
prefix owl: <http://www.w3.org/2002/07/owl#>
prefix skos: <http://www.w3.org/2004/02/skos/core#>

SELECT ?destination ?distance
FROM <http://anzograph.com/airline_flight_network>
WHERE 
{
  { 
    SERVICE <csi:shortest_path> 
  { 
      [] <csi:binding-vertex> ?airport ;
         <csi:binding-predecessor> ?predecessor ;
         <csi:binding-distance> ?distance ;
         <csi:graph> <http://anzograph.com/airline_flight_network> ;
         <csi:source-vertex> <http://anzograph.com/flights/Airport/BOS> ;
         <csi:destination-vertex> <http://anzograph.com/flights/Airport/HNL> ;
         <csi:edge-label> <http://anzograph.com/flights/hasRouteTo> ;
         <csi:weight> <http://anzograph.com/flights/distanceMiles> .
  }
  ?airport fl:terminalCode ?destination .
}
ORDER BY ?distance

The results (shown below) determine that the shortest path from BOS to HNL is through Salt Lake City (SLC). The binding-vertex column (?distance) shows the distance for each leg of the flight.

destination | distance
------------+-------------
BOS         |    0.000000
SLC         | 2105.000000
HNL         | 5099.000000
3 rows