# Single-source Shortest Path (Weighted)

Supported Graph Characteristics
 Weighted edges Directed edges Undirected edges Homogeneous vertex types Heterogeneous vertex types

Finding shortest paths in a graph with weighted edges is algorithmically harder than in an unweighted graph because even after you find one path to a vertex T, you cannot be certain that it is a shortest path.

If edge weights are always positive, then you must keep trying until you have considered every in-edge to T. If edge weights can be negative, then it’s even harder. You must consider all possible paths.

A classic application for a weighted shortest path algorithm is finding the shortest travel route to get from an origin location to a destination location. In this case, the edge weights would be the distances between vertices. In general, any application where you are looking for the cheapest route is a possible fit.

## Notes

If you have edges with positive weights, use `shortest_path_pos_wt`, which is based on the delta-stepping approach, to take advantage of TigerGraph’s parallel processing. The well-known Dijsktra’s algorithm is not used because it is not appropriate for parallel computation.

If you have edges with both positive and negative weights, use `shortest_path_any_wt`, which implements the Bellman-Ford algorithm. If there is more than one path with the same total weight, the algorithm returns one of them.

## Specifications

The shortest path algorithm can be optimized if we know all the weights are non-negative. If there can be negative weights, then sometimes a longer path will have a lower cumulative weight. Therefore, we have two versions of this algorithm

``````tg_shortest_ss_pos_wt (VERTEX source, SET<STRING> v_type, SET<STRING> e_type,
STRING wt_attr, STRING wt_type, INT output_limit = -1, BOOL print_accum = TRUE,
STRING result_attr = "", STRING file_path = "", BOOL display_edges = FALSE)``````
``````tg_shortest_ss_any_wt (VERTEX source, SET<STRING> v_type, SET<STRING> e_type,
STRING wt_attr, STRING wt_type, INT output_limit = -1, BOOL print_accum = TRUE,
STRING result_attr = "", STRING file_path = "", BOOL display_edges = FALSE)``````

### Parameters

Parameter Description Default

`VERTEX source`

ID of the source vertex

(empty string)

`SET<STRING> v_type`

Names of vertex types to use

(empty string)

`SET<STRING> e_type`

Names of edge types to use

N/A

`STRING wt_attr`

Name of the edge weight attribute

(empty string)

`STRING wt_type`

The data type of the edge weight attribute. Can be `INT`, `FLOAT`, or `DOUBLE`.

(empty string)

`INT output_limit`

If >=0, max number of vertices to output to JSON

-1

`BOOL print_accum`

Whether to print results in JSON format to standard output

True

`STRING result_attr`

If not empty, store distance values in INT to this vertex attribute

(empty string)

`STRING file_path`

If not empty, write output to this file.

(empty string)

`BOOL display_edges`

If true, include the graph’s edges in the JSON output, so that the full graph can be displayed in the query view window on GraphStudio.

False

### Output

Computes a shortest distance (given in `INT` format) and a shortest path (`STRING`) from a given source vertex to all other vertices in the graph.

Returns a result size of V, the number of vertices in the graph.

### Time complexity

For a graph with positive weight edges, the time complexity is approximately O(V+E), where V is equal to the number of vertices and E is equal to the number of edges.

For a graph with positive and negative weight edges, the time complexity is O(V*E).

## Example

The graph below has only positive edge weights. Using vertex A as the source vertex, the algorithm discovers that the shortest weighted path from A to B is A-D-B, with distance 8. The shortest weighted path from A to C is A-D-B-C with distance 9.

``````[
{
"ResultSet": [
{
"v_id": "B",
"v_type": "Node",
"attributes": {
"ResultSet.@dis": 8,
"ResultSet.@path": [
"D",
"B"
]
}
},
{
"v_id": "A",
"v_type": "Node",
"attributes": {
"ResultSet.@dis": 0,
"ResultSet.@path": []
}
},
{
"v_id": "C",
"v_type": "Node",
"attributes": {
"ResultSet.@dis": 9,
"ResultSet.@path": [
"D",
"B",
"C"
]
}
},
{
"v_id": "E",
"v_type": "Node",
"attributes": {
"ResultSet.@dis": 7,
"ResultSet.@path": [
"D",
"E"
]
}
},
{
"v_id": "D",
"v_type": "Node",
"attributes": {
"ResultSet.@dis": 5,
"ResultSet.@path": [
"D"
]
}
}
]
}
]``````

The graph below has both positive and negative edge weights. Using vertex A as the source vertex, the algorithm discovers that the shortest weighted path from A to E is A-D-C-B-E, with a cumulative score of 7 - 3 - 2 - 4 = -2.