dgl.shortest_dist¶

dgl.
shortest_dist
(g, root=None, return_paths=False)[source]¶ Compute shortest distance and paths on the given graph.
Only unweighted cases are supported. Only directed paths (in which the edges are all oriented in the same direction) are considered effective.
 Parameters
g (DGLGraph) – The input graph. Must be homogeneous.
root (int, optional) – Given a root node ID, it returns the shortest distance and paths (optional) between the root node and all the nodes. If None, it returns the results for all node pairs. Default: None.
return_paths (bool, optional) – If True, it returns the shortest paths corresponding to the shortest distances. Default: False.
 Returns
dist (Tensor) – The shortest distance tensor.
If
root
is a node ID, it is a tensor of shape \((N,)\), where \(N\) is the number of nodes.dist[j]
gives the shortest distance fromroot
to nodej
.Otherwise, it is a tensor of shape \((N, N)\).
dist[i][j]
gives the shortest distance from nodei
to nodej
.The distance values of unreachable node pairs are filled with 1.
paths (Tensor, optional) – The shortest path tensor. It is only returned when
return_paths
is True.If
root
is a node ID, it is a tensor of shape \((N, L)\), where \(L\) is the length of the longest path.path[j]
is the shortest path from noderoot
to nodej
.Otherwise, it is a tensor of shape \((N, N, L)\).
path[i][j]
is the shortest path from nodei
to nodej
.Each path is a vector that consists of edge IDs with paddings of 1 at the end.
Shortest path between a node and itself is a vector filled with 1’s.
Example
>>> import dgl
>>> g = dgl.graph(([0, 1, 1, 2], [2, 0, 3, 3])) >>> dgl.shortest_dist(g, root=0) tensor([ 0, 1, 1, 2]) >>> dist, paths = dgl.shortest_dist(g, root=None, return_paths=True) >>> print(dist) tensor([[ 0, 1, 1, 2], [ 1, 0, 2, 1], [1, 1, 0, 1], [1, 1, 1, 0]]) >>> print(paths) tensor([[[1, 1], [1, 1], [ 0, 1], [ 0, 3]], [[ 1, 1], [1, 1], [ 1, 0], [ 2, 1]], [[1, 1], [1, 1], [1, 1], [ 3, 1]], [[1, 1], [1, 1], [1, 1], [1, 1]]])