Single-source Shortest Path (Unweighted)

Supported Graph Characteristics

Directed edges

Undirected edges

Homogeneous vertex types

Heterogeneous vertex types

Algorithm link: 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<STRING> e_type, INT output_limit = -1, BOOL print_accum =TRUE,
  STRING result_attr ="", STRING file_path ="", BOOL display_edges =FALSE)

Parameters

Parameter Description Default

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

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

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 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"
          ]
        }
      }
    ]
  }
]