Given a distance-weighted directed graph, consisting of a queryCURSOR input consisting of the starting and ending node for each edge and a distance, and a specified origin and destination node, tf_graph_shortest_path computes the shortest distance-weighted path through the graph between origin_node and destination_node, returning a row for each node along the computed shortest path, with the traversal-ordered index of that node and the cumulative distance from the origin_node to that node. If either origin_node or destination_node do not exist, an error is returned.
Destination node column in directed edge list CURSOR
Column< INT | BIGINT | TEXT ENCODED DICT> (must be the same type as node1)
distance
Distance between origin and destination node in directed edge list CURSOR
Column< INT | BIGINT | FLOAT | DOUBLE >
origin_node
The origin node to start graph traversal from. If not a value present in edge_list.node1, will cause empty result set to be returned.
BIGINT | TEXT ENCODED DICT
destination_node
The destination node to finish graph traversal at. If not a value present in edge_list.node1, will cause empty result set to be returned.
BIGINT | TEXT ENCODED DICT
Output Columns
Name
Description
Data Types
path_step
The index of this node along the path traversal from origin_node to destination_node, with the first node (the origin_node) indexed as 1.
Column< INT >
node
The current node along the path traversal from origin_node to destination_node. The first node (as denoted by path_step = 1) will always be the input origin_node, and the final node (as denoted by MAX(path_step)) will always be the input destination_node.
Column < INT | BIGINT | TEXT ENCODED DICT> (same type as the node1 and node2 input columns)
cume_distance
The cumulative distance adding all input distance values from the origin_node to the current node.
Column < INT | BIGINT | FLOAT | DOUBLE> (same type as the distance input column)
Example A
/* Compute the shortest flight route on United Airlines for the year 2008 as measured
by flight time between origin airport 'RDU' (Raleigh-Durham, NC) and destination
airport 'SAT' (San Antonio, TX), adding 60 minutes for each leg to account for
boarding/plane change time costs, and only counting routes that were flown at least
300 times during the year. */
SELECT
*
FROM
TABLE(
tf_graph_shortest_path(
edge_list => CURSOR(
SELECT
origin,
dest,
/* Add 60 minutes to each leg to account
for boarding/plane change costs */
AVG(airtime) + 60 as avg_airtime
FROM
flights_2008
WHERE
carrier_name = 'United Air Lines'
GROUP by
origin,
dest
HAVING
COUNT(*) > 300
),
origin_node => 'RDU',
destination_node => 'SAT'
)
)
ORDER BY
path_step
path_step|node|cume_distance
1|RDU|0
2|ORD|167
3|DEN|354
4|SAT|519
Example B
/* Compute the shortest path between along a time-traversal weighted
edge graph of roads in the Eastern United States between a location in North Carolina and
a location in Maine, joining to a node locations table to output the lon/lat pairs
of each node. */
select
path_step,
node,
lon,
lat,
cume_distance
from
table(
tf_graph_shortest_path(
cursor(
select
node1,
node2,
traversal_time
from
usa_roads_east_time
),
1561955,
1591319
)
),
USA_roads_east_coords
where
node = node_id
order by
cume_distance desc
limit 20;
path_step|node|lon|lat|cume_distance
4380|1591319|-71.55136299999999|43.75256|13442017
4379|1591989|-71.55174099999999|43.75245|13441199
4378|1589348|-71.554147|43.752464|13436371
4377|2315795|-71.554867|43.752489|13434924
4376|1589286|-71.55497099999999|43.752113|13434214
4375|1589285|-71.555049|43.751833|13433685
4374|2315785|-71.555999|43.750704|13431238
4373|2315973|-71.55798799999999|43.748622|13426553
4372|2315950|-71.56366299999999|43.746268|13417798
4371|1589788|-71.56476599999999|43.745765|13416053
4370|1591997|-71.56484|43.745691|13415884
4369|1589787|-71.564886|43.745645|13415779
4368|2315951|-71.56517599999999|43.745353|13415113
4367|2315952|-71.56659499999999|43.744599|13412756
4366|1591999|-71.56685899999999|43.744565|13412397
4365|543394|-71.567357|43.744335|13411606
4364|543393|-71.567832|43.744116|13410852
4363|543392|-71.571827|43.743673|13405444
4362|541181|-71.57268499999999|43.743802|13404271
4361|1589786|-71.572964|43.743844|13403890
The computed shortest path along a time-traversal weighted road edge graph for the eastern US.
