dgl.shortest_dist

dgl.shortest_dist(g, root=None, return_paths=False)[source]

计算给定图上的最短距离和路径。

仅支持无权图。仅考虑有效的有向路径（其中边的方向一致）。

参数：

g (DGLGraph) – 输入图。必须是同质图。
root (int, 可选) – 给定一个根节点 ID，它返回根节点与所有节点之间的最短距离和路径（可选）。如果为 None，则返回所有节点对的结果。默认值：None。
return_paths (bool, 可选) – 如果为 True，则返回与最短距离对应的最短路径。默认值：False。

返回值：

dist (Tensor) – 最短距离张量。
- 如果 root 是一个节点 ID，则它是一个形状为 \((N,)\) 的张量，其中 \(N\) 是节点数量。dist[j] 表示从 root 到节点 j 的最短距离。
- 否则，它是一个形状为 \((N, N)\) 的张量。dist[i][j] 表示从节点 i 到节点 j 的最短距离。
- 不可达节点对的距离值用 -1 填充。
paths (Tensor, 可选) – 最短路径张量。仅当 return_paths 为 True 时返回。
- 如果 root 是一个节点 ID，则它是一个形状为 \((N, L)\) 的张量，其中 \(L\) 是最长路径的长度。path[j] 是从节点 root 到节点 j 的最短路径。
- 否则，它是一个形状为 \((N, N, L)\) 的张量。path[i][j] 是从节点 i 到节点 j 的最短路径。
- 每条路径都是一个由边 ID 组成的向量，末尾用 -1 填充。
- 节点到其自身的最短路径是一个填充了 -1 的向量。

示例

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