Function _bellman_ford_step

python/pathway/stdlib/graphs/bellman_ford/impl.py:26–37

(
    vertices_dist: pw.Table[DistFromSource], edges: pw.Table[Edge | Dist]
)

def _bellman_ford_step(
    vertices_dist: pw.Table[DistFromSource], edges: pw.Table[Edge | Dist]
) -> pw.Table[DistFromSource]:
    relaxed_edges = edges + edges.select(
        dist_from_source=vertices_dist.ix(edges.u).dist_from_source + edges.dist
    )
    vertices_dist = vertices_dist.update_rows(
        relaxed_edges.groupby(id=relaxed_edges.v).reduce(
            dist_from_source=pw.reducers.min(relaxed_edges.dist_from_source),
        )
    )
    return vertices_dist


@check_arg_types