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 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 Description Range & Default Value
<csi:binding-source-vertex> Required property that defines the name to use for the result column 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 result column 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 result column that lists the nodes that are on the path between the source and destination vertices. 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 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. Range: Must be a variable name
Default: none
<csi:weight> 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 and Querying Labeled Property Graphs (RDF*). Range: Must be a URI
Default: none
<csi:destination-vertex> 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 returns the shortest path between all vertices that are accessible by the edge-label. Range: Must be a URI
Default: none

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 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
Related Topics