# tf\_graph\_shortest\_path

Given a distance-weighted directed graph, consisting of a query`CURSOR` 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.

```
SELECT * FROM TABLE(
    tf_graph_shortest_path(
        edge_list => CURSOR(
            SELECT node1, node2, distance FROM table
        ),
        origin_node => <origin node>,
        destination_node => <destination node>
    )
```

**Input Arguments**

| Parameter          | Description                                                                                                                                 | Data Types                                                                     |
| ------------------ | ------------------------------------------------------------------------------------------------------------------------------------------- | ------------------------------------------------------------------------------ |
| `node1`            | Origin node column in directed edge list CURSOR                                                                                             | Column< INT \| BIGINT \| TEXT ENCODED DICT>                                    |
| `node2`            | 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**

<table><thead><tr><th width="198">Name</th><th width="325">Description</th><th>Data Types</th></tr></thead><tbody><tr><td><code>path_step</code></td><td>The index of this node along the path traversal from <code>origin_node</code> to <code>destination_node</code>, with the first node (the <code>origin_node)</code> indexed as 1.</td><td>Column&#x3C; INT ></td></tr><tr><td><code>node</code></td><td>The current node along the path traversal from <code>origin_node</code> to <code>destination_node</code>. The first node (as denoted by <code>path_step</code> = 1) will always be the input <code>origin_node</code>, and the final node (as denoted by <code>MAX(path_step)</code>) will always be the input <code>destination_node</code>.</td><td>Column &#x3C; INT | BIGINT | TEXT ENCODED DICT> (same type as the <code>node1</code> and <code>node2</code> input columns)</td></tr><tr><td><code>cume_distance</code></td><td>The cumulative distance adding all input <code>distance</code> values from the <code>origin_node</code> to the current node.</td><td>Column &#x3C; INT | BIGINT | FLOAT | DOUBLE> (same type as the <code>distance</code> input column)</td></tr></tbody></table>

**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
```

<figure><img src="https://875484548-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FgWRc88gdQeZ7mRBB46Rx%2Fuploads%2Fgit-blob-890223ba732c03412a5978ed29d80cd3cf456389%2Fimage%20(8).png?alt=media" alt=""><figcaption><p>The computed shortest path along a time-traversal weighted road edge graph for the eastern US.</p></figcaption></figure>