# Single-source Shortest Path (Unweighted)

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

Unweighted Shortest Path answers a question posed to one vertex about its relationship with every other vertex in the graph: "How closely are you two related?" This is useful in a host of applications, from estimating influences or knowledge transfer, to criminal investigation.

This algorithm finds an unweighted shortest path from one source vertex to each possible destination vertex in the graph. It finds n paths, where n is the number of vertices.

If a graph has unweighted edges, then finding the shortest path from one vertex to another is the same as finding the path with the fewest hops.

When the graph is unweighted, we can use a "greedy" approach to find the shortest path. In computer science, a greedy algorithm does not re-evaluate choices with further iterations of itself. In this algorithm, the first path found to another vertex is considered to be the shortest path.

## Notes

On a graph with weighted edges, use Single-source Shortest Path (Weighted). With weighted edges, the algorithm must search the whole graph, whether you want the path for just one destination or for all destinations.

## Specifications

``````CREATE QUERY tg_shortest_ss_no_wt (VERTEX source,  SET<STRING> v_type_set,
SET<STRING> e_type_set, 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")`

N/A

`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

`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 `INT` and shortest path `STRING` from the given source to every other vertex.

Optionally, writes the distance value from the source to each target vertex on a specified INT attribute.

### Time complexity

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

### Space complexity

This algorithm has a space complexity of O(V logV), where V is equal to the number of vertices.

## Example

Consider the following unweighted graph with vertices A, B, C, D, and E. Using vertex A as the source vertex, the algorithm discovers that the shortest path from A to B is A → B, a path with a distance of 1.

The shortest path from A to C is A → D → C, with a distance of 2.

The returned JSON output lists, for each vertex on the graph in random order:

• The vertex ID

• The vertex Type

• A set of two distance attributes:

• The distance from the source vertex A

• The path from the source vertex A

``````[
{
"ResultSet": [
{
"v_id": "B",
"v_type": "Node",
"attributes": {
"ResultSet.@dis": 1,
"ResultSet.@path": [
"A",
"B"
]
}
},
{
"v_id": "A",
"v_type": "Node",
"attributes": {
"ResultSet.@dis": 0,
"ResultSet.@path": [
"A"
]
}
},
{
"v_id": "C",
"v_type": "Node",
"attributes": {
"ResultSet.@dis": 2,
"ResultSet.@path": [
"A",
"D",
"C"
]
}
},
{
"v_id": "E",
"v_type": "Node",
"attributes": {
"ResultSet.@dis": 2,
"ResultSet.@path": [
"A",
"D",
"E"
]
}
},
{
"v_id": "D",
"v_type": "Node",
"attributes": {
"ResultSet.@dis": 1,
"ResultSet.@path": [
"A",
"D"
]
}
}
]
}
]``````