---
title: "Single-source Shortest Path (Weighted)"
component: "graph-ml"
version: "3.10"
module: "pathfinding-algorithms"
html_url: "/graph-ml/3.10/pathfinding-algorithms/single-source-shortest-path-weighted"
canonical_url: "https://www.tigergraph.com/docs/graph-ml/3.10/pathfinding-algorithms/single-source-shortest-path-weighted"
markdown_url: "https://www.tigergraph.com/docs/graph-ml/3.10/pathfinding-algorithms/single-source-shortest-path-weighted.md"
---

[View as HTML](https://www.tigergraph.com/docs/graph-ml/3.10/pathfinding-algorithms/single-source-shortest-path-weighted)

# Single-source Shortest Path (Weighted)

Supported Graph Characteristics

| Weighted edges |
| --- |
| Directed edges |
| Undirected edges |
| Homogeneous vertex types |
| Heterogeneous vertex types |

Algorithm link: [Single-source Shortest Path (Weighted)](https://github.com/tigergraph/gsql-graph-algorithms/tree/master/algorithms/Path/shortest%5Fpath/weighted)

> [!NOTE]
> Updated 15 Oct 2024 to document the overlooked `epsilon` parameter.

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. Each round, the algorithm tries to find a shorter path to each destination.`epsilon` (aka `delta`) is the minimum path reduction the algorithm must find in a round in order to justify searching for another round. The well-known Dijsktra's algorithm is not well-suited 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

```gsql
tg_shortest_ss_pos_wt (VERTEX source,  SET<STRING> v_type_set,  SET<STRING> e_type_set,
 STRING weight_attribute, STRING weight_type, FLOAT epsilon = 0.001,
INT print_limit = -1, BOOL print_results = TRUE,
 STRING result_attribute = "", STRING file_path = "", BOOL display_edges = FALSE)
```

```gsql
tg_shortest_ss_any_wt (VERTEX source,  SET<STRING> v_type_set,  SET<STRING> e_type_set,
 STRING weight_attribute, STRING weight_type, INT print_limit = -1, BOOL print_results = TRUE,
 STRING result_attribute = "", STRING file_path = "", BOOL display_edges = FALSE)
```

### Parameters

| **Parameter** | Description | Default |
| --- | --- | --- |
| `VERTEX source` | The source vertex to start from. Provide the vertex ID and type as a tuple: `("id","type")` | (empty string) |
| `SET<STRING> v_type_set` | Names of vertex types to use | (empty string) |
| `SET<STRING> e_type_set` | Names of edge types to use | N/A |
| `STRING weight_attribute` | Name of the edge weight attribute | (empty string) |
| `STRING weight_type` | The data type of the edge weight attribute. Can be `INT`, `FLOAT`, or `DOUBLE`. | (empty string) |
| `FLOAT epsilon` | Minimum delta weight. | 0.001 |
| `INT print_limit` | If >=0, max number of vertices to output to JSON | \-1 |
| `BOOL print_results` | Whether to print results in JSON format to standard output | True |
| `STRING result_attribute` | 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.

![Generic graph with only positive weights](https://www.tigergraph.com/docs/graph-ml/3.10/pathfinding-algorithms/_images/screen-shot-2019-01-09-at-6.01.28-pm.png) 

```text
[
  {
    "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.

![Example results on a graph with negative weights on edges](https://www.tigergraph.com/docs/graph-ml/3.10/pathfinding-algorithms/_images/shortest_neg_result.png)
