Single-source Shortest Path (Unweighted)
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 |
---|---|---|
|
The source vertex to start from. Provide the vertex ID and type as a tuple: |
N/A |
|
Names of vertex types to use |
(empty string) |
|
Names of edge types to use |
N/A |
|
If >=0, max number of vertices to output to JSON |
-1 |
|
Whether to print results in JSON format to standard output |
True |
|
If not empty, store distance values in INT to this vertex attribute |
(empty string) |
|
If not empty, write output to this file. |
(empty string) |
|
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.
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"
]
}
}
]
}
]