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 from root to node j.

    • Otherwise, it is a tensor of shape \((N, N)\). dist[i][j] gives the shortest distance from node i to node j.

    • 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 node root to node j.

    • Otherwise, it is a tensor of shape \((N, N, L)\). path[i][j] is the shortest path from node i to node j.

    • 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]]])