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 a 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

The `shortest_path_any_wt` algorithm in this library is an implementation of the Bellman-Ford algorithm. If there is more than one path with the same total weight, the algorithm returns one of them.

Currently, `shortest_path_pos_wt` also uses Bellman-Ford. The well-known Dijsktra’s algorithm is designed for serial computation and cannot work with GSQL’s parallel processing.

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

This algorithm has a time complexity of O(V*E), where V is equal to the number of vertices and E is equal to the number of edges.

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.