turicreate.shortest_path.create

turicreate.shortest_path.create(graph, source_vid, weight_field='', max_distance=1e+30, verbose=True)

Compute the single source shortest path distance from the source vertex to all vertices in the graph. Note that because SGraph is directed, shortest paths are also directed. To find undirected shortest paths add edges to the SGraph in both directions. Return a model object with distance each of vertex in the graph.

Parameters:
graph : SGraph

The graph on which to compute shortest paths.

source_vid : vertex ID

ID of the source vertex.

weight_field : string, optional

The edge field representing the edge weights. If empty, uses unit weights.

verbose : bool, optional

If True, print progress updates.
Returns:
out : ShortestPathModel

See also

ShortestPathModel

References

Examples

If given an SGraph g, we can create a ShortestPathModel as follows:

>>> g = turicreate.load_sgraph('http://snap.stanford.edu/data/email-Enron.txt.gz', format='snap')
>>> sp = turicreate.shortest_path.create(g, source_vid=1)

We can obtain the shortest path distance from the source vertex to each vertex in the graph g as follows:

>>> sp_sframe = sp['distance']   # SFrame

We can add the new distance field to the original graph g using:

>>> g.vertices['distance_to_1'] = sp['graph'].vertices['distance']

Note that the task above does not require a join because the vertex ordering is preserved through create().

To get the actual path from the source vertex to any destination vertex:

>>> path = sp.get_path(vid=10)

We can obtain an auxiliary graph with additional information corresponding to the shortest path from the source vertex to each vertex in the graph g as follows:

>>> sp_graph = sp.get.graph      # SGraph