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. Think of Six Degrees of Separation and Friend of a Friend. Unweighted Shortest Path answers the question "How are you two related?" The two entities do not have to be persons. Shortest Path is useful in a host of applications, from estimating influences or knowledge transfer, to criminal investigation.
When the graph is unweighted, we can use a "greedy" approach to find the shortest path. In computer science, a greedy algorithm makes intermediate choices based on the data being considered at the moment, and then does not revisit those choices later on. In this case, once the algorithm finds any path to a vertex T, it is certain that that is a shortest path.
This algorithm finds an unweighted shortest path from one source vertex to each possible destination vertex in the graph. That is, it finds n paths.
If your graph has weighted edges, see the next algorithm. With weighted edges, it is necessary to search the whole graph, whether you want the path for just one destination or for all destinations.
In the below graph, we do not consider the weight on edges. Using vertex A as the source vertex, the algorithm discovers that the shortest path from A to B is A-B, and the shortest path from A to C is A-D-C, etc.
Characteristic
Value
Result
Computes a shortest distance (INT) and shortest path (STRING) from vertex source to each other vertex.
Input Parameters
VERTEX source
: ID of the source vertex
SET<STRING> v_type
: Names of vertex types to use
SET<STRING> e_type
: Names of edge types to use
INT output_limit
: If >=0, max number of vertices to output to JSON.
BOOL print_accum
: If True, output JSON to standard output
STRING result_attr
: If not empty, store distance values (INT) to this attribute
STRING file_path
: If not empty, write output to this file.
BOOL display_edges
: If true, include the graph's edges in the JSON output,
so that the full graph can be displayed.
Result Size
V = number of vertices
Time Complexity
O(E), E = number of edges
Graph Types
Directed or Undirected edges, Unweighted edges