two version of R2R are hereHEADmaster

13 files changed, 6455 insertions, 0 deletions

diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/shortest_paths/__init__.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/shortest_paths/__init__.py
new file mode 100644
index 00000000..eb0d91ce
--- /dev/null
+++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/shortest_paths/__init__.py
@@ -0,0 +1,5 @@
+from networkx.algorithms.shortest_paths.generic import *
+from networkx.algorithms.shortest_paths.unweighted import *
+from networkx.algorithms.shortest_paths.weighted import *
+from networkx.algorithms.shortest_paths.astar import *
+from networkx.algorithms.shortest_paths.dense import *
diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/shortest_paths/astar.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/shortest_paths/astar.py
new file mode 100644
index 00000000..8d988477
--- /dev/null
+++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/shortest_paths/astar.py
@@ -0,0 +1,241 @@
+"""Shortest paths and path lengths using the A* ("A star") algorithm."""
+
+from heapq import heappop, heappush
+from itertools import count
+
+import networkx as nx
+from networkx.algorithms.shortest_paths.weighted import _weight_function
+
+__all__ = ["astar_path", "astar_path_length"]
+
+
+@nx._dispatchable(edge_attrs="weight", preserve_node_attrs="heuristic")
+def astar_path(G, source, target, heuristic=None, weight="weight", *, cutoff=None):
+    """Returns a list of nodes in a shortest path between source and target
+    using the A* ("A-star") algorithm.
+
+    There may be more than one shortest path.  This returns only one.
+
+    Parameters
+    ----------
+    G : NetworkX graph
+
+    source : node
+       Starting node for path
+
+    target : node
+       Ending node for path
+
+    heuristic : function
+       A function to evaluate the estimate of the distance
+       from the a node to the target.  The function takes
+       two nodes arguments and must return a number.
+       If the heuristic is inadmissible (if it might
+       overestimate the cost of reaching the goal from a node),
+       the result may not be a shortest path.
+       The algorithm does not support updating heuristic
+       values for the same node due to caching the first
+       heuristic calculation per node.
+
+    weight : string or function
+       If this is a string, then edge weights will be accessed via the
+       edge attribute with this key (that is, the weight of the edge
+       joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
+       such edge attribute exists, the weight of the edge is assumed to
+       be one.
+       If this is a function, the weight of an edge is the value
+       returned by the function. The function must accept exactly three
+       positional arguments: the two endpoints of an edge and the
+       dictionary of edge attributes for that edge. The function must
+       return a number or None to indicate a hidden edge.
+
+    cutoff : float, optional
+       If this is provided, the search will be bounded to this value. I.e. if
+       the evaluation function surpasses this value for a node n, the node will not
+       be expanded further and will be ignored. More formally, let h'(n) be the
+       heuristic function, and g(n) be the cost of reaching n from the source node. Then,
+       if g(n) + h'(n) > cutoff, the node will not be explored further.
+       Note that if the heuristic is inadmissible, it is possible that paths
+       are ignored even though they satisfy the cutoff.
+
+    Raises
+    ------
+    NetworkXNoPath
+        If no path exists between source and target.
+
+    Examples
+    --------
+    >>> G = nx.path_graph(5)
+    >>> print(nx.astar_path(G, 0, 4))
+    [0, 1, 2, 3, 4]
+    >>> G = nx.grid_graph(dim=[3, 3])  # nodes are two-tuples (x,y)
+    >>> nx.set_edge_attributes(G, {e: e[1][0] * 2 for e in G.edges()}, "cost")
+    >>> def dist(a, b):
+    ...     (x1, y1) = a
+    ...     (x2, y2) = b
+    ...     return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5
+    >>> print(nx.astar_path(G, (0, 0), (2, 2), heuristic=dist, weight="cost"))
+    [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2)]
+
+    Notes
+    -----
+    Edge weight attributes must be numerical.
+    Distances are calculated as sums of weighted edges traversed.
+
+    The weight function can be used to hide edges by returning None.
+    So ``weight = lambda u, v, d: 1 if d['color']=="red" else None``
+    will find the shortest red path.
+
+    See Also
+    --------
+    shortest_path, dijkstra_path
+
+    """
+    if source not in G:
+        raise nx.NodeNotFound(f"Source {source} is not in G")
+
+    if target not in G:
+        raise nx.NodeNotFound(f"Target {target} is not in G")
+
+    if heuristic is None:
+        # The default heuristic is h=0 - same as Dijkstra's algorithm
+        def heuristic(u, v):
+            return 0
+
+    push = heappush
+    pop = heappop
+    weight = _weight_function(G, weight)
+
+    G_succ = G._adj  # For speed-up (and works for both directed and undirected graphs)
+
+    # The queue stores priority, node, cost to reach, and parent.
+    # Uses Python heapq to keep in priority order.
+    # Add a counter to the queue to prevent the underlying heap from
+    # attempting to compare the nodes themselves. The hash breaks ties in the
+    # priority and is guaranteed unique for all nodes in the graph.
+    c = count()
+    queue = [(0, next(c), source, 0, None)]
+
+    # Maps enqueued nodes to distance of discovered paths and the
+    # computed heuristics to target. We avoid computing the heuristics
+    # more than once and inserting the node into the queue too many times.
+    enqueued = {}
+    # Maps explored nodes to parent closest to the source.
+    explored = {}
+
+    while queue:
+        # Pop the smallest item from queue.
+        _, __, curnode, dist, parent = pop(queue)
+
+        if curnode == target:
+            path = [curnode]
+            node = parent
+            while node is not None:
+                path.append(node)
+                node = explored[node]
+            path.reverse()
+            return path
+
+        if curnode in explored:
+            # Do not override the parent of starting node
+            if explored[curnode] is None:
+                continue
+
+            # Skip bad paths that were enqueued before finding a better one
+            qcost, h = enqueued[curnode]
+            if qcost < dist:
+                continue
+
+        explored[curnode] = parent
+
+        for neighbor, w in G_succ[curnode].items():
+            cost = weight(curnode, neighbor, w)
+            if cost is None:
+                continue
+            ncost = dist + cost
+            if neighbor in enqueued:
+                qcost, h = enqueued[neighbor]
+                # if qcost <= ncost, a less costly path from the
+                # neighbor to the source was already determined.
+                # Therefore, we won't attempt to push this neighbor
+                # to the queue
+                if qcost <= ncost:
+                    continue
+            else:
+                h = heuristic(neighbor, target)
+
+            if cutoff and ncost + h > cutoff:
+                continue
+
+            enqueued[neighbor] = ncost, h
+            push(queue, (ncost + h, next(c), neighbor, ncost, curnode))
+
+    raise nx.NetworkXNoPath(f"Node {target} not reachable from {source}")
+
+
+@nx._dispatchable(edge_attrs="weight", preserve_node_attrs="heuristic")
+def astar_path_length(
+    G, source, target, heuristic=None, weight="weight", *, cutoff=None
+):
+    """Returns the length of the shortest path between source and target using
+    the A* ("A-star") algorithm.
+
+    Parameters
+    ----------
+    G : NetworkX graph
+
+    source : node
+       Starting node for path
+
+    target : node
+       Ending node for path
+
+    heuristic : function
+       A function to evaluate the estimate of the distance
+       from the a node to the target.  The function takes
+       two nodes arguments and must return a number.
+       If the heuristic is inadmissible (if it might
+       overestimate the cost of reaching the goal from a node),
+       the result may not be a shortest path.
+       The algorithm does not support updating heuristic
+       values for the same node due to caching the first
+       heuristic calculation per node.
+
+    weight : string or function
+       If this is a string, then edge weights will be accessed via the
+       edge attribute with this key (that is, the weight of the edge
+       joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
+       such edge attribute exists, the weight of the edge is assumed to
+       be one.
+       If this is a function, the weight of an edge is the value
+       returned by the function. The function must accept exactly three
+       positional arguments: the two endpoints of an edge and the
+       dictionary of edge attributes for that edge. The function must
+       return a number or None to indicate a hidden edge.
+
+    cutoff : float, optional
+       If this is provided, the search will be bounded to this value. I.e. if
+       the evaluation function surpasses this value for a node n, the node will not
+       be expanded further and will be ignored. More formally, let h'(n) be the
+       heuristic function, and g(n) be the cost of reaching n from the source node. Then,
+       if g(n) + h'(n) > cutoff, the node will not be explored further.
+       Note that if the heuristic is inadmissible, it is possible that paths
+       are ignored even though they satisfy the cutoff.
+
+    Raises
+    ------
+    NetworkXNoPath
+        If no path exists between source and target.
+
+    See Also
+    --------
+    astar_path
+
+    """
+    if source not in G or target not in G:
+        msg = f"Either source {source} or target {target} is not in G"
+        raise nx.NodeNotFound(msg)
+
+    weight = _weight_function(G, weight)
+    path = astar_path(G, source, target, heuristic, weight, cutoff=cutoff)
+    return sum(weight(u, v, G[u][v]) for u, v in zip(path[:-1], path[1:]))
diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/shortest_paths/dense.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/shortest_paths/dense.py
new file mode 100644
index 00000000..107b9208
--- /dev/null
+++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/shortest_paths/dense.py
@@ -0,0 +1,260 @@
+"""Floyd-Warshall algorithm for shortest paths."""
+
+import networkx as nx
+
+__all__ = [
+    "floyd_warshall",
+    "floyd_warshall_predecessor_and_distance",
+    "reconstruct_path",
+    "floyd_warshall_numpy",
+]
+
+
+@nx._dispatchable(edge_attrs="weight")
+def floyd_warshall_numpy(G, nodelist=None, weight="weight"):
+    """Find all-pairs shortest path lengths using Floyd's algorithm.
+
+    This algorithm for finding shortest paths takes advantage of
+    matrix representations of a graph and works well for dense
+    graphs where all-pairs shortest path lengths are desired.
+    The results are returned as a NumPy array, distance[i, j],
+    where i and j are the indexes of two nodes in nodelist.
+    The entry distance[i, j] is the distance along a shortest
+    path from i to j. If no path exists the distance is Inf.
+
+    Parameters
+    ----------
+    G : NetworkX graph
+
+    nodelist : list, optional (default=G.nodes)
+       The rows and columns are ordered by the nodes in nodelist.
+       If nodelist is None then the ordering is produced by G.nodes.
+       Nodelist should include all nodes in G.
+
+    weight: string, optional (default='weight')
+       Edge data key corresponding to the edge weight.
+
+    Returns
+    -------
+    distance : 2D numpy.ndarray
+        A numpy array of shortest path distances between nodes.
+        If there is no path between two nodes the value is Inf.
+
+    Examples
+    --------
+    >>> G = nx.DiGraph()
+    >>> G.add_weighted_edges_from(
+    ...     [(0, 1, 5), (1, 2, 2), (2, 3, -3), (1, 3, 10), (3, 2, 8)]
+    ... )
+    >>> nx.floyd_warshall_numpy(G)
+    array([[ 0.,  5.,  7.,  4.],
+           [inf,  0.,  2., -1.],
+           [inf, inf,  0., -3.],
+           [inf, inf,  8.,  0.]])
+
+    Notes
+    -----
+    Floyd's algorithm is appropriate for finding shortest paths in
+    dense graphs or graphs with negative weights when Dijkstra's
+    algorithm fails. This algorithm can still fail if there are negative
+    cycles. It has running time $O(n^3)$ with running space of $O(n^2)$.
+
+    Raises
+    ------
+    NetworkXError
+        If nodelist is not a list of the nodes in G.
+    """
+    import numpy as np
+
+    if nodelist is not None:
+        if not (len(nodelist) == len(G) == len(set(nodelist))):
+            raise nx.NetworkXError(
+                "nodelist must contain every node in G with no repeats."
+                "If you wanted a subgraph of G use G.subgraph(nodelist)"
+            )
+
+    # To handle cases when an edge has weight=0, we must make sure that
+    # nonedges are not given the value 0 as well.
+    A = nx.to_numpy_array(
+        G, nodelist, multigraph_weight=min, weight=weight, nonedge=np.inf
+    )
+    n, m = A.shape
+    np.fill_diagonal(A, 0)  # diagonal elements should be zero
+    for i in range(n):
+        # The second term has the same shape as A due to broadcasting
+        A = np.minimum(A, A[i, :][np.newaxis, :] + A[:, i][:, np.newaxis])
+    return A
+
+
+@nx._dispatchable(edge_attrs="weight")
+def floyd_warshall_predecessor_and_distance(G, weight="weight"):
+    """Find all-pairs shortest path lengths using Floyd's algorithm.
+
+    Parameters
+    ----------
+    G : NetworkX graph
+
+    weight: string, optional (default= 'weight')
+       Edge data key corresponding to the edge weight.
+
+    Returns
+    -------
+    predecessor,distance : dictionaries
+       Dictionaries, keyed by source and target, of predecessors and distances
+       in the shortest path.
+
+    Examples
+    --------
+    >>> G = nx.DiGraph()
+    >>> G.add_weighted_edges_from(
+    ...     [
+    ...         ("s", "u", 10),
+    ...         ("s", "x", 5),
+    ...         ("u", "v", 1),
+    ...         ("u", "x", 2),
+    ...         ("v", "y", 1),
+    ...         ("x", "u", 3),
+    ...         ("x", "v", 5),
+    ...         ("x", "y", 2),
+    ...         ("y", "s", 7),
+    ...         ("y", "v", 6),
+    ...     ]
+    ... )
+    >>> predecessors, _ = nx.floyd_warshall_predecessor_and_distance(G)
+    >>> print(nx.reconstruct_path("s", "v", predecessors))
+    ['s', 'x', 'u', 'v']
+
+    Notes
+    -----
+    Floyd's algorithm is appropriate for finding shortest paths
+    in dense graphs or graphs with negative weights when Dijkstra's algorithm
+    fails.  This algorithm can still fail if there are negative cycles.
+    It has running time $O(n^3)$ with running space of $O(n^2)$.
+
+    See Also
+    --------
+    floyd_warshall
+    floyd_warshall_numpy
+    all_pairs_shortest_path
+    all_pairs_shortest_path_length
+    """
+    from collections import defaultdict
+
+    # dictionary-of-dictionaries representation for dist and pred
+    # use some defaultdict magick here
+    # for dist the default is the floating point inf value
+    dist = defaultdict(lambda: defaultdict(lambda: float("inf")))
+    for u in G:
+        dist[u][u] = 0
+    pred = defaultdict(dict)
+    # initialize path distance dictionary to be the adjacency matrix
+    # also set the distance to self to 0 (zero diagonal)
+    undirected = not G.is_directed()
+    for u, v, d in G.edges(data=True):
+        e_weight = d.get(weight, 1.0)
+        dist[u][v] = min(e_weight, dist[u][v])
+        pred[u][v] = u
+        if undirected:
+            dist[v][u] = min(e_weight, dist[v][u])
+            pred[v][u] = v
+    for w in G:
+        dist_w = dist[w]  # save recomputation
+        for u in G:
+            dist_u = dist[u]  # save recomputation
+            for v in G:
+                d = dist_u[w] + dist_w[v]
+                if dist_u[v] > d:
+                    dist_u[v] = d
+                    pred[u][v] = pred[w][v]
+    return dict(pred), dict(dist)
+
+
+@nx._dispatchable(graphs=None)
+def reconstruct_path(source, target, predecessors):
+    """Reconstruct a path from source to target using the predecessors
+    dict as returned by floyd_warshall_predecessor_and_distance
+
+    Parameters
+    ----------
+    source : node
+       Starting node for path
+
+    target : node
+       Ending node for path
+
+    predecessors: dictionary
+       Dictionary, keyed by source and target, of predecessors in the
+       shortest path, as returned by floyd_warshall_predecessor_and_distance
+
+    Returns
+    -------
+    path : list
+       A list of nodes containing the shortest path from source to target
+
+       If source and target are the same, an empty list is returned
+
+    Notes
+    -----
+    This function is meant to give more applicability to the
+    floyd_warshall_predecessor_and_distance function
+
+    See Also
+    --------
+    floyd_warshall_predecessor_and_distance
+    """
+    if source == target:
+        return []
+    prev = predecessors[source]
+    curr = prev[target]
+    path = [target, curr]
+    while curr != source:
+        curr = prev[curr]
+        path.append(curr)
+    return list(reversed(path))
+
+
+@nx._dispatchable(edge_attrs="weight")
+def floyd_warshall(G, weight="weight"):
+    """Find all-pairs shortest path lengths using Floyd's algorithm.
+
+    Parameters
+    ----------
+    G : NetworkX graph
+
+    weight: string, optional (default= 'weight')
+       Edge data key corresponding to the edge weight.
+
+
+    Returns
+    -------
+    distance : dict
+       A dictionary,  keyed by source and target, of shortest paths distances
+       between nodes.
+
+    Examples
+    --------
+    >>> G = nx.DiGraph()
+    >>> G.add_weighted_edges_from(
+    ...     [(0, 1, 5), (1, 2, 2), (2, 3, -3), (1, 3, 10), (3, 2, 8)]
+    ... )
+    >>> fw = nx.floyd_warshall(G, weight="weight")
+    >>> results = {a: dict(b) for a, b in fw.items()}
+    >>> print(results)
+    {0: {0: 0, 1: 5, 2: 7, 3: 4}, 1: {1: 0, 2: 2, 3: -1, 0: inf}, 2: {2: 0, 3: -3, 0: inf, 1: inf}, 3: {3: 0, 2: 8, 0: inf, 1: inf}}
+
+    Notes
+    -----
+    Floyd's algorithm is appropriate for finding shortest paths
+    in dense graphs or graphs with negative weights when Dijkstra's algorithm
+    fails.  This algorithm can still fail if there are negative cycles.
+    It has running time $O(n^3)$ with running space of $O(n^2)$.
+
+    See Also
+    --------
+    floyd_warshall_predecessor_and_distance
+    floyd_warshall_numpy
+    all_pairs_shortest_path
+    all_pairs_shortest_path_length
+    """
+    # could make this its own function to reduce memory costs
+    return floyd_warshall_predecessor_and_distance(G, weight=weight)[1]
diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/shortest_paths/generic.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/shortest_paths/generic.py
new file mode 100644
index 00000000..9ac48c90
--- /dev/null
+++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/shortest_paths/generic.py
@@ -0,0 +1,730 @@
+"""
+Compute the shortest paths and path lengths between nodes in the graph.
+
+These algorithms work with undirected and directed graphs.
+
+"""
+
+import warnings
+
+import networkx as nx
+
+__all__ = [
+    "shortest_path",
+    "all_shortest_paths",
+    "single_source_all_shortest_paths",
+    "all_pairs_all_shortest_paths",
+    "shortest_path_length",
+    "average_shortest_path_length",
+    "has_path",
+]
+
+
+@nx._dispatchable
+def has_path(G, source, target):
+    """Returns *True* if *G* has a path from *source* to *target*.
+
+    Parameters
+    ----------
+    G : NetworkX graph
+
+    source : node
+       Starting node for path
+
+    target : node
+       Ending node for path
+    """
+    try:
+        nx.shortest_path(G, source, target)
+    except nx.NetworkXNoPath:
+        return False
+    return True
+
+
+@nx._dispatchable(edge_attrs="weight")
+def shortest_path(G, source=None, target=None, weight=None, method="dijkstra"):
+    """Compute shortest paths in the graph.
+
+    Parameters
+    ----------
+    G : NetworkX graph
+
+    source : node, optional
+        Starting node for path. If not specified, compute shortest
+        paths for each possible starting node.
+
+    target : node, optional
+        Ending node for path. If not specified, compute shortest
+        paths to all possible nodes.
+
+    weight : None, string or function, optional (default = None)
+        If None, every edge has weight/distance/cost 1.
+        If a string, use this edge attribute as the edge weight.
+        Any edge attribute not present defaults to 1.
+        If this is a function, the weight of an edge is the value
+        returned by the function. The function must accept exactly
+        three positional arguments: the two endpoints of an edge and
+        the dictionary of edge attributes for that edge.
+        The function must return a number.
+
+    method : string, optional (default = 'dijkstra')
+        The algorithm to use to compute the path.
+        Supported options: 'dijkstra', 'bellman-ford'.
+        Other inputs produce a ValueError.
+        If `weight` is None, unweighted graph methods are used, and this
+        suggestion is ignored.
+
+    Returns
+    -------
+    path: list or dictionary
+        All returned paths include both the source and target in the path.
+
+        If the source and target are both specified, return a single list
+        of nodes in a shortest path from the source to the target.
+
+        If only the source is specified, return a dictionary keyed by
+        targets with a list of nodes in a shortest path from the source
+        to one of the targets.
+
+        If only the target is specified, return a dictionary keyed by
+        sources with a list of nodes in a shortest path from one of the
+        sources to the target.
+
+        If neither the source nor target are specified return a dictionary
+        of dictionaries with path[source][target]=[list of nodes in path].
+
+    Raises
+    ------
+    NodeNotFound
+        If `source` is not in `G`.
+
+    ValueError
+        If `method` is not among the supported options.
+
+    Examples
+    --------
+    >>> G = nx.path_graph(5)
+    >>> print(nx.shortest_path(G, source=0, target=4))
+    [0, 1, 2, 3, 4]
+    >>> p = nx.shortest_path(G, source=0)  # target not specified
+    >>> p[3]  # shortest path from source=0 to target=3
+    [0, 1, 2, 3]
+    >>> p = nx.shortest_path(G, target=4)  # source not specified
+    >>> p[1]  # shortest path from source=1 to target=4
+    [1, 2, 3, 4]
+    >>> p = dict(nx.shortest_path(G))  # source, target not specified
+    >>> p[2][4]  # shortest path from source=2 to target=4
+    [2, 3, 4]
+
+    Notes
+    -----
+    There may be more than one shortest path between a source and target.
+    This returns only one of them.
+
+    See Also
+    --------
+    all_pairs_shortest_path
+    all_pairs_dijkstra_path
+    all_pairs_bellman_ford_path
+    single_source_shortest_path
+    single_source_dijkstra_path
+    single_source_bellman_ford_path
+    """
+    if method not in ("dijkstra", "bellman-ford"):
+        # so we don't need to check in each branch later
+        raise ValueError(f"method not supported: {method}")
+    method = "unweighted" if weight is None else method
+    if source is None:
+        if target is None:
+            warnings.warn(
+                (
+                    "\n\nshortest_path will return an iterator that yields\n"
+                    "(node, path) pairs instead of a dictionary when source\n"
+                    "and target are unspecified beginning in version 3.5\n\n"
+                    "To keep the current behavior, use:\n\n"
+                    "\tdict(nx.shortest_path(G))"
+                ),
+                FutureWarning,
+                stacklevel=3,
+            )
+
+            # Find paths between all pairs.
+            if method == "unweighted":
+                paths = dict(nx.all_pairs_shortest_path(G))
+            elif method == "dijkstra":
+                paths = dict(nx.all_pairs_dijkstra_path(G, weight=weight))
+            else:  # method == 'bellman-ford':
+                paths = dict(nx.all_pairs_bellman_ford_path(G, weight=weight))
+        else:
+            # Find paths from all nodes co-accessible to the target.
+            if G.is_directed():
+                G = G.reverse(copy=False)
+            if method == "unweighted":
+                paths = nx.single_source_shortest_path(G, target)
+            elif method == "dijkstra":
+                paths = nx.single_source_dijkstra_path(G, target, weight=weight)
+            else:  # method == 'bellman-ford':
+                paths = nx.single_source_bellman_ford_path(G, target, weight=weight)
+            # Now flip the paths so they go from a source to the target.
+            for target in paths:
+                paths[target] = list(reversed(paths[target]))
+    else:
+        if target is None:
+            # Find paths to all nodes accessible from the source.
+            if method == "unweighted":
+                paths = nx.single_source_shortest_path(G, source)
+            elif method == "dijkstra":
+                paths = nx.single_source_dijkstra_path(G, source, weight=weight)
+            else:  # method == 'bellman-ford':
+                paths = nx.single_source_bellman_ford_path(G, source, weight=weight)
+        else:
+            # Find shortest source-target path.
+            if method == "unweighted":
+                paths = nx.bidirectional_shortest_path(G, source, target)
+            elif method == "dijkstra":
+                _, paths = nx.bidirectional_dijkstra(G, source, target, weight)
+            else:  # method == 'bellman-ford':
+                paths = nx.bellman_ford_path(G, source, target, weight)
+    return paths
+
+
+@nx._dispatchable(edge_attrs="weight")
+def shortest_path_length(G, source=None, target=None, weight=None, method="dijkstra"):
+    """Compute shortest path lengths in the graph.
+
+    Parameters
+    ----------
+    G : NetworkX graph
+
+    source : node, optional
+        Starting node for path.
+        If not specified, compute shortest path lengths using all nodes as
+        source nodes.
+
+    target : node, optional
+        Ending node for path.
+        If not specified, compute shortest path lengths using all nodes as
+        target nodes.
+
+    weight : None, string or function, optional (default = None)
+        If None, every edge has weight/distance/cost 1.
+        If a string, use this edge attribute as the edge weight.
+        Any edge attribute not present defaults to 1.
+        If this is a function, the weight of an edge is the value
+        returned by the function. The function must accept exactly
+        three positional arguments: the two endpoints of an edge and
+        the dictionary of edge attributes for that edge.
+        The function must return a number.
+
+    method : string, optional (default = 'dijkstra')
+        The algorithm to use to compute the path length.
+        Supported options: 'dijkstra', 'bellman-ford'.
+        Other inputs produce a ValueError.
+        If `weight` is None, unweighted graph methods are used, and this
+        suggestion is ignored.
+
+    Returns
+    -------
+    length: number or iterator
+        If the source and target are both specified, return the length of
+        the shortest path from the source to the target.
+
+        If only the source is specified, return a dict keyed by target
+        to the shortest path length from the source to that target.
+
+        If only the target is specified, return a dict keyed by source
+        to the shortest path length from that source to the target.
+
+        If neither the source nor target are specified, return an iterator
+        over (source, dictionary) where dictionary is keyed by target to
+        shortest path length from source to that target.
+
+    Raises
+    ------
+    NodeNotFound
+        If `source` is not in `G`.
+
+    NetworkXNoPath
+        If no path exists between source and target.
+
+    ValueError
+        If `method` is not among the supported options.
+
+    Examples
+    --------
+    >>> G = nx.path_graph(5)
+    >>> nx.shortest_path_length(G, source=0, target=4)
+    4
+    >>> p = nx.shortest_path_length(G, source=0)  # target not specified
+    >>> p[4]
+    4
+    >>> p = nx.shortest_path_length(G, target=4)  # source not specified
+    >>> p[0]
+    4
+    >>> p = dict(nx.shortest_path_length(G))  # source,target not specified
+    >>> p[0][4]
+    4
+
+    Notes
+    -----
+    The length of the path is always 1 less than the number of nodes involved
+    in the path since the length measures the number of edges followed.
+
+    For digraphs this returns the shortest directed path length. To find path
+    lengths in the reverse direction use G.reverse(copy=False) first to flip
+    the edge orientation.
+
+    See Also
+    --------
+    all_pairs_shortest_path_length
+    all_pairs_dijkstra_path_length
+    all_pairs_bellman_ford_path_length
+    single_source_shortest_path_length
+    single_source_dijkstra_path_length
+    single_source_bellman_ford_path_length
+    """
+    if method not in ("dijkstra", "bellman-ford"):
+        # so we don't need to check in each branch later
+        raise ValueError(f"method not supported: {method}")
+    method = "unweighted" if weight is None else method
+    if source is None:
+        if target is None:
+            # Find paths between all pairs.
+            if method == "unweighted":
+                paths = nx.all_pairs_shortest_path_length(G)
+            elif method == "dijkstra":
+                paths = nx.all_pairs_dijkstra_path_length(G, weight=weight)
+            else:  # method == 'bellman-ford':
+                paths = nx.all_pairs_bellman_ford_path_length(G, weight=weight)
+        else:
+            # Find paths from all nodes co-accessible to the target.
+            if G.is_directed():
+                G = G.reverse(copy=False)
+            if method == "unweighted":
+                path_length = nx.single_source_shortest_path_length
+                paths = path_length(G, target)
+            elif method == "dijkstra":
+                path_length = nx.single_source_dijkstra_path_length
+                paths = path_length(G, target, weight=weight)
+            else:  # method == 'bellman-ford':
+                path_length = nx.single_source_bellman_ford_path_length
+                paths = path_length(G, target, weight=weight)
+    else:
+        if target is None:
+            # Find paths to all nodes accessible from the source.
+            if method == "unweighted":
+                paths = nx.single_source_shortest_path_length(G, source)
+            elif method == "dijkstra":
+                path_length = nx.single_source_dijkstra_path_length
+                paths = path_length(G, source, weight=weight)
+            else:  # method == 'bellman-ford':
+                path_length = nx.single_source_bellman_ford_path_length
+                paths = path_length(G, source, weight=weight)
+        else:
+            # Find shortest source-target path.
+            if method == "unweighted":
+                p = nx.bidirectional_shortest_path(G, source, target)
+                paths = len(p) - 1
+            elif method == "dijkstra":
+                paths = nx.dijkstra_path_length(G, source, target, weight)
+            else:  # method == 'bellman-ford':
+                paths = nx.bellman_ford_path_length(G, source, target, weight)
+    return paths
+
+
+@nx._dispatchable(edge_attrs="weight")
+def average_shortest_path_length(G, weight=None, method=None):
+    r"""Returns the average shortest path length.
+
+    The average shortest path length is
+
+    .. math::
+
+       a =\sum_{\substack{s,t \in V \\ s\neq t}} \frac{d(s, t)}{n(n-1)}
+
+    where `V` is the set of nodes in `G`,
+    `d(s, t)` is the shortest path from `s` to `t`,
+    and `n` is the number of nodes in `G`.
+
+    .. versionchanged:: 3.0
+       An exception is raised for directed graphs that are not strongly
+       connected.
+
+    Parameters
+    ----------
+    G : NetworkX graph
+
+    weight : None, string or function, optional (default = None)
+        If None, every edge has weight/distance/cost 1.
+        If a string, use this edge attribute as the edge weight.
+        Any edge attribute not present defaults to 1.
+        If this is a function, the weight of an edge is the value
+        returned by the function. The function must accept exactly
+        three positional arguments: the two endpoints of an edge and
+        the dictionary of edge attributes for that edge.
+        The function must return a number.
+
+    method : string, optional (default = 'unweighted' or 'dijkstra')
+        The algorithm to use to compute the path lengths.
+        Supported options are 'unweighted', 'dijkstra', 'bellman-ford',
+        'floyd-warshall' and 'floyd-warshall-numpy'.
+        Other method values produce a ValueError.
+        The default method is 'unweighted' if `weight` is None,
+        otherwise the default method is 'dijkstra'.
+
+    Raises
+    ------
+    NetworkXPointlessConcept
+        If `G` is the null graph (that is, the graph on zero nodes).
+
+    NetworkXError
+        If `G` is not connected (or not strongly connected, in the case
+        of a directed graph).
+
+    ValueError
+        If `method` is not among the supported options.
+
+    Examples
+    --------
+    >>> G = nx.path_graph(5)
+    >>> nx.average_shortest_path_length(G)
+    2.0
+
+    For disconnected graphs, you can compute the average shortest path
+    length for each component
+
+    >>> G = nx.Graph([(1, 2), (3, 4)])
+    >>> for C in (G.subgraph(c).copy() for c in nx.connected_components(G)):
+    ...     print(nx.average_shortest_path_length(C))
+    1.0
+    1.0
+
+    """
+    single_source_methods = ["unweighted", "dijkstra", "bellman-ford"]
+    all_pairs_methods = ["floyd-warshall", "floyd-warshall-numpy"]
+    supported_methods = single_source_methods + all_pairs_methods
+
+    if method is None:
+        method = "unweighted" if weight is None else "dijkstra"
+    if method not in supported_methods:
+        raise ValueError(f"method not supported: {method}")
+
+    n = len(G)
+    # For the special case of the null graph, raise an exception, since
+    # there are no paths in the null graph.
+    if n == 0:
+        msg = (
+            "the null graph has no paths, thus there is no average "
+            "shortest path length"
+        )
+        raise nx.NetworkXPointlessConcept(msg)
+    # For the special case of the trivial graph, return zero immediately.
+    if n == 1:
+        return 0
+    # Shortest path length is undefined if the graph is not strongly connected.
+    if G.is_directed() and not nx.is_strongly_connected(G):
+        raise nx.NetworkXError("Graph is not strongly connected.")
+    # Shortest path length is undefined if the graph is not connected.
+    if not G.is_directed() and not nx.is_connected(G):
+        raise nx.NetworkXError("Graph is not connected.")
+
+    # Compute all-pairs shortest paths.
+    def path_length(v):
+        if method == "unweighted":
+            return nx.single_source_shortest_path_length(G, v)
+        elif method == "dijkstra":
+            return nx.single_source_dijkstra_path_length(G, v, weight=weight)
+        elif method == "bellman-ford":
+            return nx.single_source_bellman_ford_path_length(G, v, weight=weight)
+
+    if method in single_source_methods:
+        # Sum the distances for each (ordered) pair of source and target node.
+        s = sum(l for u in G for l in path_length(u).values())
+    else:
+        if method == "floyd-warshall":
+            all_pairs = nx.floyd_warshall(G, weight=weight)
+            s = sum(sum(t.values()) for t in all_pairs.values())
+        elif method == "floyd-warshall-numpy":
+            s = float(nx.floyd_warshall_numpy(G, weight=weight).sum())
+    return s / (n * (n - 1))
+
+
+@nx._dispatchable(edge_attrs="weight")
+def all_shortest_paths(G, source, target, weight=None, method="dijkstra"):
+    """Compute all shortest simple paths in the graph.
+
+    Parameters
+    ----------
+    G : NetworkX graph
+
+    source : node
+       Starting node for path.
+
+    target : node
+       Ending node for path.
+
+    weight : None, string or function, optional (default = None)
+        If None, every edge has weight/distance/cost 1.
+        If a string, use this edge attribute as the edge weight.
+        Any edge attribute not present defaults to 1.
+        If this is a function, the weight of an edge is the value
+        returned by the function. The function must accept exactly
+        three positional arguments: the two endpoints of an edge and
+        the dictionary of edge attributes for that edge.
+        The function must return a number.
+
+    method : string, optional (default = 'dijkstra')
+       The algorithm to use to compute the path lengths.
+       Supported options: 'dijkstra', 'bellman-ford'.
+       Other inputs produce a ValueError.
+       If `weight` is None, unweighted graph methods are used, and this
+       suggestion is ignored.
+
+    Returns
+    -------
+    paths : generator of lists
+        A generator of all paths between source and target.
+
+    Raises
+    ------
+    ValueError
+        If `method` is not among the supported options.
+
+    NetworkXNoPath
+        If `target` cannot be reached from `source`.
+
+    Examples
+    --------
+    >>> G = nx.Graph()
+    >>> nx.add_path(G, [0, 1, 2])
+    >>> nx.add_path(G, [0, 10, 2])
+    >>> print([p for p in nx.all_shortest_paths(G, source=0, target=2)])
+    [[0, 1, 2], [0, 10, 2]]
+
+    Notes
+    -----
+    There may be many shortest paths between the source and target.  If G
+    contains zero-weight cycles, this function will not produce all shortest
+    paths because doing so would produce infinitely many paths of unbounded
+    length -- instead, we only produce the shortest simple paths.
+
+    See Also
+    --------
+    shortest_path
+    single_source_shortest_path
+    all_pairs_shortest_path
+    """
+    method = "unweighted" if weight is None else method
+    if method == "unweighted":
+        pred = nx.predecessor(G, source)
+    elif method == "dijkstra":
+        pred, dist = nx.dijkstra_predecessor_and_distance(G, source, weight=weight)
+    elif method == "bellman-ford":
+        pred, dist = nx.bellman_ford_predecessor_and_distance(G, source, weight=weight)
+    else:
+        raise ValueError(f"method not supported: {method}")
+
+    return _build_paths_from_predecessors({source}, target, pred)
+
+
+@nx._dispatchable(edge_attrs="weight")
+def single_source_all_shortest_paths(G, source, weight=None, method="dijkstra"):
+    """Compute all shortest simple paths from the given source in the graph.
+
+    Parameters
+    ----------
+    G : NetworkX graph
+
+    source : node
+       Starting node for path.
+
+    weight : None, string or function, optional (default = None)
+        If None, every edge has weight/distance/cost 1.
+        If a string, use this edge attribute as the edge weight.
+        Any edge attribute not present defaults to 1.
+        If this is a function, the weight of an edge is the value
+        returned by the function. The function must accept exactly
+        three positional arguments: the two endpoints of an edge and
+        the dictionary of edge attributes for that edge.
+        The function must return a number.
+
+    method : string, optional (default = 'dijkstra')
+       The algorithm to use to compute the path lengths.
+       Supported options: 'dijkstra', 'bellman-ford'.
+       Other inputs produce a ValueError.
+       If `weight` is None, unweighted graph methods are used, and this
+       suggestion is ignored.
+
+    Returns
+    -------
+    paths : generator of dictionary
+        A generator of all paths between source and all nodes in the graph.
+
+    Raises
+    ------
+    ValueError
+        If `method` is not among the supported options.
+
+    Examples
+    --------
+    >>> G = nx.Graph()
+    >>> nx.add_path(G, [0, 1, 2, 3, 0])
+    >>> dict(nx.single_source_all_shortest_paths(G, source=0))
+    {0: [[0]], 1: [[0, 1]], 2: [[0, 1, 2], [0, 3, 2]], 3: [[0, 3]]}
+
+    Notes
+    -----
+    There may be many shortest paths between the source and target.  If G
+    contains zero-weight cycles, this function will not produce all shortest
+    paths because doing so would produce infinitely many paths of unbounded
+    length -- instead, we only produce the shortest simple paths.
+
+    See Also
+    --------
+    shortest_path
+    all_shortest_paths
+    single_source_shortest_path
+    all_pairs_shortest_path
+    all_pairs_all_shortest_paths
+    """
+    method = "unweighted" if weight is None else method
+    if method == "unweighted":
+        pred = nx.predecessor(G, source)
+    elif method == "dijkstra":
+        pred, dist = nx.dijkstra_predecessor_and_distance(G, source, weight=weight)
+    elif method == "bellman-ford":
+        pred, dist = nx.bellman_ford_predecessor_and_distance(G, source, weight=weight)
+    else:
+        raise ValueError(f"method not supported: {method}")
+    for n in G:
+        try:
+            yield n, list(_build_paths_from_predecessors({source}, n, pred))
+        except nx.NetworkXNoPath:
+            pass
+
+
+@nx._dispatchable(edge_attrs="weight")
+def all_pairs_all_shortest_paths(G, weight=None, method="dijkstra"):
+    """Compute all shortest paths between all nodes.
+
+    Parameters
+    ----------
+    G : NetworkX graph
+
+    weight : None, string or function, optional (default = None)
+        If None, every edge has weight/distance/cost 1.
+        If a string, use this edge attribute as the edge weight.
+        Any edge attribute not present defaults to 1.
+        If this is a function, the weight of an edge is the value
+        returned by the function. The function must accept exactly
+        three positional arguments: the two endpoints of an edge and
+        the dictionary of edge attributes for that edge.
+        The function must return a number.
+
+    method : string, optional (default = 'dijkstra')
+       The algorithm to use to compute the path lengths.
+       Supported options: 'dijkstra', 'bellman-ford'.
+       Other inputs produce a ValueError.
+       If `weight` is None, unweighted graph methods are used, and this
+       suggestion is ignored.
+
+    Returns
+    -------
+    paths : generator of dictionary
+        Dictionary of arrays, keyed by source and target, of all shortest paths.
+
+    Raises
+    ------
+    ValueError
+        If `method` is not among the supported options.
+
+    Examples
+    --------
+    >>> G = nx.cycle_graph(4)
+    >>> dict(nx.all_pairs_all_shortest_paths(G))[0][2]
+    [[0, 1, 2], [0, 3, 2]]
+    >>> dict(nx.all_pairs_all_shortest_paths(G))[0][3]
+    [[0, 3]]
+
+    Notes
+    -----
+    There may be multiple shortest paths with equal lengths. Unlike
+    all_pairs_shortest_path, this method returns all shortest paths.
+
+    See Also
+    --------
+    all_pairs_shortest_path
+    single_source_all_shortest_paths
+    """
+    for n in G:
+        yield (
+            n,
+            dict(single_source_all_shortest_paths(G, n, weight=weight, method=method)),
+        )
+
+
+def _build_paths_from_predecessors(sources, target, pred):
+    """Compute all simple paths to target, given the predecessors found in
+    pred, terminating when any source in sources is found.
+
+    Parameters
+    ----------
+    sources : set
+       Starting nodes for path.
+
+    target : node
+       Ending node for path.
+
+    pred : dict
+       A dictionary of predecessor lists, keyed by node
+
+    Returns
+    -------
+    paths : generator of lists
+        A generator of all paths between source and target.
+
+    Raises
+    ------
+    NetworkXNoPath
+        If `target` cannot be reached from `source`.
+
+    Notes
+    -----
+    There may be many paths between the sources and target.  If there are
+    cycles among the predecessors, this function will not produce all
+    possible paths because doing so would produce infinitely many paths
+    of unbounded length -- instead, we only produce simple paths.
+
+    See Also
+    --------
+    shortest_path
+    single_source_shortest_path
+    all_pairs_shortest_path
+    all_shortest_paths
+    bellman_ford_path
+    """
+    if target not in pred:
+        raise nx.NetworkXNoPath(f"Target {target} cannot be reached from given sources")
+
+    seen = {target}
+    stack = [[target, 0]]
+    top = 0
+    while top >= 0:
+        node, i = stack[top]
+        if node in sources:
+            yield [p for p, n in reversed(stack[: top + 1])]
+        if len(pred[node]) > i:
+            stack[top][1] = i + 1
+            next = pred[node][i]
+            if next in seen:
+                continue
+            else:
+                seen.add(next)
+            top += 1
+            if top == len(stack):
+                stack.append([next, 0])
+            else:
+                stack[top][:] = [next, 0]
+        else:
+            seen.discard(node)
+            top -= 1
diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/shortest_paths/tests/__init__.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/shortest_paths/tests/__init__.py
new file mode 100644
index 00000000..e69de29b
--- /dev/null
+++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/shortest_paths/tests/__init__.py
diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/shortest_paths/tests/test_astar.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/shortest_paths/tests/test_astar.py
new file mode 100644
index 00000000..40a7d4e8
--- /dev/null
+++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/shortest_paths/tests/test_astar.py
@@ -0,0 +1,248 @@
+import pytest
+
+import networkx as nx
+from networkx.utils import pairwise
+
+
+class TestAStar:
+    @classmethod
+    def setup_class(cls):
+        edges = [
+            ("s", "u", 10),
+            ("s", "x", 5),
+            ("u", "v", 1),
+            ("u", "x", 2),
+            ("v", "y", 1),
+            ("x", "u", 3),
+            ("x", "v", 5),
+            ("x", "y", 2),
+            ("y", "s", 7),
+            ("y", "v", 6),
+        ]
+        cls.XG = nx.DiGraph()
+        cls.XG.add_weighted_edges_from(edges)
+
+    def test_multiple_optimal_paths(self):
+        """Tests that A* algorithm finds any of multiple optimal paths"""
+        heuristic_values = {"a": 1.35, "b": 1.18, "c": 0.67, "d": 0}
+
+        def h(u, v):
+            return heuristic_values[u]
+
+        graph = nx.Graph()
+        points = ["a", "b", "c", "d"]
+        edges = [("a", "b", 0.18), ("a", "c", 0.68), ("b", "c", 0.50), ("c", "d", 0.67)]
+
+        graph.add_nodes_from(points)
+        graph.add_weighted_edges_from(edges)
+
+        path1 = ["a", "c", "d"]
+        path2 = ["a", "b", "c", "d"]
+        assert nx.astar_path(graph, "a", "d", h) in (path1, path2)
+
+    def test_astar_directed(self):
+        assert nx.astar_path(self.XG, "s", "v") == ["s", "x", "u", "v"]
+        assert nx.astar_path_length(self.XG, "s", "v") == 9
+
+    def test_astar_directed_weight_function(self):
+        w1 = lambda u, v, d: d["weight"]
+        assert nx.astar_path(self.XG, "x", "u", weight=w1) == ["x", "u"]
+        assert nx.astar_path_length(self.XG, "x", "u", weight=w1) == 3
+        assert nx.astar_path(self.XG, "s", "v", weight=w1) == ["s", "x", "u", "v"]
+        assert nx.astar_path_length(self.XG, "s", "v", weight=w1) == 9
+
+        w2 = lambda u, v, d: None if (u, v) == ("x", "u") else d["weight"]
+        assert nx.astar_path(self.XG, "x", "u", weight=w2) == ["x", "y", "s", "u"]
+        assert nx.astar_path_length(self.XG, "x", "u", weight=w2) == 19
+        assert nx.astar_path(self.XG, "s", "v", weight=w2) == ["s", "x", "v"]
+        assert nx.astar_path_length(self.XG, "s", "v", weight=w2) == 10
+
+        w3 = lambda u, v, d: d["weight"] + 10
+        assert nx.astar_path(self.XG, "x", "u", weight=w3) == ["x", "u"]
+        assert nx.astar_path_length(self.XG, "x", "u", weight=w3) == 13
+        assert nx.astar_path(self.XG, "s", "v", weight=w3) == ["s", "x", "v"]
+        assert nx.astar_path_length(self.XG, "s", "v", weight=w3) == 30
+
+    def test_astar_multigraph(self):
+        G = nx.MultiDiGraph(self.XG)
+        G.add_weighted_edges_from((u, v, 1000) for (u, v) in list(G.edges()))
+        assert nx.astar_path(G, "s", "v") == ["s", "x", "u", "v"]
+        assert nx.astar_path_length(G, "s", "v") == 9
+
+    def test_astar_undirected(self):
+        GG = self.XG.to_undirected()
+        # make sure we get lower weight
+        # to_undirected might choose either edge with weight 2 or weight 3
+        GG["u"]["x"]["weight"] = 2
+        GG["y"]["v"]["weight"] = 2
+        assert nx.astar_path(GG, "s", "v") == ["s", "x", "u", "v"]
+        assert nx.astar_path_length(GG, "s", "v") == 8
+
+    def test_astar_directed2(self):
+        XG2 = nx.DiGraph()
+        edges = [
+            (1, 4, 1),
+            (4, 5, 1),
+            (5, 6, 1),
+            (6, 3, 1),
+            (1, 3, 50),
+            (1, 2, 100),
+            (2, 3, 100),
+        ]
+        XG2.add_weighted_edges_from(edges)
+        assert nx.astar_path(XG2, 1, 3) == [1, 4, 5, 6, 3]
+
+    def test_astar_undirected2(self):
+        XG3 = nx.Graph()
+        edges = [(0, 1, 2), (1, 2, 12), (2, 3, 1), (3, 4, 5), (4, 5, 1), (5, 0, 10)]
+        XG3.add_weighted_edges_from(edges)
+        assert nx.astar_path(XG3, 0, 3) == [0, 1, 2, 3]
+        assert nx.astar_path_length(XG3, 0, 3) == 15
+
+    def test_astar_undirected3(self):
+        XG4 = nx.Graph()
+        edges = [
+            (0, 1, 2),
+            (1, 2, 2),
+            (2, 3, 1),
+            (3, 4, 1),
+            (4, 5, 1),
+            (5, 6, 1),
+            (6, 7, 1),
+            (7, 0, 1),
+        ]
+        XG4.add_weighted_edges_from(edges)
+        assert nx.astar_path(XG4, 0, 2) == [0, 1, 2]
+        assert nx.astar_path_length(XG4, 0, 2) == 4
+
+    """ Tests that A* finds correct path when multiple paths exist
+        and the best one is not expanded first (GH issue #3464)
+    """
+
+    def test_astar_directed3(self):
+        heuristic_values = {"n5": 36, "n2": 4, "n1": 0, "n0": 0}
+
+        def h(u, v):
+            return heuristic_values[u]
+
+        edges = [("n5", "n1", 11), ("n5", "n2", 9), ("n2", "n1", 1), ("n1", "n0", 32)]
+        graph = nx.DiGraph()
+        graph.add_weighted_edges_from(edges)
+        answer = ["n5", "n2", "n1", "n0"]
+        assert nx.astar_path(graph, "n5", "n0", h) == answer
+
+    """ Tests that parent is not wrongly overridden when a node
+        is re-explored multiple times.
+    """
+
+    def test_astar_directed4(self):
+        edges = [
+            ("a", "b", 1),
+            ("a", "c", 1),
+            ("b", "d", 2),
+            ("c", "d", 1),
+            ("d", "e", 1),
+        ]
+        graph = nx.DiGraph()
+        graph.add_weighted_edges_from(edges)
+        assert nx.astar_path(graph, "a", "e") == ["a", "c", "d", "e"]
+
+    # >>> MXG4=NX.MultiGraph(XG4)
+    # >>> MXG4.add_edge(0,1,3)
+    # >>> NX.dijkstra_path(MXG4,0,2)
+    # [0, 1, 2]
+
+    def test_astar_w1(self):
+        G = nx.DiGraph()
+        G.add_edges_from(
+            [
+                ("s", "u"),
+                ("s", "x"),
+                ("u", "v"),
+                ("u", "x"),
+                ("v", "y"),
+                ("x", "u"),
+                ("x", "w"),
+                ("w", "v"),
+                ("x", "y"),
+                ("y", "s"),
+                ("y", "v"),
+            ]
+        )
+        assert nx.astar_path(G, "s", "v") == ["s", "u", "v"]
+        assert nx.astar_path_length(G, "s", "v") == 2
+
+    def test_astar_nopath(self):
+        with pytest.raises(nx.NodeNotFound):
+            nx.astar_path(self.XG, "s", "moon")
+
+    def test_astar_cutoff(self):
+        with pytest.raises(nx.NetworkXNoPath):
+            # optimal path_length in XG is 9
+            nx.astar_path(self.XG, "s", "v", cutoff=8.0)
+        with pytest.raises(nx.NetworkXNoPath):
+            nx.astar_path_length(self.XG, "s", "v", cutoff=8.0)
+
+    def test_astar_admissible_heuristic_with_cutoff(self):
+        heuristic_values = {"s": 36, "y": 4, "x": 0, "u": 0, "v": 0}
+
+        def h(u, v):
+            return heuristic_values[u]
+
+        assert nx.astar_path_length(self.XG, "s", "v") == 9
+        assert nx.astar_path_length(self.XG, "s", "v", heuristic=h) == 9
+        assert nx.astar_path_length(self.XG, "s", "v", heuristic=h, cutoff=12) == 9
+        assert nx.astar_path_length(self.XG, "s", "v", heuristic=h, cutoff=9) == 9
+        with pytest.raises(nx.NetworkXNoPath):
+            nx.astar_path_length(self.XG, "s", "v", heuristic=h, cutoff=8)
+
+    def test_astar_inadmissible_heuristic_with_cutoff(self):
+        heuristic_values = {"s": 36, "y": 14, "x": 10, "u": 10, "v": 0}
+
+        def h(u, v):
+            return heuristic_values[u]
+
+        # optimal path_length in XG is 9. This heuristic gives over-estimate.
+        assert nx.astar_path_length(self.XG, "s", "v", heuristic=h) == 10
+        assert nx.astar_path_length(self.XG, "s", "v", heuristic=h, cutoff=15) == 10
+        with pytest.raises(nx.NetworkXNoPath):
+            nx.astar_path_length(self.XG, "s", "v", heuristic=h, cutoff=9)
+        with pytest.raises(nx.NetworkXNoPath):
+            nx.astar_path_length(self.XG, "s", "v", heuristic=h, cutoff=12)
+
+    def test_astar_cutoff2(self):
+        assert nx.astar_path(self.XG, "s", "v", cutoff=10.0) == ["s", "x", "u", "v"]
+        assert nx.astar_path_length(self.XG, "s", "v") == 9
+
+    def test_cycle(self):
+        C = nx.cycle_graph(7)
+        assert nx.astar_path(C, 0, 3) == [0, 1, 2, 3]
+        assert nx.dijkstra_path(C, 0, 4) == [0, 6, 5, 4]
+
+    def test_unorderable_nodes(self):
+        """Tests that A* accommodates nodes that are not orderable.
+
+        For more information, see issue #554.
+
+        """
+        # Create the cycle graph on four nodes, with nodes represented
+        # as (unorderable) Python objects.
+        nodes = [object() for n in range(4)]
+        G = nx.Graph()
+        G.add_edges_from(pairwise(nodes, cyclic=True))
+        path = nx.astar_path(G, nodes[0], nodes[2])
+        assert len(path) == 3
+
+    def test_astar_NetworkXNoPath(self):
+        """Tests that exception is raised when there exists no
+        path between source and target"""
+        G = nx.gnp_random_graph(10, 0.2, seed=10)
+        with pytest.raises(nx.NetworkXNoPath):
+            nx.astar_path(G, 4, 9)
+
+    def test_astar_NodeNotFound(self):
+        """Tests that exception is raised when either
+        source or target is not in graph"""
+        G = nx.gnp_random_graph(10, 0.2, seed=10)
+        with pytest.raises(nx.NodeNotFound):
+            nx.astar_path_length(G, 11, 9)
diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/shortest_paths/tests/test_dense.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/shortest_paths/tests/test_dense.py
new file mode 100644
index 00000000..6923bfef
--- /dev/null
+++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/shortest_paths/tests/test_dense.py
@@ -0,0 +1,212 @@
+import pytest
+
+import networkx as nx
+
+
+class TestFloyd:
+    @classmethod
+    def setup_class(cls):
+        pass
+
+    def test_floyd_warshall_predecessor_and_distance(self):
+        XG = nx.DiGraph()
+        XG.add_weighted_edges_from(
+            [
+                ("s", "u", 10),
+                ("s", "x", 5),
+                ("u", "v", 1),
+                ("u", "x", 2),
+                ("v", "y", 1),
+                ("x", "u", 3),
+                ("x", "v", 5),
+                ("x", "y", 2),
+                ("y", "s", 7),
+                ("y", "v", 6),
+            ]
+        )
+        path, dist = nx.floyd_warshall_predecessor_and_distance(XG)
+        assert dist["s"]["v"] == 9
+        assert path["s"]["v"] == "u"
+        assert dist == {
+            "y": {"y": 0, "x": 12, "s": 7, "u": 15, "v": 6},
+            "x": {"y": 2, "x": 0, "s": 9, "u": 3, "v": 4},
+            "s": {"y": 7, "x": 5, "s": 0, "u": 8, "v": 9},
+            "u": {"y": 2, "x": 2, "s": 9, "u": 0, "v": 1},
+            "v": {"y": 1, "x": 13, "s": 8, "u": 16, "v": 0},
+        }
+
+        GG = XG.to_undirected()
+        # make sure we get lower weight
+        # to_undirected might choose either edge with weight 2 or weight 3
+        GG["u"]["x"]["weight"] = 2
+        path, dist = nx.floyd_warshall_predecessor_and_distance(GG)
+        assert dist["s"]["v"] == 8
+        # skip this test, could be alternate path s-u-v
+        #        assert_equal(path['s']['v'],'y')
+
+        G = nx.DiGraph()  # no weights
+        G.add_edges_from(
+            [
+                ("s", "u"),
+                ("s", "x"),
+                ("u", "v"),
+                ("u", "x"),
+                ("v", "y"),
+                ("x", "u"),
+                ("x", "v"),
+                ("x", "y"),
+                ("y", "s"),
+                ("y", "v"),
+            ]
+        )
+        path, dist = nx.floyd_warshall_predecessor_and_distance(G)
+        assert dist["s"]["v"] == 2
+        # skip this test, could be alternate path s-u-v
+        # assert_equal(path['s']['v'],'x')
+
+        # alternate interface
+        dist = nx.floyd_warshall(G)
+        assert dist["s"]["v"] == 2
+
+        # floyd_warshall_predecessor_and_distance returns
+        # dicts-of-defautdicts
+        # make sure we don't get empty dictionary
+        XG = nx.DiGraph()
+        XG.add_weighted_edges_from(
+            [("v", "x", 5.0), ("y", "x", 5.0), ("v", "y", 6.0), ("x", "u", 2.0)]
+        )
+        path, dist = nx.floyd_warshall_predecessor_and_distance(XG)
+        inf = float("inf")
+        assert dist == {
+            "v": {"v": 0, "x": 5.0, "y": 6.0, "u": 7.0},
+            "x": {"x": 0, "u": 2.0, "v": inf, "y": inf},
+            "y": {"y": 0, "x": 5.0, "v": inf, "u": 7.0},
+            "u": {"u": 0, "v": inf, "x": inf, "y": inf},
+        }
+        assert path == {
+            "v": {"x": "v", "y": "v", "u": "x"},
+            "x": {"u": "x"},
+            "y": {"x": "y", "u": "x"},
+        }
+
+    def test_reconstruct_path(self):
+        with pytest.raises(KeyError):
+            XG = nx.DiGraph()
+            XG.add_weighted_edges_from(
+                [
+                    ("s", "u", 10),
+                    ("s", "x", 5),
+                    ("u", "v", 1),
+                    ("u", "x", 2),
+                    ("v", "y", 1),
+                    ("x", "u", 3),
+                    ("x", "v", 5),
+                    ("x", "y", 2),
+                    ("y", "s", 7),
+                    ("y", "v", 6),
+                ]
+            )
+            predecessors, _ = nx.floyd_warshall_predecessor_and_distance(XG)
+
+            path = nx.reconstruct_path("s", "v", predecessors)
+            assert path == ["s", "x", "u", "v"]
+
+            path = nx.reconstruct_path("s", "s", predecessors)
+            assert path == []
+
+            # this part raises the keyError
+            nx.reconstruct_path("1", "2", predecessors)
+
+    def test_cycle(self):
+        path, dist = nx.floyd_warshall_predecessor_and_distance(nx.cycle_graph(7))
+        assert dist[0][3] == 3
+        assert path[0][3] == 2
+        assert dist[0][4] == 3
+
+    def test_weighted(self):
+        XG3 = nx.Graph()
+        XG3.add_weighted_edges_from(
+            [[0, 1, 2], [1, 2, 12], [2, 3, 1], [3, 4, 5], [4, 5, 1], [5, 0, 10]]
+        )
+        path, dist = nx.floyd_warshall_predecessor_and_distance(XG3)
+        assert dist[0][3] == 15
+        assert path[0][3] == 2
+
+    def test_weighted2(self):
+        XG4 = nx.Graph()
+        XG4.add_weighted_edges_from(
+            [
+                [0, 1, 2],
+                [1, 2, 2],
+                [2, 3, 1],
+                [3, 4, 1],
+                [4, 5, 1],
+                [5, 6, 1],
+                [6, 7, 1],
+                [7, 0, 1],
+            ]
+        )
+        path, dist = nx.floyd_warshall_predecessor_and_distance(XG4)
+        assert dist[0][2] == 4
+        assert path[0][2] == 1
+
+    def test_weight_parameter(self):
+        XG4 = nx.Graph()
+        XG4.add_edges_from(
+            [
+                (0, 1, {"heavy": 2}),
+                (1, 2, {"heavy": 2}),
+                (2, 3, {"heavy": 1}),
+                (3, 4, {"heavy": 1}),
+                (4, 5, {"heavy": 1}),
+                (5, 6, {"heavy": 1}),
+                (6, 7, {"heavy": 1}),
+                (7, 0, {"heavy": 1}),
+            ]
+        )
+        path, dist = nx.floyd_warshall_predecessor_and_distance(XG4, weight="heavy")
+        assert dist[0][2] == 4
+        assert path[0][2] == 1
+
+    def test_zero_distance(self):
+        XG = nx.DiGraph()
+        XG.add_weighted_edges_from(
+            [
+                ("s", "u", 10),
+                ("s", "x", 5),
+                ("u", "v", 1),
+                ("u", "x", 2),
+                ("v", "y", 1),
+                ("x", "u", 3),
+                ("x", "v", 5),
+                ("x", "y", 2),
+                ("y", "s", 7),
+                ("y", "v", 6),
+            ]
+        )
+        path, dist = nx.floyd_warshall_predecessor_and_distance(XG)
+
+        for u in XG:
+            assert dist[u][u] == 0
+
+        GG = XG.to_undirected()
+        # make sure we get lower weight
+        # to_undirected might choose either edge with weight 2 or weight 3
+        GG["u"]["x"]["weight"] = 2
+        path, dist = nx.floyd_warshall_predecessor_and_distance(GG)
+
+        for u in GG:
+            dist[u][u] = 0
+
+    def test_zero_weight(self):
+        G = nx.DiGraph()
+        edges = [(1, 2, -2), (2, 3, -4), (1, 5, 1), (5, 4, 0), (4, 3, -5), (2, 5, -7)]
+        G.add_weighted_edges_from(edges)
+        dist = nx.floyd_warshall(G)
+        assert dist[1][3] == -14
+
+        G = nx.MultiDiGraph()
+        edges.append((2, 5, -7))
+        G.add_weighted_edges_from(edges)
+        dist = nx.floyd_warshall(G)
+        assert dist[1][3] == -14
diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/shortest_paths/tests/test_dense_numpy.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/shortest_paths/tests/test_dense_numpy.py
new file mode 100644
index 00000000..1316e23e
--- /dev/null
+++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/shortest_paths/tests/test_dense_numpy.py
@@ -0,0 +1,89 @@
+import pytest
+
+np = pytest.importorskip("numpy")
+
+
+import networkx as nx
+
+
+def test_cycle_numpy():
+    dist = nx.floyd_warshall_numpy(nx.cycle_graph(7))
+    assert dist[0, 3] == 3
+    assert dist[0, 4] == 3
+
+
+def test_weighted_numpy_three_edges():
+    XG3 = nx.Graph()
+    XG3.add_weighted_edges_from(
+        [[0, 1, 2], [1, 2, 12], [2, 3, 1], [3, 4, 5], [4, 5, 1], [5, 0, 10]]
+    )
+    dist = nx.floyd_warshall_numpy(XG3)
+    assert dist[0, 3] == 15
+
+
+def test_weighted_numpy_two_edges():
+    XG4 = nx.Graph()
+    XG4.add_weighted_edges_from(
+        [
+            [0, 1, 2],
+            [1, 2, 2],
+            [2, 3, 1],
+            [3, 4, 1],
+            [4, 5, 1],
+            [5, 6, 1],
+            [6, 7, 1],
+            [7, 0, 1],
+        ]
+    )
+    dist = nx.floyd_warshall_numpy(XG4)
+    assert dist[0, 2] == 4
+
+
+def test_weight_parameter_numpy():
+    XG4 = nx.Graph()
+    XG4.add_edges_from(
+        [
+            (0, 1, {"heavy": 2}),
+            (1, 2, {"heavy": 2}),
+            (2, 3, {"heavy": 1}),
+            (3, 4, {"heavy": 1}),
+            (4, 5, {"heavy": 1}),
+            (5, 6, {"heavy": 1}),
+            (6, 7, {"heavy": 1}),
+            (7, 0, {"heavy": 1}),
+        ]
+    )
+    dist = nx.floyd_warshall_numpy(XG4, weight="heavy")
+    assert dist[0, 2] == 4
+
+
+def test_directed_cycle_numpy():
+    G = nx.DiGraph()
+    nx.add_cycle(G, [0, 1, 2, 3])
+    pred, dist = nx.floyd_warshall_predecessor_and_distance(G)
+    D = nx.utils.dict_to_numpy_array(dist)
+    np.testing.assert_equal(nx.floyd_warshall_numpy(G), D)
+
+
+def test_zero_weight():
+    G = nx.DiGraph()
+    edges = [(1, 2, -2), (2, 3, -4), (1, 5, 1), (5, 4, 0), (4, 3, -5), (2, 5, -7)]
+    G.add_weighted_edges_from(edges)
+    dist = nx.floyd_warshall_numpy(G)
+    assert int(np.min(dist)) == -14
+
+    G = nx.MultiDiGraph()
+    edges.append((2, 5, -7))
+    G.add_weighted_edges_from(edges)
+    dist = nx.floyd_warshall_numpy(G)
+    assert int(np.min(dist)) == -14
+
+
+def test_nodelist():
+    G = nx.path_graph(7)
+    dist = nx.floyd_warshall_numpy(G, nodelist=[3, 5, 4, 6, 2, 1, 0])
+    assert dist[0, 3] == 3
+    assert dist[0, 1] == 2
+    assert dist[6, 2] == 4
+    pytest.raises(nx.NetworkXError, nx.floyd_warshall_numpy, G, [1, 3])
+    pytest.raises(nx.NetworkXError, nx.floyd_warshall_numpy, G, list(range(9)))
diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/shortest_paths/tests/test_generic.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/shortest_paths/tests/test_generic.py
new file mode 100644
index 00000000..e30de517
--- /dev/null
+++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/shortest_paths/tests/test_generic.py
@@ -0,0 +1,450 @@
+import pytest
+
+import networkx as nx
+
+
+def validate_grid_path(r, c, s, t, p):
+    assert isinstance(p, list)
+    assert p[0] == s
+    assert p[-1] == t
+    s = ((s - 1) // c, (s - 1) % c)
+    t = ((t - 1) // c, (t - 1) % c)
+    assert len(p) == abs(t[0] - s[0]) + abs(t[1] - s[1]) + 1
+    p = [((u - 1) // c, (u - 1) % c) for u in p]
+    for u in p:
+        assert 0 <= u[0] < r
+        assert 0 <= u[1] < c
+    for u, v in zip(p[:-1], p[1:]):
+        assert (abs(v[0] - u[0]), abs(v[1] - u[1])) in [(0, 1), (1, 0)]
+
+
+class TestGenericPath:
+    @classmethod
+    def setup_class(cls):
+        from networkx import convert_node_labels_to_integers as cnlti
+
+        cls.grid = cnlti(nx.grid_2d_graph(4, 4), first_label=1, ordering="sorted")
+        cls.cycle = nx.cycle_graph(7)
+        cls.directed_cycle = nx.cycle_graph(7, create_using=nx.DiGraph())
+        cls.neg_weights = nx.DiGraph()
+        cls.neg_weights.add_edge(0, 1, weight=1)
+        cls.neg_weights.add_edge(0, 2, weight=3)
+        cls.neg_weights.add_edge(1, 3, weight=1)
+        cls.neg_weights.add_edge(2, 3, weight=-2)
+
+    def test_shortest_path(self):
+        assert nx.shortest_path(self.cycle, 0, 3) == [0, 1, 2, 3]
+        assert nx.shortest_path(self.cycle, 0, 4) == [0, 6, 5, 4]
+        validate_grid_path(4, 4, 1, 12, nx.shortest_path(self.grid, 1, 12))
+        assert nx.shortest_path(self.directed_cycle, 0, 3) == [0, 1, 2, 3]
+        # now with weights
+        assert nx.shortest_path(self.cycle, 0, 3, weight="weight") == [0, 1, 2, 3]
+        assert nx.shortest_path(self.cycle, 0, 4, weight="weight") == [0, 6, 5, 4]
+        validate_grid_path(
+            4, 4, 1, 12, nx.shortest_path(self.grid, 1, 12, weight="weight")
+        )
+        assert nx.shortest_path(self.directed_cycle, 0, 3, weight="weight") == [
+            0,
+            1,
+            2,
+            3,
+        ]
+        # weights and method specified
+        assert nx.shortest_path(
+            self.directed_cycle, 0, 3, weight="weight", method="dijkstra"
+        ) == [0, 1, 2, 3]
+        assert nx.shortest_path(
+            self.directed_cycle, 0, 3, weight="weight", method="bellman-ford"
+        ) == [0, 1, 2, 3]
+        # when Dijkstra's will probably (depending on precise implementation)
+        # incorrectly return [0, 1, 3] instead
+        assert nx.shortest_path(
+            self.neg_weights, 0, 3, weight="weight", method="bellman-ford"
+        ) == [0, 2, 3]
+        # confirm bad method rejection
+        pytest.raises(ValueError, nx.shortest_path, self.cycle, method="SPAM")
+        # confirm absent source rejection
+        pytest.raises(nx.NodeNotFound, nx.shortest_path, self.cycle, 8)
+
+    def test_shortest_path_target(self):
+        answer = {0: [0, 1], 1: [1], 2: [2, 1]}
+        sp = nx.shortest_path(nx.path_graph(3), target=1)
+        assert sp == answer
+        # with weights
+        sp = nx.shortest_path(nx.path_graph(3), target=1, weight="weight")
+        assert sp == answer
+        # weights and method specified
+        sp = nx.shortest_path(
+            nx.path_graph(3), target=1, weight="weight", method="dijkstra"
+        )
+        assert sp == answer
+        sp = nx.shortest_path(
+            nx.path_graph(3), target=1, weight="weight", method="bellman-ford"
+        )
+        assert sp == answer
+
+    def test_shortest_path_length(self):
+        assert nx.shortest_path_length(self.cycle, 0, 3) == 3
+        assert nx.shortest_path_length(self.grid, 1, 12) == 5
+        assert nx.shortest_path_length(self.directed_cycle, 0, 4) == 4
+        # now with weights
+        assert nx.shortest_path_length(self.cycle, 0, 3, weight="weight") == 3
+        assert nx.shortest_path_length(self.grid, 1, 12, weight="weight") == 5
+        assert nx.shortest_path_length(self.directed_cycle, 0, 4, weight="weight") == 4
+        # weights and method specified
+        assert (
+            nx.shortest_path_length(
+                self.cycle, 0, 3, weight="weight", method="dijkstra"
+            )
+            == 3
+        )
+        assert (
+            nx.shortest_path_length(
+                self.cycle, 0, 3, weight="weight", method="bellman-ford"
+            )
+            == 3
+        )
+        # confirm bad method rejection
+        pytest.raises(ValueError, nx.shortest_path_length, self.cycle, method="SPAM")
+        # confirm absent source rejection
+        pytest.raises(nx.NodeNotFound, nx.shortest_path_length, self.cycle, 8)
+
+    def test_shortest_path_length_target(self):
+        answer = {0: 1, 1: 0, 2: 1}
+        sp = dict(nx.shortest_path_length(nx.path_graph(3), target=1))
+        assert sp == answer
+        # with weights
+        sp = nx.shortest_path_length(nx.path_graph(3), target=1, weight="weight")
+        assert sp == answer
+        # weights and method specified
+        sp = nx.shortest_path_length(
+            nx.path_graph(3), target=1, weight="weight", method="dijkstra"
+        )
+        assert sp == answer
+        sp = nx.shortest_path_length(
+            nx.path_graph(3), target=1, weight="weight", method="bellman-ford"
+        )
+        assert sp == answer
+
+    def test_single_source_shortest_path(self):
+        p = nx.shortest_path(self.cycle, 0)
+        assert p[3] == [0, 1, 2, 3]
+        assert p == nx.single_source_shortest_path(self.cycle, 0)
+        p = nx.shortest_path(self.grid, 1)
+        validate_grid_path(4, 4, 1, 12, p[12])
+        # now with weights
+        p = nx.shortest_path(self.cycle, 0, weight="weight")
+        assert p[3] == [0, 1, 2, 3]
+        assert p == nx.single_source_dijkstra_path(self.cycle, 0)
+        p = nx.shortest_path(self.grid, 1, weight="weight")
+        validate_grid_path(4, 4, 1, 12, p[12])
+        # weights and method specified
+        p = nx.shortest_path(self.cycle, 0, method="dijkstra", weight="weight")
+        assert p[3] == [0, 1, 2, 3]
+        assert p == nx.single_source_shortest_path(self.cycle, 0)
+        p = nx.shortest_path(self.cycle, 0, method="bellman-ford", weight="weight")
+        assert p[3] == [0, 1, 2, 3]
+        assert p == nx.single_source_shortest_path(self.cycle, 0)
+
+    def test_single_source_shortest_path_length(self):
+        ans = dict(nx.shortest_path_length(self.cycle, 0))
+        assert ans == {0: 0, 1: 1, 2: 2, 3: 3, 4: 3, 5: 2, 6: 1}
+        assert ans == dict(nx.single_source_shortest_path_length(self.cycle, 0))
+        ans = dict(nx.shortest_path_length(self.grid, 1))
+        assert ans[16] == 6
+        # now with weights
+        ans = dict(nx.shortest_path_length(self.cycle, 0, weight="weight"))
+        assert ans == {0: 0, 1: 1, 2: 2, 3: 3, 4: 3, 5: 2, 6: 1}
+        assert ans == dict(nx.single_source_dijkstra_path_length(self.cycle, 0))
+        ans = dict(nx.shortest_path_length(self.grid, 1, weight="weight"))
+        assert ans[16] == 6
+        # weights and method specified
+        ans = dict(
+            nx.shortest_path_length(self.cycle, 0, weight="weight", method="dijkstra")
+        )
+        assert ans == {0: 0, 1: 1, 2: 2, 3: 3, 4: 3, 5: 2, 6: 1}
+        assert ans == dict(nx.single_source_dijkstra_path_length(self.cycle, 0))
+        ans = dict(
+            nx.shortest_path_length(
+                self.cycle, 0, weight="weight", method="bellman-ford"
+            )
+        )
+        assert ans == {0: 0, 1: 1, 2: 2, 3: 3, 4: 3, 5: 2, 6: 1}
+        assert ans == dict(nx.single_source_bellman_ford_path_length(self.cycle, 0))
+
+    def test_single_source_all_shortest_paths(self):
+        cycle_ans = {0: [[0]], 1: [[0, 1]], 2: [[0, 1, 2], [0, 3, 2]], 3: [[0, 3]]}
+        ans = dict(nx.single_source_all_shortest_paths(nx.cycle_graph(4), 0))
+        assert sorted(ans[2]) == cycle_ans[2]
+        ans = dict(nx.single_source_all_shortest_paths(self.grid, 1))
+        grid_ans = [
+            [1, 2, 3, 7, 11],
+            [1, 2, 6, 7, 11],
+            [1, 2, 6, 10, 11],
+            [1, 5, 6, 7, 11],
+            [1, 5, 6, 10, 11],
+            [1, 5, 9, 10, 11],
+        ]
+        assert sorted(ans[11]) == grid_ans
+        ans = dict(
+            nx.single_source_all_shortest_paths(nx.cycle_graph(4), 0, weight="weight")
+        )
+        assert sorted(ans[2]) == cycle_ans[2]
+        ans = dict(
+            nx.single_source_all_shortest_paths(
+                nx.cycle_graph(4), 0, method="bellman-ford", weight="weight"
+            )
+        )
+        assert sorted(ans[2]) == cycle_ans[2]
+        ans = dict(nx.single_source_all_shortest_paths(self.grid, 1, weight="weight"))
+        assert sorted(ans[11]) == grid_ans
+        ans = dict(
+            nx.single_source_all_shortest_paths(
+                self.grid, 1, method="bellman-ford", weight="weight"
+            )
+        )
+        assert sorted(ans[11]) == grid_ans
+        G = nx.cycle_graph(4)
+        G.add_node(4)
+        ans = dict(nx.single_source_all_shortest_paths(G, 0))
+        assert sorted(ans[2]) == [[0, 1, 2], [0, 3, 2]]
+        ans = dict(nx.single_source_all_shortest_paths(G, 4))
+        assert sorted(ans[4]) == [[4]]
+
+    def test_all_pairs_shortest_path(self):
+        # shortest_path w/o source and target will return a generator instead of
+        # a dict beginning in version 3.5. Only the first call needs changed here.
+        p = nx.shortest_path(self.cycle)
+        assert p[0][3] == [0, 1, 2, 3]
+        assert p == dict(nx.all_pairs_shortest_path(self.cycle))
+        p = dict(nx.shortest_path(self.grid))
+        validate_grid_path(4, 4, 1, 12, p[1][12])
+        # now with weights
+        p = dict(nx.shortest_path(self.cycle, weight="weight"))
+        assert p[0][3] == [0, 1, 2, 3]
+        assert p == dict(nx.all_pairs_dijkstra_path(self.cycle))
+        p = dict(nx.shortest_path(self.grid, weight="weight"))
+        validate_grid_path(4, 4, 1, 12, p[1][12])
+        # weights and method specified
+        p = dict(nx.shortest_path(self.cycle, weight="weight", method="dijkstra"))
+        assert p[0][3] == [0, 1, 2, 3]
+        assert p == dict(nx.all_pairs_dijkstra_path(self.cycle))
+        p = dict(nx.shortest_path(self.cycle, weight="weight", method="bellman-ford"))
+        assert p[0][3] == [0, 1, 2, 3]
+        assert p == dict(nx.all_pairs_bellman_ford_path(self.cycle))
+
+    def test_all_pairs_shortest_path_length(self):
+        ans = dict(nx.shortest_path_length(self.cycle))
+        assert ans[0] == {0: 0, 1: 1, 2: 2, 3: 3, 4: 3, 5: 2, 6: 1}
+        assert ans == dict(nx.all_pairs_shortest_path_length(self.cycle))
+        ans = dict(nx.shortest_path_length(self.grid))
+        assert ans[1][16] == 6
+        # now with weights
+        ans = dict(nx.shortest_path_length(self.cycle, weight="weight"))
+        assert ans[0] == {0: 0, 1: 1, 2: 2, 3: 3, 4: 3, 5: 2, 6: 1}
+        assert ans == dict(nx.all_pairs_dijkstra_path_length(self.cycle))
+        ans = dict(nx.shortest_path_length(self.grid, weight="weight"))
+        assert ans[1][16] == 6
+        # weights and method specified
+        ans = dict(
+            nx.shortest_path_length(self.cycle, weight="weight", method="dijkstra")
+        )
+        assert ans[0] == {0: 0, 1: 1, 2: 2, 3: 3, 4: 3, 5: 2, 6: 1}
+        assert ans == dict(nx.all_pairs_dijkstra_path_length(self.cycle))
+        ans = dict(
+            nx.shortest_path_length(self.cycle, weight="weight", method="bellman-ford")
+        )
+        assert ans[0] == {0: 0, 1: 1, 2: 2, 3: 3, 4: 3, 5: 2, 6: 1}
+        assert ans == dict(nx.all_pairs_bellman_ford_path_length(self.cycle))
+
+    def test_all_pairs_all_shortest_paths(self):
+        ans = dict(nx.all_pairs_all_shortest_paths(nx.cycle_graph(4)))
+        assert sorted(ans[1][3]) == [[1, 0, 3], [1, 2, 3]]
+        ans = dict(nx.all_pairs_all_shortest_paths(nx.cycle_graph(4)), weight="weight")
+        assert sorted(ans[1][3]) == [[1, 0, 3], [1, 2, 3]]
+        ans = dict(
+            nx.all_pairs_all_shortest_paths(nx.cycle_graph(4)),
+            method="bellman-ford",
+            weight="weight",
+        )
+        assert sorted(ans[1][3]) == [[1, 0, 3], [1, 2, 3]]
+        G = nx.cycle_graph(4)
+        G.add_node(4)
+        ans = dict(nx.all_pairs_all_shortest_paths(G))
+        assert sorted(ans[4][4]) == [[4]]
+
+    def test_has_path(self):
+        G = nx.Graph()
+        nx.add_path(G, range(3))
+        nx.add_path(G, range(3, 5))
+        assert nx.has_path(G, 0, 2)
+        assert not nx.has_path(G, 0, 4)
+
+    def test_has_path_singleton(self):
+        G = nx.empty_graph(1)
+        assert nx.has_path(G, 0, 0)
+
+    def test_all_shortest_paths(self):
+        G = nx.Graph()
+        nx.add_path(G, [0, 1, 2, 3])
+        nx.add_path(G, [0, 10, 20, 3])
+        assert [[0, 1, 2, 3], [0, 10, 20, 3]] == sorted(nx.all_shortest_paths(G, 0, 3))
+        # with weights
+        G = nx.Graph()
+        nx.add_path(G, [0, 1, 2, 3])
+        nx.add_path(G, [0, 10, 20, 3])
+        assert [[0, 1, 2, 3], [0, 10, 20, 3]] == sorted(
+            nx.all_shortest_paths(G, 0, 3, weight="weight")
+        )
+        # weights and method specified
+        G = nx.Graph()
+        nx.add_path(G, [0, 1, 2, 3])
+        nx.add_path(G, [0, 10, 20, 3])
+        assert [[0, 1, 2, 3], [0, 10, 20, 3]] == sorted(
+            nx.all_shortest_paths(G, 0, 3, weight="weight", method="dijkstra")
+        )
+        G = nx.Graph()
+        nx.add_path(G, [0, 1, 2, 3])
+        nx.add_path(G, [0, 10, 20, 3])
+        assert [[0, 1, 2, 3], [0, 10, 20, 3]] == sorted(
+            nx.all_shortest_paths(G, 0, 3, weight="weight", method="bellman-ford")
+        )
+
+    def test_all_shortest_paths_raise(self):
+        with pytest.raises(nx.NetworkXNoPath):
+            G = nx.path_graph(4)
+            G.add_node(4)
+            list(nx.all_shortest_paths(G, 0, 4))
+
+    def test_bad_method(self):
+        with pytest.raises(ValueError):
+            G = nx.path_graph(2)
+            list(nx.all_shortest_paths(G, 0, 1, weight="weight", method="SPAM"))
+
+    def test_single_source_all_shortest_paths_bad_method(self):
+        with pytest.raises(ValueError):
+            G = nx.path_graph(2)
+            dict(
+                nx.single_source_all_shortest_paths(
+                    G, 0, weight="weight", method="SPAM"
+                )
+            )
+
+    def test_all_shortest_paths_zero_weight_edge(self):
+        g = nx.Graph()
+        nx.add_path(g, [0, 1, 3])
+        nx.add_path(g, [0, 1, 2, 3])
+        g.edges[1, 2]["weight"] = 0
+        paths30d = list(
+            nx.all_shortest_paths(g, 3, 0, weight="weight", method="dijkstra")
+        )
+        paths03d = list(
+            nx.all_shortest_paths(g, 0, 3, weight="weight", method="dijkstra")
+        )
+        paths30b = list(
+            nx.all_shortest_paths(g, 3, 0, weight="weight", method="bellman-ford")
+        )
+        paths03b = list(
+            nx.all_shortest_paths(g, 0, 3, weight="weight", method="bellman-ford")
+        )
+        assert sorted(paths03d) == sorted(p[::-1] for p in paths30d)
+        assert sorted(paths03d) == sorted(p[::-1] for p in paths30b)
+        assert sorted(paths03b) == sorted(p[::-1] for p in paths30b)
+
+
+class TestAverageShortestPathLength:
+    def test_cycle_graph(self):
+        ans = nx.average_shortest_path_length(nx.cycle_graph(7))
+        assert ans == pytest.approx(2, abs=1e-7)
+
+    def test_path_graph(self):
+        ans = nx.average_shortest_path_length(nx.path_graph(5))
+        assert ans == pytest.approx(2, abs=1e-7)
+
+    def test_weighted(self):
+        G = nx.Graph()
+        nx.add_cycle(G, range(7), weight=2)
+        ans = nx.average_shortest_path_length(G, weight="weight")
+        assert ans == pytest.approx(4, abs=1e-7)
+        G = nx.Graph()
+        nx.add_path(G, range(5), weight=2)
+        ans = nx.average_shortest_path_length(G, weight="weight")
+        assert ans == pytest.approx(4, abs=1e-7)
+
+    def test_specified_methods(self):
+        G = nx.Graph()
+        nx.add_cycle(G, range(7), weight=2)
+        ans = nx.average_shortest_path_length(G, weight="weight", method="dijkstra")
+        assert ans == pytest.approx(4, abs=1e-7)
+        ans = nx.average_shortest_path_length(G, weight="weight", method="bellman-ford")
+        assert ans == pytest.approx(4, abs=1e-7)
+        ans = nx.average_shortest_path_length(
+            G, weight="weight", method="floyd-warshall"
+        )
+        assert ans == pytest.approx(4, abs=1e-7)
+
+        G = nx.Graph()
+        nx.add_path(G, range(5), weight=2)
+        ans = nx.average_shortest_path_length(G, weight="weight", method="dijkstra")
+        assert ans == pytest.approx(4, abs=1e-7)
+        ans = nx.average_shortest_path_length(G, weight="weight", method="bellman-ford")
+        assert ans == pytest.approx(4, abs=1e-7)
+        ans = nx.average_shortest_path_length(
+            G, weight="weight", method="floyd-warshall"
+        )
+        assert ans == pytest.approx(4, abs=1e-7)
+
+    def test_directed_not_strongly_connected(self):
+        G = nx.DiGraph([(0, 1)])
+        with pytest.raises(nx.NetworkXError, match="Graph is not strongly connected"):
+            nx.average_shortest_path_length(G)
+
+    def test_undirected_not_connected(self):
+        g = nx.Graph()
+        g.add_nodes_from(range(3))
+        g.add_edge(0, 1)
+        pytest.raises(nx.NetworkXError, nx.average_shortest_path_length, g)
+
+    def test_trivial_graph(self):
+        """Tests that the trivial graph has average path length zero,
+        since there is exactly one path of length zero in the trivial
+        graph.
+
+        For more information, see issue #1960.
+
+        """
+        G = nx.trivial_graph()
+        assert nx.average_shortest_path_length(G) == 0
+
+    def test_null_graph(self):
+        with pytest.raises(nx.NetworkXPointlessConcept):
+            nx.average_shortest_path_length(nx.null_graph())
+
+    def test_bad_method(self):
+        with pytest.raises(ValueError):
+            G = nx.path_graph(2)
+            nx.average_shortest_path_length(G, weight="weight", method="SPAM")
+
+
+class TestAverageShortestPathLengthNumpy:
+    @classmethod
+    def setup_class(cls):
+        global np
+        import pytest
+
+        np = pytest.importorskip("numpy")
+
+    def test_specified_methods_numpy(self):
+        G = nx.Graph()
+        nx.add_cycle(G, range(7), weight=2)
+        ans = nx.average_shortest_path_length(
+            G, weight="weight", method="floyd-warshall-numpy"
+        )
+        np.testing.assert_almost_equal(ans, 4)
+
+        G = nx.Graph()
+        nx.add_path(G, range(5), weight=2)
+        ans = nx.average_shortest_path_length(
+            G, weight="weight", method="floyd-warshall-numpy"
+        )
+        np.testing.assert_almost_equal(ans, 4)
diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/shortest_paths/tests/test_unweighted.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/shortest_paths/tests/test_unweighted.py
new file mode 100644
index 00000000..f09c8b10
--- /dev/null
+++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/shortest_paths/tests/test_unweighted.py
@@ -0,0 +1,149 @@
+import pytest
+
+import networkx as nx
+
+
+def validate_grid_path(r, c, s, t, p):
+    assert isinstance(p, list)
+    assert p[0] == s
+    assert p[-1] == t
+    s = ((s - 1) // c, (s - 1) % c)
+    t = ((t - 1) // c, (t - 1) % c)
+    assert len(p) == abs(t[0] - s[0]) + abs(t[1] - s[1]) + 1
+    p = [((u - 1) // c, (u - 1) % c) for u in p]
+    for u in p:
+        assert 0 <= u[0] < r
+        assert 0 <= u[1] < c
+    for u, v in zip(p[:-1], p[1:]):
+        assert (abs(v[0] - u[0]), abs(v[1] - u[1])) in [(0, 1), (1, 0)]
+
+
+class TestUnweightedPath:
+    @classmethod
+    def setup_class(cls):
+        from networkx import convert_node_labels_to_integers as cnlti
+
+        cls.grid = cnlti(nx.grid_2d_graph(4, 4), first_label=1, ordering="sorted")
+        cls.cycle = nx.cycle_graph(7)
+        cls.directed_cycle = nx.cycle_graph(7, create_using=nx.DiGraph())
+
+    def test_bidirectional_shortest_path(self):
+        assert nx.bidirectional_shortest_path(self.cycle, 0, 3) == [0, 1, 2, 3]
+        assert nx.bidirectional_shortest_path(self.cycle, 0, 4) == [0, 6, 5, 4]
+        validate_grid_path(
+            4, 4, 1, 12, nx.bidirectional_shortest_path(self.grid, 1, 12)
+        )
+        assert nx.bidirectional_shortest_path(self.directed_cycle, 0, 3) == [0, 1, 2, 3]
+        # test source = target
+        assert nx.bidirectional_shortest_path(self.cycle, 3, 3) == [3]
+
+    @pytest.mark.parametrize(
+        ("src", "tgt"),
+        (
+            (8, 3),  # source not in graph
+            (3, 8),  # target not in graph
+            (8, 10),  # neither source nor target in graph
+            (8, 8),  # src == tgt, neither in graph - tests order of input checks
+        ),
+    )
+    def test_bidirectional_shortest_path_src_tgt_not_in_graph(self, src, tgt):
+        with pytest.raises(
+            nx.NodeNotFound,
+            match=f"(Source {src}|Target {tgt}) is not in G",
+        ):
+            nx.bidirectional_shortest_path(self.cycle, src, tgt)
+
+    def test_shortest_path_length(self):
+        assert nx.shortest_path_length(self.cycle, 0, 3) == 3
+        assert nx.shortest_path_length(self.grid, 1, 12) == 5
+        assert nx.shortest_path_length(self.directed_cycle, 0, 4) == 4
+        # now with weights
+        assert nx.shortest_path_length(self.cycle, 0, 3, weight=True) == 3
+        assert nx.shortest_path_length(self.grid, 1, 12, weight=True) == 5
+        assert nx.shortest_path_length(self.directed_cycle, 0, 4, weight=True) == 4
+
+    def test_single_source_shortest_path(self):
+        p = nx.single_source_shortest_path(self.directed_cycle, 3)
+        assert p[0] == [3, 4, 5, 6, 0]
+        p = nx.single_source_shortest_path(self.cycle, 0)
+        assert p[3] == [0, 1, 2, 3]
+        p = nx.single_source_shortest_path(self.cycle, 0, cutoff=0)
+        assert p == {0: [0]}
+
+    def test_single_source_shortest_path_length(self):
+        pl = nx.single_source_shortest_path_length
+        lengths = {0: 0, 1: 1, 2: 2, 3: 3, 4: 3, 5: 2, 6: 1}
+        assert dict(pl(self.cycle, 0)) == lengths
+        lengths = {0: 0, 1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 6: 6}
+        assert dict(pl(self.directed_cycle, 0)) == lengths
+
+    def test_single_target_shortest_path(self):
+        p = nx.single_target_shortest_path(self.directed_cycle, 0)
+        assert p[3] == [3, 4, 5, 6, 0]
+        p = nx.single_target_shortest_path(self.cycle, 0)
+        assert p[3] == [3, 2, 1, 0]
+        p = nx.single_target_shortest_path(self.cycle, 0, cutoff=0)
+        assert p == {0: [0]}
+        # test missing targets
+        target = 8
+        with pytest.raises(nx.NodeNotFound, match=f"Target {target} not in G"):
+            nx.single_target_shortest_path(self.cycle, target)
+
+    def test_single_target_shortest_path_length(self):
+        pl = nx.single_target_shortest_path_length
+        lengths = {0: 0, 1: 1, 2: 2, 3: 3, 4: 3, 5: 2, 6: 1}
+        assert dict(pl(self.cycle, 0)) == lengths
+        lengths = {0: 0, 1: 6, 2: 5, 3: 4, 4: 3, 5: 2, 6: 1}
+        assert dict(pl(self.directed_cycle, 0)) == lengths
+        # test missing targets
+        target = 8
+        with pytest.raises(nx.NodeNotFound, match=f"Target {target} is not in G"):
+            nx.single_target_shortest_path_length(self.cycle, target)
+
+    def test_all_pairs_shortest_path(self):
+        p = dict(nx.all_pairs_shortest_path(self.cycle))
+        assert p[0][3] == [0, 1, 2, 3]
+        p = dict(nx.all_pairs_shortest_path(self.grid))
+        validate_grid_path(4, 4, 1, 12, p[1][12])
+
+    def test_all_pairs_shortest_path_length(self):
+        l = dict(nx.all_pairs_shortest_path_length(self.cycle))
+        assert l[0] == {0: 0, 1: 1, 2: 2, 3: 3, 4: 3, 5: 2, 6: 1}
+        l = dict(nx.all_pairs_shortest_path_length(self.grid))
+        assert l[1][16] == 6
+
+    def test_predecessor_path(self):
+        G = nx.path_graph(4)
+        assert nx.predecessor(G, 0) == {0: [], 1: [0], 2: [1], 3: [2]}
+        assert nx.predecessor(G, 0, 3) == [2]
+
+    def test_predecessor_cycle(self):
+        G = nx.cycle_graph(4)
+        pred = nx.predecessor(G, 0)
+        assert pred[0] == []
+        assert pred[1] == [0]
+        assert pred[2] in [[1, 3], [3, 1]]
+        assert pred[3] == [0]
+
+    def test_predecessor_cutoff(self):
+        G = nx.path_graph(4)
+        p = nx.predecessor(G, 0, 3)
+        assert 4 not in p
+
+    def test_predecessor_target(self):
+        G = nx.path_graph(4)
+        p = nx.predecessor(G, 0, 3)
+        assert p == [2]
+        p = nx.predecessor(G, 0, 3, cutoff=2)
+        assert p == []
+        p, s = nx.predecessor(G, 0, 3, return_seen=True)
+        assert p == [2]
+        assert s == 3
+        p, s = nx.predecessor(G, 0, 3, cutoff=2, return_seen=True)
+        assert p == []
+        assert s == -1
+
+    def test_predecessor_missing_source(self):
+        source = 8
+        with pytest.raises(nx.NodeNotFound, match=f"Source {source} not in G"):
+            nx.predecessor(self.cycle, source)
diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/shortest_paths/tests/test_weighted.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/shortest_paths/tests/test_weighted.py
new file mode 100644
index 00000000..dc88572d
--- /dev/null
+++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/shortest_paths/tests/test_weighted.py
@@ -0,0 +1,972 @@
+import pytest
+
+import networkx as nx
+from networkx.utils import pairwise
+
+
+def validate_path(G, s, t, soln_len, path, weight="weight"):
+    assert path[0] == s
+    assert path[-1] == t
+
+    if callable(weight):
+        weight_f = weight
+    else:
+        if G.is_multigraph():
+
+            def weight_f(u, v, d):
+                return min(e.get(weight, 1) for e in d.values())
+
+        else:
+
+            def weight_f(u, v, d):
+                return d.get(weight, 1)
+
+    computed = sum(weight_f(u, v, G[u][v]) for u, v in pairwise(path))
+    assert soln_len == computed
+
+
+def validate_length_path(G, s, t, soln_len, length, path, weight="weight"):
+    assert soln_len == length
+    validate_path(G, s, t, length, path, weight=weight)
+
+
+class WeightedTestBase:
+    """Base class for test classes that test functions for computing
+    shortest paths in weighted graphs.
+
+    """
+
+    def setup_method(self):
+        """Creates some graphs for use in the unit tests."""
+        cnlti = nx.convert_node_labels_to_integers
+        self.grid = cnlti(nx.grid_2d_graph(4, 4), first_label=1, ordering="sorted")
+        self.cycle = nx.cycle_graph(7)
+        self.directed_cycle = nx.cycle_graph(7, create_using=nx.DiGraph())
+        self.XG = nx.DiGraph()
+        self.XG.add_weighted_edges_from(
+            [
+                ("s", "u", 10),
+                ("s", "x", 5),
+                ("u", "v", 1),
+                ("u", "x", 2),
+                ("v", "y", 1),
+                ("x", "u", 3),
+                ("x", "v", 5),
+                ("x", "y", 2),
+                ("y", "s", 7),
+                ("y", "v", 6),
+            ]
+        )
+        self.MXG = nx.MultiDiGraph(self.XG)
+        self.MXG.add_edge("s", "u", weight=15)
+        self.XG2 = nx.DiGraph()
+        self.XG2.add_weighted_edges_from(
+            [
+                [1, 4, 1],
+                [4, 5, 1],
+                [5, 6, 1],
+                [6, 3, 1],
+                [1, 3, 50],
+                [1, 2, 100],
+                [2, 3, 100],
+            ]
+        )
+
+        self.XG3 = nx.Graph()
+        self.XG3.add_weighted_edges_from(
+            [[0, 1, 2], [1, 2, 12], [2, 3, 1], [3, 4, 5], [4, 5, 1], [5, 0, 10]]
+        )
+
+        self.XG4 = nx.Graph()
+        self.XG4.add_weighted_edges_from(
+            [
+                [0, 1, 2],
+                [1, 2, 2],
+                [2, 3, 1],
+                [3, 4, 1],
+                [4, 5, 1],
+                [5, 6, 1],
+                [6, 7, 1],
+                [7, 0, 1],
+            ]
+        )
+        self.MXG4 = nx.MultiGraph(self.XG4)
+        self.MXG4.add_edge(0, 1, weight=3)
+        self.G = nx.DiGraph()  # no weights
+        self.G.add_edges_from(
+            [
+                ("s", "u"),
+                ("s", "x"),
+                ("u", "v"),
+                ("u", "x"),
+                ("v", "y"),
+                ("x", "u"),
+                ("x", "v"),
+                ("x", "y"),
+                ("y", "s"),
+                ("y", "v"),
+            ]
+        )
+
+
+class TestWeightedPath(WeightedTestBase):
+    def test_dijkstra(self):
+        (D, P) = nx.single_source_dijkstra(self.XG, "s")
+        validate_path(self.XG, "s", "v", 9, P["v"])
+        assert D["v"] == 9
+
+        validate_path(
+            self.XG, "s", "v", 9, nx.single_source_dijkstra_path(self.XG, "s")["v"]
+        )
+        assert dict(nx.single_source_dijkstra_path_length(self.XG, "s"))["v"] == 9
+
+        validate_path(
+            self.XG, "s", "v", 9, nx.single_source_dijkstra(self.XG, "s")[1]["v"]
+        )
+        validate_path(
+            self.MXG, "s", "v", 9, nx.single_source_dijkstra_path(self.MXG, "s")["v"]
+        )
+
+        GG = self.XG.to_undirected()
+        # make sure we get lower weight
+        # to_undirected might choose either edge with weight 2 or weight 3
+        GG["u"]["x"]["weight"] = 2
+        (D, P) = nx.single_source_dijkstra(GG, "s")
+        validate_path(GG, "s", "v", 8, P["v"])
+        assert D["v"] == 8  # uses lower weight of 2 on u<->x edge
+        validate_path(GG, "s", "v", 8, nx.dijkstra_path(GG, "s", "v"))
+        assert nx.dijkstra_path_length(GG, "s", "v") == 8
+
+        validate_path(self.XG2, 1, 3, 4, nx.dijkstra_path(self.XG2, 1, 3))
+        validate_path(self.XG3, 0, 3, 15, nx.dijkstra_path(self.XG3, 0, 3))
+        assert nx.dijkstra_path_length(self.XG3, 0, 3) == 15
+        validate_path(self.XG4, 0, 2, 4, nx.dijkstra_path(self.XG4, 0, 2))
+        assert nx.dijkstra_path_length(self.XG4, 0, 2) == 4
+        validate_path(self.MXG4, 0, 2, 4, nx.dijkstra_path(self.MXG4, 0, 2))
+        validate_path(
+            self.G, "s", "v", 2, nx.single_source_dijkstra(self.G, "s", "v")[1]
+        )
+        validate_path(
+            self.G, "s", "v", 2, nx.single_source_dijkstra(self.G, "s")[1]["v"]
+        )
+
+        validate_path(self.G, "s", "v", 2, nx.dijkstra_path(self.G, "s", "v"))
+        assert nx.dijkstra_path_length(self.G, "s", "v") == 2
+
+        # NetworkXError: node s not reachable from moon
+        pytest.raises(nx.NetworkXNoPath, nx.dijkstra_path, self.G, "s", "moon")
+        pytest.raises(nx.NetworkXNoPath, nx.dijkstra_path_length, self.G, "s", "moon")
+
+        validate_path(self.cycle, 0, 3, 3, nx.dijkstra_path(self.cycle, 0, 3))
+        validate_path(self.cycle, 0, 4, 3, nx.dijkstra_path(self.cycle, 0, 4))
+
+        assert nx.single_source_dijkstra(self.cycle, 0, 0) == (0, [0])
+
+    def test_bidirectional_dijkstra(self):
+        validate_length_path(
+            self.XG, "s", "v", 9, *nx.bidirectional_dijkstra(self.XG, "s", "v")
+        )
+        validate_length_path(
+            self.G, "s", "v", 2, *nx.bidirectional_dijkstra(self.G, "s", "v")
+        )
+        validate_length_path(
+            self.cycle, 0, 3, 3, *nx.bidirectional_dijkstra(self.cycle, 0, 3)
+        )
+        validate_length_path(
+            self.cycle, 0, 4, 3, *nx.bidirectional_dijkstra(self.cycle, 0, 4)
+        )
+        validate_length_path(
+            self.XG3, 0, 3, 15, *nx.bidirectional_dijkstra(self.XG3, 0, 3)
+        )
+        validate_length_path(
+            self.XG4, 0, 2, 4, *nx.bidirectional_dijkstra(self.XG4, 0, 2)
+        )
+
+        # need more tests here
+        P = nx.single_source_dijkstra_path(self.XG, "s")["v"]
+        validate_path(
+            self.XG,
+            "s",
+            "v",
+            sum(self.XG[u][v]["weight"] for u, v in zip(P[:-1], P[1:])),
+            nx.dijkstra_path(self.XG, "s", "v"),
+        )
+
+        # check absent source
+        G = nx.path_graph(2)
+        pytest.raises(nx.NodeNotFound, nx.bidirectional_dijkstra, G, 3, 0)
+
+    def test_weight_functions(self):
+        def heuristic(*z):
+            return sum(val**2 for val in z)
+
+        def getpath(pred, v, s):
+            return [v] if v == s else getpath(pred, pred[v], s) + [v]
+
+        def goldberg_radzik(g, s, t, weight="weight"):
+            pred, dist = nx.goldberg_radzik(g, s, weight=weight)
+            dist = dist[t]
+            return dist, getpath(pred, t, s)
+
+        def astar(g, s, t, weight="weight"):
+            path = nx.astar_path(g, s, t, heuristic, weight=weight)
+            dist = nx.astar_path_length(g, s, t, heuristic, weight=weight)
+            return dist, path
+
+        def vlp(G, s, t, l, F, w):
+            res = F(G, s, t, weight=w)
+            validate_length_path(G, s, t, l, *res, weight=w)
+
+        G = self.cycle
+        s = 6
+        t = 4
+        path = [6] + list(range(t + 1))
+
+        def weight(u, v, _):
+            return 1 + v**2
+
+        length = sum(weight(u, v, None) for u, v in pairwise(path))
+        vlp(G, s, t, length, nx.bidirectional_dijkstra, weight)
+        vlp(G, s, t, length, nx.single_source_dijkstra, weight)
+        vlp(G, s, t, length, nx.single_source_bellman_ford, weight)
+        vlp(G, s, t, length, goldberg_radzik, weight)
+        vlp(G, s, t, length, astar, weight)
+
+        def weight(u, v, _):
+            return 2 ** (u * v)
+
+        length = sum(weight(u, v, None) for u, v in pairwise(path))
+        vlp(G, s, t, length, nx.bidirectional_dijkstra, weight)
+        vlp(G, s, t, length, nx.single_source_dijkstra, weight)
+        vlp(G, s, t, length, nx.single_source_bellman_ford, weight)
+        vlp(G, s, t, length, goldberg_radzik, weight)
+        vlp(G, s, t, length, astar, weight)
+
+    def test_bidirectional_dijkstra_no_path(self):
+        with pytest.raises(nx.NetworkXNoPath):
+            G = nx.Graph()
+            nx.add_path(G, [1, 2, 3])
+            nx.add_path(G, [4, 5, 6])
+            path = nx.bidirectional_dijkstra(G, 1, 6)
+
+    @pytest.mark.parametrize(
+        "fn",
+        (
+            nx.dijkstra_path,
+            nx.dijkstra_path_length,
+            nx.single_source_dijkstra_path,
+            nx.single_source_dijkstra_path_length,
+            nx.single_source_dijkstra,
+            nx.dijkstra_predecessor_and_distance,
+        ),
+    )
+    def test_absent_source(self, fn):
+        G = nx.path_graph(2)
+        with pytest.raises(nx.NodeNotFound):
+            fn(G, 3, 0)
+        # Test when source == target, which is handled specially by some functions
+        with pytest.raises(nx.NodeNotFound):
+            fn(G, 3, 3)
+
+    def test_dijkstra_predecessor1(self):
+        G = nx.path_graph(4)
+        assert nx.dijkstra_predecessor_and_distance(G, 0) == (
+            {0: [], 1: [0], 2: [1], 3: [2]},
+            {0: 0, 1: 1, 2: 2, 3: 3},
+        )
+
+    def test_dijkstra_predecessor2(self):
+        # 4-cycle
+        G = nx.Graph([(0, 1), (1, 2), (2, 3), (3, 0)])
+        pred, dist = nx.dijkstra_predecessor_and_distance(G, (0))
+        assert pred[0] == []
+        assert pred[1] == [0]
+        assert pred[2] in [[1, 3], [3, 1]]
+        assert pred[3] == [0]
+        assert dist == {0: 0, 1: 1, 2: 2, 3: 1}
+
+    def test_dijkstra_predecessor3(self):
+        XG = nx.DiGraph()
+        XG.add_weighted_edges_from(
+            [
+                ("s", "u", 10),
+                ("s", "x", 5),
+                ("u", "v", 1),
+                ("u", "x", 2),
+                ("v", "y", 1),
+                ("x", "u", 3),
+                ("x", "v", 5),
+                ("x", "y", 2),
+                ("y", "s", 7),
+                ("y", "v", 6),
+            ]
+        )
+        (P, D) = nx.dijkstra_predecessor_and_distance(XG, "s")
+        assert P["v"] == ["u"]
+        assert D["v"] == 9
+        (P, D) = nx.dijkstra_predecessor_and_distance(XG, "s", cutoff=8)
+        assert "v" not in D
+
+    def test_single_source_dijkstra_path_length(self):
+        pl = nx.single_source_dijkstra_path_length
+        assert dict(pl(self.MXG4, 0))[2] == 4
+        spl = pl(self.MXG4, 0, cutoff=2)
+        assert 2 not in spl
+
+    def test_bidirectional_dijkstra_multigraph(self):
+        G = nx.MultiGraph()
+        G.add_edge("a", "b", weight=10)
+        G.add_edge("a", "b", weight=100)
+        dp = nx.bidirectional_dijkstra(G, "a", "b")
+        assert dp == (10, ["a", "b"])
+
+    def test_dijkstra_pred_distance_multigraph(self):
+        G = nx.MultiGraph()
+        G.add_edge("a", "b", key="short", foo=5, weight=100)
+        G.add_edge("a", "b", key="long", bar=1, weight=110)
+        p, d = nx.dijkstra_predecessor_and_distance(G, "a")
+        assert p == {"a": [], "b": ["a"]}
+        assert d == {"a": 0, "b": 100}
+
+    def test_negative_edge_cycle(self):
+        G = nx.cycle_graph(5, create_using=nx.DiGraph())
+        assert not nx.negative_edge_cycle(G)
+        G.add_edge(8, 9, weight=-7)
+        G.add_edge(9, 8, weight=3)
+        graph_size = len(G)
+        assert nx.negative_edge_cycle(G)
+        assert graph_size == len(G)
+        pytest.raises(ValueError, nx.single_source_dijkstra_path_length, G, 8)
+        pytest.raises(ValueError, nx.single_source_dijkstra, G, 8)
+        pytest.raises(ValueError, nx.dijkstra_predecessor_and_distance, G, 8)
+        G.add_edge(9, 10)
+        pytest.raises(ValueError, nx.bidirectional_dijkstra, G, 8, 10)
+        G = nx.MultiDiGraph()
+        G.add_edge(2, 2, weight=-1)
+        assert nx.negative_edge_cycle(G)
+
+    def test_negative_edge_cycle_empty(self):
+        G = nx.DiGraph()
+        assert not nx.negative_edge_cycle(G)
+
+    def test_negative_edge_cycle_custom_weight_key(self):
+        d = nx.DiGraph()
+        d.add_edge("a", "b", w=-2)
+        d.add_edge("b", "a", w=-1)
+        assert nx.negative_edge_cycle(d, weight="w")
+
+    def test_weight_function(self):
+        """Tests that a callable weight is interpreted as a weight
+        function instead of an edge attribute.
+
+        """
+        # Create a triangle in which the edge from node 0 to node 2 has
+        # a large weight and the other two edges have a small weight.
+        G = nx.complete_graph(3)
+        G.adj[0][2]["weight"] = 10
+        G.adj[0][1]["weight"] = 1
+        G.adj[1][2]["weight"] = 1
+
+        # The weight function will take the multiplicative inverse of
+        # the weights on the edges. This way, weights that were large
+        # before now become small and vice versa.
+
+        def weight(u, v, d):
+            return 1 / d["weight"]
+
+        # The shortest path from 0 to 2 using the actual weights on the
+        # edges should be [0, 1, 2].
+        distance, path = nx.single_source_dijkstra(G, 0, 2)
+        assert distance == 2
+        assert path == [0, 1, 2]
+        # However, with the above weight function, the shortest path
+        # should be [0, 2], since that has a very small weight.
+        distance, path = nx.single_source_dijkstra(G, 0, 2, weight=weight)
+        assert distance == 1 / 10
+        assert path == [0, 2]
+
+    def test_all_pairs_dijkstra_path(self):
+        cycle = nx.cycle_graph(7)
+        p = dict(nx.all_pairs_dijkstra_path(cycle))
+        assert p[0][3] == [0, 1, 2, 3]
+
+        cycle[1][2]["weight"] = 10
+        p = dict(nx.all_pairs_dijkstra_path(cycle))
+        assert p[0][3] == [0, 6, 5, 4, 3]
+
+    def test_all_pairs_dijkstra_path_length(self):
+        cycle = nx.cycle_graph(7)
+        pl = dict(nx.all_pairs_dijkstra_path_length(cycle))
+        assert pl[0] == {0: 0, 1: 1, 2: 2, 3: 3, 4: 3, 5: 2, 6: 1}
+
+        cycle[1][2]["weight"] = 10
+        pl = dict(nx.all_pairs_dijkstra_path_length(cycle))
+        assert pl[0] == {0: 0, 1: 1, 2: 5, 3: 4, 4: 3, 5: 2, 6: 1}
+
+    def test_all_pairs_dijkstra(self):
+        cycle = nx.cycle_graph(7)
+        out = dict(nx.all_pairs_dijkstra(cycle))
+        assert out[0][0] == {0: 0, 1: 1, 2: 2, 3: 3, 4: 3, 5: 2, 6: 1}
+        assert out[0][1][3] == [0, 1, 2, 3]
+
+        cycle[1][2]["weight"] = 10
+        out = dict(nx.all_pairs_dijkstra(cycle))
+        assert out[0][0] == {0: 0, 1: 1, 2: 5, 3: 4, 4: 3, 5: 2, 6: 1}
+        assert out[0][1][3] == [0, 6, 5, 4, 3]
+
+
+class TestDijkstraPathLength:
+    """Unit tests for the :func:`networkx.dijkstra_path_length`
+    function.
+
+    """
+
+    def test_weight_function(self):
+        """Tests for computing the length of the shortest path using
+        Dijkstra's algorithm with a user-defined weight function.
+
+        """
+        # Create a triangle in which the edge from node 0 to node 2 has
+        # a large weight and the other two edges have a small weight.
+        G = nx.complete_graph(3)
+        G.adj[0][2]["weight"] = 10
+        G.adj[0][1]["weight"] = 1
+        G.adj[1][2]["weight"] = 1
+
+        # The weight function will take the multiplicative inverse of
+        # the weights on the edges. This way, weights that were large
+        # before now become small and vice versa.
+
+        def weight(u, v, d):
+            return 1 / d["weight"]
+
+        # The shortest path from 0 to 2 using the actual weights on the
+        # edges should be [0, 1, 2]. However, with the above weight
+        # function, the shortest path should be [0, 2], since that has a
+        # very small weight.
+        length = nx.dijkstra_path_length(G, 0, 2, weight=weight)
+        assert length == 1 / 10
+
+
+class TestMultiSourceDijkstra:
+    """Unit tests for the multi-source dialect of Dijkstra's shortest
+    path algorithms.
+
+    """
+
+    def test_no_sources(self):
+        with pytest.raises(ValueError):
+            nx.multi_source_dijkstra(nx.Graph(), {})
+
+    def test_path_no_sources(self):
+        with pytest.raises(ValueError):
+            nx.multi_source_dijkstra_path(nx.Graph(), {})
+
+    def test_path_length_no_sources(self):
+        with pytest.raises(ValueError):
+            nx.multi_source_dijkstra_path_length(nx.Graph(), {})
+
+    @pytest.mark.parametrize(
+        "fn",
+        (
+            nx.multi_source_dijkstra_path,
+            nx.multi_source_dijkstra_path_length,
+            nx.multi_source_dijkstra,
+        ),
+    )
+    def test_absent_source(self, fn):
+        G = nx.path_graph(2)
+        with pytest.raises(nx.NodeNotFound):
+            fn(G, [3], 0)
+        with pytest.raises(nx.NodeNotFound):
+            fn(G, [3], 3)
+
+    def test_two_sources(self):
+        edges = [(0, 1, 1), (1, 2, 1), (2, 3, 10), (3, 4, 1)]
+        G = nx.Graph()
+        G.add_weighted_edges_from(edges)
+        sources = {0, 4}
+        distances, paths = nx.multi_source_dijkstra(G, sources)
+        expected_distances = {0: 0, 1: 1, 2: 2, 3: 1, 4: 0}
+        expected_paths = {0: [0], 1: [0, 1], 2: [0, 1, 2], 3: [4, 3], 4: [4]}
+        assert distances == expected_distances
+        assert paths == expected_paths
+
+    def test_simple_paths(self):
+        G = nx.path_graph(4)
+        lengths = nx.multi_source_dijkstra_path_length(G, [0])
+        assert lengths == {n: n for n in G}
+        paths = nx.multi_source_dijkstra_path(G, [0])
+        assert paths == {n: list(range(n + 1)) for n in G}
+
+
+class TestBellmanFordAndGoldbergRadzik(WeightedTestBase):
+    def test_single_node_graph(self):
+        G = nx.DiGraph()
+        G.add_node(0)
+        assert nx.single_source_bellman_ford_path(G, 0) == {0: [0]}
+        assert nx.single_source_bellman_ford_path_length(G, 0) == {0: 0}
+        assert nx.single_source_bellman_ford(G, 0) == ({0: 0}, {0: [0]})
+        assert nx.bellman_ford_predecessor_and_distance(G, 0) == ({0: []}, {0: 0})
+        assert nx.goldberg_radzik(G, 0) == ({0: None}, {0: 0})
+
+    def test_absent_source_bellman_ford(self):
+        # the check is in _bellman_ford; this provides regression testing
+        # against later changes to "client" Bellman-Ford functions
+        G = nx.path_graph(2)
+        for fn in (
+            nx.bellman_ford_predecessor_and_distance,
+            nx.bellman_ford_path,
+            nx.bellman_ford_path_length,
+            nx.single_source_bellman_ford_path,
+            nx.single_source_bellman_ford_path_length,
+            nx.single_source_bellman_ford,
+        ):
+            pytest.raises(nx.NodeNotFound, fn, G, 3, 0)
+            pytest.raises(nx.NodeNotFound, fn, G, 3, 3)
+
+    def test_absent_source_goldberg_radzik(self):
+        with pytest.raises(nx.NodeNotFound):
+            G = nx.path_graph(2)
+            nx.goldberg_radzik(G, 3, 0)
+
+    def test_negative_cycle_heuristic(self):
+        G = nx.DiGraph()
+        G.add_edge(0, 1, weight=-1)
+        G.add_edge(1, 2, weight=-1)
+        G.add_edge(2, 3, weight=-1)
+        G.add_edge(3, 0, weight=3)
+        assert not nx.negative_edge_cycle(G, heuristic=True)
+        G.add_edge(2, 0, weight=1.999)
+        assert nx.negative_edge_cycle(G, heuristic=True)
+        G.edges[2, 0]["weight"] = 2
+        assert not nx.negative_edge_cycle(G, heuristic=True)
+
+    def test_negative_cycle_consistency(self):
+        import random
+
+        unif = random.uniform
+        for random_seed in range(2):  # range(20):
+            random.seed(random_seed)
+            for density in [0.1, 0.9]:  # .3, .7, .9]:
+                for N in [1, 10, 20]:  # range(1, 60 - int(30 * density)):
+                    for max_cost in [1, 90]:  # [1, 10, 40, 90]:
+                        G = nx.binomial_graph(N, density, seed=4, directed=True)
+                        edges = ((u, v, unif(-1, max_cost)) for u, v in G.edges)
+                        G.add_weighted_edges_from(edges)
+
+                        no_heuristic = nx.negative_edge_cycle(G, heuristic=False)
+                        with_heuristic = nx.negative_edge_cycle(G, heuristic=True)
+                        assert no_heuristic == with_heuristic
+
+    def test_negative_cycle(self):
+        G = nx.cycle_graph(5, create_using=nx.DiGraph())
+        G.add_edge(1, 2, weight=-7)
+        for i in range(5):
+            pytest.raises(
+                nx.NetworkXUnbounded, nx.single_source_bellman_ford_path, G, i
+            )
+            pytest.raises(
+                nx.NetworkXUnbounded, nx.single_source_bellman_ford_path_length, G, i
+            )
+            pytest.raises(nx.NetworkXUnbounded, nx.single_source_bellman_ford, G, i)
+            pytest.raises(
+                nx.NetworkXUnbounded, nx.bellman_ford_predecessor_and_distance, G, i
+            )
+            pytest.raises(nx.NetworkXUnbounded, nx.goldberg_radzik, G, i)
+        G = nx.cycle_graph(5)  # undirected Graph
+        G.add_edge(1, 2, weight=-3)
+        for i in range(5):
+            pytest.raises(
+                nx.NetworkXUnbounded, nx.single_source_bellman_ford_path, G, i
+            )
+            pytest.raises(
+                nx.NetworkXUnbounded, nx.single_source_bellman_ford_path_length, G, i
+            )
+            pytest.raises(nx.NetworkXUnbounded, nx.single_source_bellman_ford, G, i)
+            pytest.raises(
+                nx.NetworkXUnbounded, nx.bellman_ford_predecessor_and_distance, G, i
+            )
+            pytest.raises(nx.NetworkXUnbounded, nx.goldberg_radzik, G, i)
+        G = nx.DiGraph([(1, 1, {"weight": -1})])
+        pytest.raises(nx.NetworkXUnbounded, nx.single_source_bellman_ford_path, G, 1)
+        pytest.raises(
+            nx.NetworkXUnbounded, nx.single_source_bellman_ford_path_length, G, 1
+        )
+        pytest.raises(nx.NetworkXUnbounded, nx.single_source_bellman_ford, G, 1)
+        pytest.raises(
+            nx.NetworkXUnbounded, nx.bellman_ford_predecessor_and_distance, G, 1
+        )
+        pytest.raises(nx.NetworkXUnbounded, nx.goldberg_radzik, G, 1)
+        G = nx.MultiDiGraph([(1, 1, {"weight": -1})])
+        pytest.raises(nx.NetworkXUnbounded, nx.single_source_bellman_ford_path, G, 1)
+        pytest.raises(
+            nx.NetworkXUnbounded, nx.single_source_bellman_ford_path_length, G, 1
+        )
+        pytest.raises(nx.NetworkXUnbounded, nx.single_source_bellman_ford, G, 1)
+        pytest.raises(
+            nx.NetworkXUnbounded, nx.bellman_ford_predecessor_and_distance, G, 1
+        )
+        pytest.raises(nx.NetworkXUnbounded, nx.goldberg_radzik, G, 1)
+
+    def test_zero_cycle(self):
+        G = nx.cycle_graph(5, create_using=nx.DiGraph())
+        G.add_edge(2, 3, weight=-4)
+        # check that zero cycle doesn't raise
+        nx.goldberg_radzik(G, 1)
+        nx.bellman_ford_predecessor_and_distance(G, 1)
+
+        G.add_edge(2, 3, weight=-4.0001)
+        # check that negative cycle does raise
+        pytest.raises(
+            nx.NetworkXUnbounded, nx.bellman_ford_predecessor_and_distance, G, 1
+        )
+        pytest.raises(nx.NetworkXUnbounded, nx.goldberg_radzik, G, 1)
+
+    def test_find_negative_cycle_longer_cycle(self):
+        G = nx.cycle_graph(5, create_using=nx.DiGraph())
+        nx.add_cycle(G, [3, 5, 6, 7, 8, 9])
+        G.add_edge(1, 2, weight=-30)
+        assert nx.find_negative_cycle(G, 1) == [0, 1, 2, 3, 4, 0]
+        assert nx.find_negative_cycle(G, 7) == [2, 3, 4, 0, 1, 2]
+
+    def test_find_negative_cycle_no_cycle(self):
+        G = nx.path_graph(5, create_using=nx.DiGraph())
+        pytest.raises(nx.NetworkXError, nx.find_negative_cycle, G, 3)
+
+    def test_find_negative_cycle_single_edge(self):
+        G = nx.Graph()
+        G.add_edge(0, 1, weight=-1)
+        assert nx.find_negative_cycle(G, 1) == [1, 0, 1]
+
+    def test_negative_weight(self):
+        G = nx.cycle_graph(5, create_using=nx.DiGraph())
+        G.add_edge(1, 2, weight=-3)
+        assert nx.single_source_bellman_ford_path(G, 0) == {
+            0: [0],
+            1: [0, 1],
+            2: [0, 1, 2],
+            3: [0, 1, 2, 3],
+            4: [0, 1, 2, 3, 4],
+        }
+        assert nx.single_source_bellman_ford_path_length(G, 0) == {
+            0: 0,
+            1: 1,
+            2: -2,
+            3: -1,
+            4: 0,
+        }
+        assert nx.single_source_bellman_ford(G, 0) == (
+            {0: 0, 1: 1, 2: -2, 3: -1, 4: 0},
+            {0: [0], 1: [0, 1], 2: [0, 1, 2], 3: [0, 1, 2, 3], 4: [0, 1, 2, 3, 4]},
+        )
+        assert nx.bellman_ford_predecessor_and_distance(G, 0) == (
+            {0: [], 1: [0], 2: [1], 3: [2], 4: [3]},
+            {0: 0, 1: 1, 2: -2, 3: -1, 4: 0},
+        )
+        assert nx.goldberg_radzik(G, 0) == (
+            {0: None, 1: 0, 2: 1, 3: 2, 4: 3},
+            {0: 0, 1: 1, 2: -2, 3: -1, 4: 0},
+        )
+
+    def test_not_connected(self):
+        G = nx.complete_graph(6)
+        G.add_edge(10, 11)
+        G.add_edge(10, 12)
+        assert nx.single_source_bellman_ford_path(G, 0) == {
+            0: [0],
+            1: [0, 1],
+            2: [0, 2],
+            3: [0, 3],
+            4: [0, 4],
+            5: [0, 5],
+        }
+        assert nx.single_source_bellman_ford_path_length(G, 0) == {
+            0: 0,
+            1: 1,
+            2: 1,
+            3: 1,
+            4: 1,
+            5: 1,
+        }
+        assert nx.single_source_bellman_ford(G, 0) == (
+            {0: 0, 1: 1, 2: 1, 3: 1, 4: 1, 5: 1},
+            {0: [0], 1: [0, 1], 2: [0, 2], 3: [0, 3], 4: [0, 4], 5: [0, 5]},
+        )
+        assert nx.bellman_ford_predecessor_and_distance(G, 0) == (
+            {0: [], 1: [0], 2: [0], 3: [0], 4: [0], 5: [0]},
+            {0: 0, 1: 1, 2: 1, 3: 1, 4: 1, 5: 1},
+        )
+        assert nx.goldberg_radzik(G, 0) == (
+            {0: None, 1: 0, 2: 0, 3: 0, 4: 0, 5: 0},
+            {0: 0, 1: 1, 2: 1, 3: 1, 4: 1, 5: 1},
+        )
+
+        # not connected, with a component not containing the source that
+        # contains a negative cycle.
+        G = nx.complete_graph(6)
+        G.add_edges_from(
+            [
+                ("A", "B", {"load": 3}),
+                ("B", "C", {"load": -10}),
+                ("C", "A", {"load": 2}),
+            ]
+        )
+        assert nx.single_source_bellman_ford_path(G, 0, weight="load") == {
+            0: [0],
+            1: [0, 1],
+            2: [0, 2],
+            3: [0, 3],
+            4: [0, 4],
+            5: [0, 5],
+        }
+        assert nx.single_source_bellman_ford_path_length(G, 0, weight="load") == {
+            0: 0,
+            1: 1,
+            2: 1,
+            3: 1,
+            4: 1,
+            5: 1,
+        }
+        assert nx.single_source_bellman_ford(G, 0, weight="load") == (
+            {0: 0, 1: 1, 2: 1, 3: 1, 4: 1, 5: 1},
+            {0: [0], 1: [0, 1], 2: [0, 2], 3: [0, 3], 4: [0, 4], 5: [0, 5]},
+        )
+        assert nx.bellman_ford_predecessor_and_distance(G, 0, weight="load") == (
+            {0: [], 1: [0], 2: [0], 3: [0], 4: [0], 5: [0]},
+            {0: 0, 1: 1, 2: 1, 3: 1, 4: 1, 5: 1},
+        )
+        assert nx.goldberg_radzik(G, 0, weight="load") == (
+            {0: None, 1: 0, 2: 0, 3: 0, 4: 0, 5: 0},
+            {0: 0, 1: 1, 2: 1, 3: 1, 4: 1, 5: 1},
+        )
+
+    def test_multigraph(self):
+        assert nx.bellman_ford_path(self.MXG, "s", "v") == ["s", "x", "u", "v"]
+        assert nx.bellman_ford_path_length(self.MXG, "s", "v") == 9
+        assert nx.single_source_bellman_ford_path(self.MXG, "s")["v"] == [
+            "s",
+            "x",
+            "u",
+            "v",
+        ]
+        assert nx.single_source_bellman_ford_path_length(self.MXG, "s")["v"] == 9
+        D, P = nx.single_source_bellman_ford(self.MXG, "s", target="v")
+        assert D == 9
+        assert P == ["s", "x", "u", "v"]
+        P, D = nx.bellman_ford_predecessor_and_distance(self.MXG, "s")
+        assert P["v"] == ["u"]
+        assert D["v"] == 9
+        P, D = nx.goldberg_radzik(self.MXG, "s")
+        assert P["v"] == "u"
+        assert D["v"] == 9
+        assert nx.bellman_ford_path(self.MXG4, 0, 2) == [0, 1, 2]
+        assert nx.bellman_ford_path_length(self.MXG4, 0, 2) == 4
+        assert nx.single_source_bellman_ford_path(self.MXG4, 0)[2] == [0, 1, 2]
+        assert nx.single_source_bellman_ford_path_length(self.MXG4, 0)[2] == 4
+        D, P = nx.single_source_bellman_ford(self.MXG4, 0, target=2)
+        assert D == 4
+        assert P == [0, 1, 2]
+        P, D = nx.bellman_ford_predecessor_and_distance(self.MXG4, 0)
+        assert P[2] == [1]
+        assert D[2] == 4
+        P, D = nx.goldberg_radzik(self.MXG4, 0)
+        assert P[2] == 1
+        assert D[2] == 4
+
+    def test_others(self):
+        assert nx.bellman_ford_path(self.XG, "s", "v") == ["s", "x", "u", "v"]
+        assert nx.bellman_ford_path_length(self.XG, "s", "v") == 9
+        assert nx.single_source_bellman_ford_path(self.XG, "s")["v"] == [
+            "s",
+            "x",
+            "u",
+            "v",
+        ]
+        assert nx.single_source_bellman_ford_path_length(self.XG, "s")["v"] == 9
+        D, P = nx.single_source_bellman_ford(self.XG, "s", target="v")
+        assert D == 9
+        assert P == ["s", "x", "u", "v"]
+        (P, D) = nx.bellman_ford_predecessor_and_distance(self.XG, "s")
+        assert P["v"] == ["u"]
+        assert D["v"] == 9
+        (P, D) = nx.goldberg_radzik(self.XG, "s")
+        assert P["v"] == "u"
+        assert D["v"] == 9
+
+    def test_path_graph(self):
+        G = nx.path_graph(4)
+        assert nx.single_source_bellman_ford_path(G, 0) == {
+            0: [0],
+            1: [0, 1],
+            2: [0, 1, 2],
+            3: [0, 1, 2, 3],
+        }
+        assert nx.single_source_bellman_ford_path_length(G, 0) == {
+            0: 0,
+            1: 1,
+            2: 2,
+            3: 3,
+        }
+        assert nx.single_source_bellman_ford(G, 0) == (
+            {0: 0, 1: 1, 2: 2, 3: 3},
+            {0: [0], 1: [0, 1], 2: [0, 1, 2], 3: [0, 1, 2, 3]},
+        )
+        assert nx.bellman_ford_predecessor_and_distance(G, 0) == (
+            {0: [], 1: [0], 2: [1], 3: [2]},
+            {0: 0, 1: 1, 2: 2, 3: 3},
+        )
+        assert nx.goldberg_radzik(G, 0) == (
+            {0: None, 1: 0, 2: 1, 3: 2},
+            {0: 0, 1: 1, 2: 2, 3: 3},
+        )
+        assert nx.single_source_bellman_ford_path(G, 3) == {
+            0: [3, 2, 1, 0],
+            1: [3, 2, 1],
+            2: [3, 2],
+            3: [3],
+        }
+        assert nx.single_source_bellman_ford_path_length(G, 3) == {
+            0: 3,
+            1: 2,
+            2: 1,
+            3: 0,
+        }
+        assert nx.single_source_bellman_ford(G, 3) == (
+            {0: 3, 1: 2, 2: 1, 3: 0},
+            {0: [3, 2, 1, 0], 1: [3, 2, 1], 2: [3, 2], 3: [3]},
+        )
+        assert nx.bellman_ford_predecessor_and_distance(G, 3) == (
+            {0: [1], 1: [2], 2: [3], 3: []},
+            {0: 3, 1: 2, 2: 1, 3: 0},
+        )
+        assert nx.goldberg_radzik(G, 3) == (
+            {0: 1, 1: 2, 2: 3, 3: None},
+            {0: 3, 1: 2, 2: 1, 3: 0},
+        )
+
+    def test_4_cycle(self):
+        # 4-cycle
+        G = nx.Graph([(0, 1), (1, 2), (2, 3), (3, 0)])
+        dist, path = nx.single_source_bellman_ford(G, 0)
+        assert dist == {0: 0, 1: 1, 2: 2, 3: 1}
+        assert path[0] == [0]
+        assert path[1] == [0, 1]
+        assert path[2] in [[0, 1, 2], [0, 3, 2]]
+        assert path[3] == [0, 3]
+
+        pred, dist = nx.bellman_ford_predecessor_and_distance(G, 0)
+        assert pred[0] == []
+        assert pred[1] == [0]
+        assert pred[2] in [[1, 3], [3, 1]]
+        assert pred[3] == [0]
+        assert dist == {0: 0, 1: 1, 2: 2, 3: 1}
+
+        pred, dist = nx.goldberg_radzik(G, 0)
+        assert pred[0] is None
+        assert pred[1] == 0
+        assert pred[2] in [1, 3]
+        assert pred[3] == 0
+        assert dist == {0: 0, 1: 1, 2: 2, 3: 1}
+
+    def test_negative_weight_bf_path(self):
+        G = nx.DiGraph()
+        G.add_nodes_from("abcd")
+        G.add_edge("a", "d", weight=0)
+        G.add_edge("a", "b", weight=1)
+        G.add_edge("b", "c", weight=-3)
+        G.add_edge("c", "d", weight=1)
+
+        assert nx.bellman_ford_path(G, "a", "d") == ["a", "b", "c", "d"]
+        assert nx.bellman_ford_path_length(G, "a", "d") == -1
+
+    def test_zero_cycle_smoke(self):
+        D = nx.DiGraph()
+        D.add_weighted_edges_from([(0, 1, 1), (1, 2, 1), (2, 3, 1), (3, 1, -2)])
+
+        nx.bellman_ford_path(D, 1, 3)
+        nx.dijkstra_path(D, 1, 3)
+        nx.bidirectional_dijkstra(D, 1, 3)
+        # FIXME nx.goldberg_radzik(D, 1)
+
+
+class TestJohnsonAlgorithm(WeightedTestBase):
+    def test_single_node_graph(self):
+        G = nx.DiGraph()
+        G.add_node(0)
+        assert nx.johnson(G) == {0: {0: [0]}}
+
+    def test_negative_cycle(self):
+        G = nx.DiGraph()
+        G.add_weighted_edges_from(
+            [
+                ("0", "3", 3),
+                ("0", "1", -5),
+                ("1", "0", -5),
+                ("0", "2", 2),
+                ("1", "2", 4),
+                ("2", "3", 1),
+            ]
+        )
+        pytest.raises(nx.NetworkXUnbounded, nx.johnson, G)
+        G = nx.Graph()
+        G.add_weighted_edges_from(
+            [
+                ("0", "3", 3),
+                ("0", "1", -5),
+                ("1", "0", -5),
+                ("0", "2", 2),
+                ("1", "2", 4),
+                ("2", "3", 1),
+            ]
+        )
+        pytest.raises(nx.NetworkXUnbounded, nx.johnson, G)
+
+    def test_negative_weights(self):
+        G = nx.DiGraph()
+        G.add_weighted_edges_from(
+            [("0", "3", 3), ("0", "1", -5), ("0", "2", 2), ("1", "2", 4), ("2", "3", 1)]
+        )
+        paths = nx.johnson(G)
+        assert paths == {
+            "1": {"1": ["1"], "3": ["1", "2", "3"], "2": ["1", "2"]},
+            "0": {
+                "1": ["0", "1"],
+                "0": ["0"],
+                "3": ["0", "1", "2", "3"],
+                "2": ["0", "1", "2"],
+            },
+            "3": {"3": ["3"]},
+            "2": {"3": ["2", "3"], "2": ["2"]},
+        }
+
+    def test_unweighted_graph(self):
+        G = nx.Graph()
+        G.add_edges_from([(1, 0), (2, 1)])
+        H = G.copy()
+        nx.set_edge_attributes(H, values=1, name="weight")
+        assert nx.johnson(G) == nx.johnson(H)
+
+    def test_partially_weighted_graph_with_negative_edges(self):
+        G = nx.DiGraph()
+        G.add_edges_from([(0, 1), (1, 2), (2, 0), (1, 0)])
+        G[1][0]["weight"] = -2
+        G[0][1]["weight"] = 3
+        G[1][2]["weight"] = -4
+
+        H = G.copy()
+        H[2][0]["weight"] = 1
+
+        I = G.copy()
+        I[2][0]["weight"] = 8
+
+        assert nx.johnson(G) == nx.johnson(H)
+        assert nx.johnson(G) != nx.johnson(I)
+
+    def test_graphs(self):
+        validate_path(self.XG, "s", "v", 9, nx.johnson(self.XG)["s"]["v"])
+        validate_path(self.MXG, "s", "v", 9, nx.johnson(self.MXG)["s"]["v"])
+        validate_path(self.XG2, 1, 3, 4, nx.johnson(self.XG2)[1][3])
+        validate_path(self.XG3, 0, 3, 15, nx.johnson(self.XG3)[0][3])
+        validate_path(self.XG4, 0, 2, 4, nx.johnson(self.XG4)[0][2])
+        validate_path(self.MXG4, 0, 2, 4, nx.johnson(self.MXG4)[0][2])
diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/shortest_paths/unweighted.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/shortest_paths/unweighted.py
new file mode 100644
index 00000000..3aeef854
--- /dev/null
+++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/shortest_paths/unweighted.py
@@ -0,0 +1,579 @@
+"""
+Shortest path algorithms for unweighted graphs.
+"""
+
+import warnings
+
+import networkx as nx
+
+__all__ = [
+    "bidirectional_shortest_path",
+    "single_source_shortest_path",
+    "single_source_shortest_path_length",
+    "single_target_shortest_path",
+    "single_target_shortest_path_length",
+    "all_pairs_shortest_path",
+    "all_pairs_shortest_path_length",
+    "predecessor",
+]
+
+
+@nx._dispatchable
+def single_source_shortest_path_length(G, source, cutoff=None):
+    """Compute the shortest path lengths from source to all reachable nodes.
+
+    Parameters
+    ----------
+    G : NetworkX graph
+
+    source : node
+       Starting node for path
+
+    cutoff : integer, optional
+        Depth to stop the search. Only paths of length <= cutoff are returned.
+
+    Returns
+    -------
+    lengths : dict
+        Dict keyed by node to shortest path length to source.
+
+    Examples
+    --------
+    >>> G = nx.path_graph(5)
+    >>> length = nx.single_source_shortest_path_length(G, 0)
+    >>> length[4]
+    4
+    >>> for node in length:
+    ...     print(f"{node}: {length[node]}")
+    0: 0
+    1: 1
+    2: 2
+    3: 3
+    4: 4
+
+    See Also
+    --------
+    shortest_path_length
+    """
+    if source not in G:
+        raise nx.NodeNotFound(f"Source {source} is not in G")
+    if cutoff is None:
+        cutoff = float("inf")
+    nextlevel = [source]
+    return dict(_single_shortest_path_length(G._adj, nextlevel, cutoff))
+
+
+def _single_shortest_path_length(adj, firstlevel, cutoff):
+    """Yields (node, level) in a breadth first search
+
+    Shortest Path Length helper function
+    Parameters
+    ----------
+        adj : dict
+            Adjacency dict or view
+        firstlevel : list
+            starting nodes, e.g. [source] or [target]
+        cutoff : int or float
+            level at which we stop the process
+    """
+    seen = set(firstlevel)
+    nextlevel = firstlevel
+    level = 0
+    n = len(adj)
+    for v in nextlevel:
+        yield (v, level)
+    while nextlevel and cutoff > level:
+        level += 1
+        thislevel = nextlevel
+        nextlevel = []
+        for v in thislevel:
+            for w in adj[v]:
+                if w not in seen:
+                    seen.add(w)
+                    nextlevel.append(w)
+                    yield (w, level)
+            if len(seen) == n:
+                return
+
+
+@nx._dispatchable
+def single_target_shortest_path_length(G, target, cutoff=None):
+    """Compute the shortest path lengths to target from all reachable nodes.
+
+    Parameters
+    ----------
+    G : NetworkX graph
+
+    target : node
+       Target node for path
+
+    cutoff : integer, optional
+        Depth to stop the search. Only paths of length <= cutoff are returned.
+
+    Returns
+    -------
+    lengths : iterator
+        (source, shortest path length) iterator
+
+    Examples
+    --------
+    >>> G = nx.path_graph(5, create_using=nx.DiGraph())
+    >>> length = dict(nx.single_target_shortest_path_length(G, 4))
+    >>> length[0]
+    4
+    >>> for node in range(5):
+    ...     print(f"{node}: {length[node]}")
+    0: 4
+    1: 3
+    2: 2
+    3: 1
+    4: 0
+
+    See Also
+    --------
+    single_source_shortest_path_length, shortest_path_length
+    """
+    if target not in G:
+        raise nx.NodeNotFound(f"Target {target} is not in G")
+
+    warnings.warn(
+        (
+            "\n\nsingle_target_shortest_path_length will return a dict instead of"
+            "\nan iterator in version 3.5"
+        ),
+        FutureWarning,
+        stacklevel=3,
+    )
+
+    if cutoff is None:
+        cutoff = float("inf")
+    # handle either directed or undirected
+    adj = G._pred if G.is_directed() else G._adj
+    nextlevel = [target]
+    # for version 3.3 we will return a dict like this:
+    # return dict(_single_shortest_path_length(adj, nextlevel, cutoff))
+    return _single_shortest_path_length(adj, nextlevel, cutoff)
+
+
+@nx._dispatchable
+def all_pairs_shortest_path_length(G, cutoff=None):
+    """Computes the shortest path lengths between all nodes in `G`.
+
+    Parameters
+    ----------
+    G : NetworkX graph
+
+    cutoff : integer, optional
+        Depth at which to stop the search. Only paths of length at most
+        `cutoff` are returned.
+
+    Returns
+    -------
+    lengths : iterator
+        (source, dictionary) iterator with dictionary keyed by target and
+        shortest path length as the key value.
+
+    Notes
+    -----
+    The iterator returned only has reachable node pairs.
+
+    Examples
+    --------
+    >>> G = nx.path_graph(5)
+    >>> length = dict(nx.all_pairs_shortest_path_length(G))
+    >>> for node in [0, 1, 2, 3, 4]:
+    ...     print(f"1 - {node}: {length[1][node]}")
+    1 - 0: 1
+    1 - 1: 0
+    1 - 2: 1
+    1 - 3: 2
+    1 - 4: 3
+    >>> length[3][2]
+    1
+    >>> length[2][2]
+    0
+
+    """
+    length = single_source_shortest_path_length
+    # TODO This can be trivially parallelized.
+    for n in G:
+        yield (n, length(G, n, cutoff=cutoff))
+
+
+@nx._dispatchable
+def bidirectional_shortest_path(G, source, target):
+    """Returns a list of nodes in a shortest path between source and target.
+
+    Parameters
+    ----------
+    G : NetworkX graph
+
+    source : node label
+       starting node for path
+
+    target : node label
+       ending node for path
+
+    Returns
+    -------
+    path: list
+       List of nodes in a path from source to target.
+
+    Raises
+    ------
+    NetworkXNoPath
+       If no path exists between source and target.
+
+    Examples
+    --------
+    >>> G = nx.Graph()
+    >>> nx.add_path(G, [0, 1, 2, 3, 0, 4, 5, 6, 7, 4])
+    >>> nx.bidirectional_shortest_path(G, 2, 6)
+    [2, 1, 0, 4, 5, 6]
+
+    See Also
+    --------
+    shortest_path
+
+    Notes
+    -----
+    This algorithm is used by shortest_path(G, source, target).
+    """
+
+    if source not in G:
+        raise nx.NodeNotFound(f"Source {source} is not in G")
+
+    if target not in G:
+        raise nx.NodeNotFound(f"Target {target} is not in G")
+
+    # call helper to do the real work
+    results = _bidirectional_pred_succ(G, source, target)
+    pred, succ, w = results
+
+    # build path from pred+w+succ
+    path = []
+    # from source to w
+    while w is not None:
+        path.append(w)
+        w = pred[w]
+    path.reverse()
+    # from w to target
+    w = succ[path[-1]]
+    while w is not None:
+        path.append(w)
+        w = succ[w]
+
+    return path
+
+
+def _bidirectional_pred_succ(G, source, target):
+    """Bidirectional shortest path helper.
+
+    Returns (pred, succ, w) where
+    pred is a dictionary of predecessors from w to the source, and
+    succ is a dictionary of successors from w to the target.
+    """
+    # does BFS from both source and target and meets in the middle
+    if target == source:
+        return ({target: None}, {source: None}, source)
+
+    # handle either directed or undirected
+    if G.is_directed():
+        Gpred = G.pred
+        Gsucc = G.succ
+    else:
+        Gpred = G.adj
+        Gsucc = G.adj
+
+    # predecessor and successors in search
+    pred = {source: None}
+    succ = {target: None}
+
+    # initialize fringes, start with forward
+    forward_fringe = [source]
+    reverse_fringe = [target]
+
+    while forward_fringe and reverse_fringe:
+        if len(forward_fringe) <= len(reverse_fringe):
+            this_level = forward_fringe
+            forward_fringe = []
+            for v in this_level:
+                for w in Gsucc[v]:
+                    if w not in pred:
+                        forward_fringe.append(w)
+                        pred[w] = v
+                    if w in succ:  # path found
+                        return pred, succ, w
+        else:
+            this_level = reverse_fringe
+            reverse_fringe = []
+            for v in this_level:
+                for w in Gpred[v]:
+                    if w not in succ:
+                        succ[w] = v
+                        reverse_fringe.append(w)
+                    if w in pred:  # found path
+                        return pred, succ, w
+
+    raise nx.NetworkXNoPath(f"No path between {source} and {target}.")
+
+
+@nx._dispatchable
+def single_source_shortest_path(G, source, cutoff=None):
+    """Compute shortest path between source
+    and all other nodes reachable from source.
+
+    Parameters
+    ----------
+    G : NetworkX graph
+
+    source : node label
+       Starting node for path
+
+    cutoff : integer, optional
+        Depth to stop the search. Only paths of length <= cutoff are returned.
+
+    Returns
+    -------
+    paths : dictionary
+        Dictionary, keyed by target, of shortest paths.
+
+    Examples
+    --------
+    >>> G = nx.path_graph(5)
+    >>> path = nx.single_source_shortest_path(G, 0)
+    >>> path[4]
+    [0, 1, 2, 3, 4]
+
+    Notes
+    -----
+    The shortest path is not necessarily unique. So there can be multiple
+    paths between the source and each target node, all of which have the
+    same 'shortest' length. For each target node, this function returns
+    only one of those paths.
+
+    See Also
+    --------
+    shortest_path
+    """
+    if source not in G:
+        raise nx.NodeNotFound(f"Source {source} not in G")
+
+    def join(p1, p2):
+        return p1 + p2
+
+    if cutoff is None:
+        cutoff = float("inf")
+    nextlevel = {source: 1}  # list of nodes to check at next level
+    paths = {source: [source]}  # paths dictionary  (paths to key from source)
+    return dict(_single_shortest_path(G.adj, nextlevel, paths, cutoff, join))
+
+
+def _single_shortest_path(adj, firstlevel, paths, cutoff, join):
+    """Returns shortest paths
+
+    Shortest Path helper function
+    Parameters
+    ----------
+        adj : dict
+            Adjacency dict or view
+        firstlevel : dict
+            starting nodes, e.g. {source: 1} or {target: 1}
+        paths : dict
+            paths for starting nodes, e.g. {source: [source]}
+        cutoff : int or float
+            level at which we stop the process
+        join : function
+            function to construct a path from two partial paths. Requires two
+            list inputs `p1` and `p2`, and returns a list. Usually returns
+            `p1 + p2` (forward from source) or `p2 + p1` (backward from target)
+    """
+    level = 0  # the current level
+    nextlevel = firstlevel
+    while nextlevel and cutoff > level:
+        thislevel = nextlevel
+        nextlevel = {}
+        for v in thislevel:
+            for w in adj[v]:
+                if w not in paths:
+                    paths[w] = join(paths[v], [w])
+                    nextlevel[w] = 1
+        level += 1
+    return paths
+
+
+@nx._dispatchable
+def single_target_shortest_path(G, target, cutoff=None):
+    """Compute shortest path to target from all nodes that reach target.
+
+    Parameters
+    ----------
+    G : NetworkX graph
+
+    target : node label
+       Target node for path
+
+    cutoff : integer, optional
+        Depth to stop the search. Only paths of length <= cutoff are returned.
+
+    Returns
+    -------
+    paths : dictionary
+        Dictionary, keyed by target, of shortest paths.
+
+    Examples
+    --------
+    >>> G = nx.path_graph(5, create_using=nx.DiGraph())
+    >>> path = nx.single_target_shortest_path(G, 4)
+    >>> path[0]
+    [0, 1, 2, 3, 4]
+
+    Notes
+    -----
+    The shortest path is not necessarily unique. So there can be multiple
+    paths between the source and each target node, all of which have the
+    same 'shortest' length. For each target node, this function returns
+    only one of those paths.
+
+    See Also
+    --------
+    shortest_path, single_source_shortest_path
+    """
+    if target not in G:
+        raise nx.NodeNotFound(f"Target {target} not in G")
+
+    def join(p1, p2):
+        return p2 + p1
+
+    # handle undirected graphs
+    adj = G.pred if G.is_directed() else G.adj
+    if cutoff is None:
+        cutoff = float("inf")
+    nextlevel = {target: 1}  # list of nodes to check at next level
+    paths = {target: [target]}  # paths dictionary  (paths to key from source)
+    return dict(_single_shortest_path(adj, nextlevel, paths, cutoff, join))
+
+
+@nx._dispatchable
+def all_pairs_shortest_path(G, cutoff=None):
+    """Compute shortest paths between all nodes.
+
+    Parameters
+    ----------
+    G : NetworkX graph
+
+    cutoff : integer, optional
+        Depth at which to stop the search. Only paths of length at most
+        `cutoff` are returned.
+
+    Returns
+    -------
+    paths : iterator
+        Dictionary, keyed by source and target, of shortest paths.
+
+    Examples
+    --------
+    >>> G = nx.path_graph(5)
+    >>> path = dict(nx.all_pairs_shortest_path(G))
+    >>> print(path[0][4])
+    [0, 1, 2, 3, 4]
+
+    Notes
+    -----
+    There may be multiple shortest paths with the same length between
+    two nodes. For each pair, this function returns only one of those paths.
+
+    See Also
+    --------
+    floyd_warshall
+    all_pairs_all_shortest_paths
+
+    """
+    # TODO This can be trivially parallelized.
+    for n in G:
+        yield (n, single_source_shortest_path(G, n, cutoff=cutoff))
+
+
+@nx._dispatchable
+def predecessor(G, source, target=None, cutoff=None, return_seen=None):
+    """Returns dict of predecessors for the path from source to all nodes in G.
+
+    Parameters
+    ----------
+    G : NetworkX graph
+
+    source : node label
+       Starting node for path
+
+    target : node label, optional
+       Ending node for path. If provided only predecessors between
+       source and target are returned
+
+    cutoff : integer, optional
+        Depth to stop the search. Only paths of length <= cutoff are returned.
+
+    return_seen : bool, optional (default=None)
+        Whether to return a dictionary, keyed by node, of the level (number of
+        hops) to reach the node (as seen during breadth-first-search).
+
+    Returns
+    -------
+    pred : dictionary
+        Dictionary, keyed by node, of predecessors in the shortest path.
+
+
+    (pred, seen): tuple of dictionaries
+        If `return_seen` argument is set to `True`, then a tuple of dictionaries
+        is returned. The first element is the dictionary, keyed by node, of
+        predecessors in the shortest path. The second element is the dictionary,
+        keyed by node, of the level (number of hops) to reach the node (as seen
+        during breadth-first-search).
+
+    Examples
+    --------
+    >>> G = nx.path_graph(4)
+    >>> list(G)
+    [0, 1, 2, 3]
+    >>> nx.predecessor(G, 0)
+    {0: [], 1: [0], 2: [1], 3: [2]}
+    >>> nx.predecessor(G, 0, return_seen=True)
+    ({0: [], 1: [0], 2: [1], 3: [2]}, {0: 0, 1: 1, 2: 2, 3: 3})
+
+
+    """
+    if source not in G:
+        raise nx.NodeNotFound(f"Source {source} not in G")
+
+    level = 0  # the current level
+    nextlevel = [source]  # list of nodes to check at next level
+    seen = {source: level}  # level (number of hops) when seen in BFS
+    pred = {source: []}  # predecessor dictionary
+    while nextlevel:
+        level = level + 1
+        thislevel = nextlevel
+        nextlevel = []
+        for v in thislevel:
+            for w in G[v]:
+                if w not in seen:
+                    pred[w] = [v]
+                    seen[w] = level
+                    nextlevel.append(w)
+                elif seen[w] == level:  # add v to predecessor list if it
+                    pred[w].append(v)  # is at the correct level
+        if cutoff and cutoff <= level:
+            break
+
+    if target is not None:
+        if return_seen:
+            if target not in pred:
+                return ([], -1)  # No predecessor
+            return (pred[target], seen[target])
+        else:
+            if target not in pred:
+                return []  # No predecessor
+            return pred[target]
+    else:
+        if return_seen:
+            return (pred, seen)
+        else:
+            return pred
diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/shortest_paths/weighted.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/shortest_paths/weighted.py
new file mode 100644
index 00000000..f8421d42
--- /dev/null
+++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/shortest_paths/weighted.py
@@ -0,0 +1,2520 @@
+"""
+Shortest path algorithms for weighted graphs.
+"""
+
+from collections import deque
+from heapq import heappop, heappush
+from itertools import count
+
+import networkx as nx
+from networkx.algorithms.shortest_paths.generic import _build_paths_from_predecessors
+
+__all__ = [
+    "dijkstra_path",
+    "dijkstra_path_length",
+    "bidirectional_dijkstra",
+    "single_source_dijkstra",
+    "single_source_dijkstra_path",
+    "single_source_dijkstra_path_length",
+    "multi_source_dijkstra",
+    "multi_source_dijkstra_path",
+    "multi_source_dijkstra_path_length",
+    "all_pairs_dijkstra",
+    "all_pairs_dijkstra_path",
+    "all_pairs_dijkstra_path_length",
+    "dijkstra_predecessor_and_distance",
+    "bellman_ford_path",
+    "bellman_ford_path_length",
+    "single_source_bellman_ford",
+    "single_source_bellman_ford_path",
+    "single_source_bellman_ford_path_length",
+    "all_pairs_bellman_ford_path",
+    "all_pairs_bellman_ford_path_length",
+    "bellman_ford_predecessor_and_distance",
+    "negative_edge_cycle",
+    "find_negative_cycle",
+    "goldberg_radzik",
+    "johnson",
+]
+
+
+def _weight_function(G, weight):
+    """Returns a function that returns the weight of an edge.
+
+    The returned function is specifically suitable for input to
+    functions :func:`_dijkstra` and :func:`_bellman_ford_relaxation`.
+
+    Parameters
+    ----------
+    G : NetworkX graph.
+
+    weight : string or function
+        If it is callable, `weight` itself is returned. If it is a string,
+        it is assumed to be the name of the edge attribute that represents
+        the weight of an edge. In that case, a function is returned that
+        gets the edge weight according to the specified edge attribute.
+
+    Returns
+    -------
+    function
+        This function returns a callable that accepts exactly three inputs:
+        a node, an node adjacent to the first one, and the edge attribute
+        dictionary for the eedge joining those nodes. That function returns
+        a number representing the weight of an edge.
+
+    If `G` is a multigraph, and `weight` is not callable, the
+    minimum edge weight over all parallel edges is returned. If any edge
+    does not have an attribute with key `weight`, it is assumed to
+    have weight one.
+
+    """
+    if callable(weight):
+        return weight
+    # If the weight keyword argument is not callable, we assume it is a
+    # string representing the edge attribute containing the weight of
+    # the edge.
+    if G.is_multigraph():
+        return lambda u, v, d: min(attr.get(weight, 1) for attr in d.values())
+    return lambda u, v, data: data.get(weight, 1)
+
+
+@nx._dispatchable(edge_attrs="weight")
+def dijkstra_path(G, source, target, weight="weight"):
+    """Returns the shortest weighted path from source to target in G.
+
+    Uses Dijkstra's Method to compute the shortest weighted path
+    between two nodes in a graph.
+
+    Parameters
+    ----------
+    G : NetworkX graph
+
+    source : node
+        Starting node
+
+    target : node
+        Ending node
+
+    weight : string or function
+        If this is a string, then edge weights will be accessed via the
+        edge attribute with this key (that is, the weight of the edge
+        joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
+        such edge attribute exists, the weight of the edge is assumed to
+        be one.
+
+        If this is a function, the weight of an edge is the value
+        returned by the function. The function must accept exactly three
+        positional arguments: the two endpoints of an edge and the
+        dictionary of edge attributes for that edge. The function must
+        return a number or None to indicate a hidden edge.
+
+    Returns
+    -------
+    path : list
+        List of nodes in a shortest path.
+
+    Raises
+    ------
+    NodeNotFound
+        If `source` is not in `G`.
+
+    NetworkXNoPath
+        If no path exists between source and target.
+
+    Examples
+    --------
+    >>> G = nx.path_graph(5)
+    >>> print(nx.dijkstra_path(G, 0, 4))
+    [0, 1, 2, 3, 4]
+
+    Find edges of shortest path in Multigraph
+
+    >>> G = nx.MultiDiGraph()
+    >>> G.add_weighted_edges_from([(1, 2, 0.75), (1, 2, 0.5), (2, 3, 0.5), (1, 3, 1.5)])
+    >>> nodes = nx.dijkstra_path(G, 1, 3)
+    >>> edges = nx.utils.pairwise(nodes)
+    >>> list(
+    ...     (u, v, min(G[u][v], key=lambda k: G[u][v][k].get("weight", 1)))
+    ...     for u, v in edges
+    ... )
+    [(1, 2, 1), (2, 3, 0)]
+
+    Notes
+    -----
+    Edge weight attributes must be numerical.
+    Distances are calculated as sums of weighted edges traversed.
+
+    The weight function can be used to hide edges by returning None.
+    So ``weight = lambda u, v, d: 1 if d['color']=="red" else None``
+    will find the shortest red path.
+
+    The weight function can be used to include node weights.
+
+    >>> def func(u, v, d):
+    ...     node_u_wt = G.nodes[u].get("node_weight", 1)
+    ...     node_v_wt = G.nodes[v].get("node_weight", 1)
+    ...     edge_wt = d.get("weight", 1)
+    ...     return node_u_wt / 2 + node_v_wt / 2 + edge_wt
+
+    In this example we take the average of start and end node
+    weights of an edge and add it to the weight of the edge.
+
+    The function :func:`single_source_dijkstra` computes both
+    path and length-of-path if you need both, use that.
+
+    See Also
+    --------
+    bidirectional_dijkstra
+    bellman_ford_path
+    single_source_dijkstra
+    """
+    (length, path) = single_source_dijkstra(G, source, target=target, weight=weight)
+    return path
+
+
+@nx._dispatchable(edge_attrs="weight")
+def dijkstra_path_length(G, source, target, weight="weight"):
+    """Returns the shortest weighted path length in G from source to target.
+
+    Uses Dijkstra's Method to compute the shortest weighted path length
+    between two nodes in a graph.
+
+    Parameters
+    ----------
+    G : NetworkX graph
+
+    source : node label
+        starting node for path
+
+    target : node label
+        ending node for path
+
+    weight : string or function
+        If this is a string, then edge weights will be accessed via the
+        edge attribute with this key (that is, the weight of the edge
+        joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
+        such edge attribute exists, the weight of the edge is assumed to
+        be one.
+
+        If this is a function, the weight of an edge is the value
+        returned by the function. The function must accept exactly three
+        positional arguments: the two endpoints of an edge and the
+        dictionary of edge attributes for that edge. The function must
+        return a number or None to indicate a hidden edge.
+
+    Returns
+    -------
+    length : number
+        Shortest path length.
+
+    Raises
+    ------
+    NodeNotFound
+        If `source` is not in `G`.
+
+    NetworkXNoPath
+        If no path exists between source and target.
+
+    Examples
+    --------
+    >>> G = nx.path_graph(5)
+    >>> nx.dijkstra_path_length(G, 0, 4)
+    4
+
+    Notes
+    -----
+    Edge weight attributes must be numerical.
+    Distances are calculated as sums of weighted edges traversed.
+
+    The weight function can be used to hide edges by returning None.
+    So ``weight = lambda u, v, d: 1 if d['color']=="red" else None``
+    will find the shortest red path.
+
+    The function :func:`single_source_dijkstra` computes both
+    path and length-of-path if you need both, use that.
+
+    See Also
+    --------
+    bidirectional_dijkstra
+    bellman_ford_path_length
+    single_source_dijkstra
+
+    """
+    if source not in G:
+        raise nx.NodeNotFound(f"Node {source} not found in graph")
+    if source == target:
+        return 0
+    weight = _weight_function(G, weight)
+    length = _dijkstra(G, source, weight, target=target)
+    try:
+        return length[target]
+    except KeyError as err:
+        raise nx.NetworkXNoPath(f"Node {target} not reachable from {source}") from err
+
+
+@nx._dispatchable(edge_attrs="weight")
+def single_source_dijkstra_path(G, source, cutoff=None, weight="weight"):
+    """Find shortest weighted paths in G from a source node.
+
+    Compute shortest path between source and all other reachable
+    nodes for a weighted graph.
+
+    Parameters
+    ----------
+    G : NetworkX graph
+
+    source : node
+        Starting node for path.
+
+    cutoff : integer or float, optional
+        Length (sum of edge weights) at which the search is stopped.
+        If cutoff is provided, only return paths with summed weight <= cutoff.
+
+    weight : string or function
+        If this is a string, then edge weights will be accessed via the
+        edge attribute with this key (that is, the weight of the edge
+        joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
+        such edge attribute exists, the weight of the edge is assumed to
+        be one.
+
+        If this is a function, the weight of an edge is the value
+        returned by the function. The function must accept exactly three
+        positional arguments: the two endpoints of an edge and the
+        dictionary of edge attributes for that edge. The function must
+        return a number or None to indicate a hidden edge.
+
+    Returns
+    -------
+    paths : dictionary
+        Dictionary of shortest path lengths keyed by target.
+
+    Raises
+    ------
+    NodeNotFound
+        If `source` is not in `G`.
+
+    Examples
+    --------
+    >>> G = nx.path_graph(5)
+    >>> path = nx.single_source_dijkstra_path(G, 0)
+    >>> path[4]
+    [0, 1, 2, 3, 4]
+
+    Notes
+    -----
+    Edge weight attributes must be numerical.
+    Distances are calculated as sums of weighted edges traversed.
+
+    The weight function can be used to hide edges by returning None.
+    So ``weight = lambda u, v, d: 1 if d['color']=="red" else None``
+    will find the shortest red path.
+
+    See Also
+    --------
+    single_source_dijkstra, single_source_bellman_ford
+
+    """
+    return multi_source_dijkstra_path(G, {source}, cutoff=cutoff, weight=weight)
+
+
+@nx._dispatchable(edge_attrs="weight")
+def single_source_dijkstra_path_length(G, source, cutoff=None, weight="weight"):
+    """Find shortest weighted path lengths in G from a source node.
+
+    Compute the shortest path length between source and all other
+    reachable nodes for a weighted graph.
+
+    Parameters
+    ----------
+    G : NetworkX graph
+
+    source : node label
+        Starting node for path
+
+    cutoff : integer or float, optional
+        Length (sum of edge weights) at which the search is stopped.
+        If cutoff is provided, only return paths with summed weight <= cutoff.
+
+    weight : string or function
+        If this is a string, then edge weights will be accessed via the
+        edge attribute with this key (that is, the weight of the edge
+        joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
+        such edge attribute exists, the weight of the edge is assumed to
+        be one.
+
+        If this is a function, the weight of an edge is the value
+        returned by the function. The function must accept exactly three
+        positional arguments: the two endpoints of an edge and the
+        dictionary of edge attributes for that edge. The function must
+        return a number or None to indicate a hidden edge.
+
+    Returns
+    -------
+    length : dict
+        Dict keyed by node to shortest path length from source.
+
+    Raises
+    ------
+    NodeNotFound
+        If `source` is not in `G`.
+
+    Examples
+    --------
+    >>> G = nx.path_graph(5)
+    >>> length = nx.single_source_dijkstra_path_length(G, 0)
+    >>> length[4]
+    4
+    >>> for node in [0, 1, 2, 3, 4]:
+    ...     print(f"{node}: {length[node]}")
+    0: 0
+    1: 1
+    2: 2
+    3: 3
+    4: 4
+
+    Notes
+    -----
+    Edge weight attributes must be numerical.
+    Distances are calculated as sums of weighted edges traversed.
+
+    The weight function can be used to hide edges by returning None.
+    So ``weight = lambda u, v, d: 1 if d['color']=="red" else None``
+    will find the shortest red path.
+
+    See Also
+    --------
+    single_source_dijkstra, single_source_bellman_ford_path_length
+
+    """
+    return multi_source_dijkstra_path_length(G, {source}, cutoff=cutoff, weight=weight)
+
+
+@nx._dispatchable(edge_attrs="weight")
+def single_source_dijkstra(G, source, target=None, cutoff=None, weight="weight"):
+    """Find shortest weighted paths and lengths from a source node.
+
+    Compute the shortest path length between source and all other
+    reachable nodes for a weighted graph.
+
+    Uses Dijkstra's algorithm to compute shortest paths and lengths
+    between a source and all other reachable nodes in a weighted graph.
+
+    Parameters
+    ----------
+    G : NetworkX graph
+
+    source : node label
+        Starting node for path
+
+    target : node label, optional
+        Ending node for path
+
+    cutoff : integer or float, optional
+        Length (sum of edge weights) at which the search is stopped.
+        If cutoff is provided, only return paths with summed weight <= cutoff.
+
+
+    weight : string or function
+        If this is a string, then edge weights will be accessed via the
+        edge attribute with this key (that is, the weight of the edge
+        joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
+        such edge attribute exists, the weight of the edge is assumed to
+        be one.
+
+        If this is a function, the weight of an edge is the value
+        returned by the function. The function must accept exactly three
+        positional arguments: the two endpoints of an edge and the
+        dictionary of edge attributes for that edge. The function must
+        return a number or None to indicate a hidden edge.
+
+    Returns
+    -------
+    distance, path : pair of dictionaries, or numeric and list.
+        If target is None, paths and lengths to all nodes are computed.
+        The return value is a tuple of two dictionaries keyed by target nodes.
+        The first dictionary stores distance to each target node.
+        The second stores the path to each target node.
+        If target is not None, returns a tuple (distance, path), where
+        distance is the distance from source to target and path is a list
+        representing the path from source to target.
+
+    Raises
+    ------
+    NodeNotFound
+        If `source` is not in `G`.
+
+    Examples
+    --------
+    >>> G = nx.path_graph(5)
+    >>> length, path = nx.single_source_dijkstra(G, 0)
+    >>> length[4]
+    4
+    >>> for node in [0, 1, 2, 3, 4]:
+    ...     print(f"{node}: {length[node]}")
+    0: 0
+    1: 1
+    2: 2
+    3: 3
+    4: 4
+    >>> path[4]
+    [0, 1, 2, 3, 4]
+    >>> length, path = nx.single_source_dijkstra(G, 0, 1)
+    >>> length
+    1
+    >>> path
+    [0, 1]
+
+    Notes
+    -----
+    Edge weight attributes must be numerical.
+    Distances are calculated as sums of weighted edges traversed.
+
+    The weight function can be used to hide edges by returning None.
+    So ``weight = lambda u, v, d: 1 if d['color']=="red" else None``
+    will find the shortest red path.
+
+    Based on the Python cookbook recipe (119466) at
+    https://code.activestate.com/recipes/119466/
+
+    This algorithm is not guaranteed to work if edge weights
+    are negative or are floating point numbers
+    (overflows and roundoff errors can cause problems).
+
+    See Also
+    --------
+    single_source_dijkstra_path
+    single_source_dijkstra_path_length
+    single_source_bellman_ford
+    """
+    return multi_source_dijkstra(
+        G, {source}, cutoff=cutoff, target=target, weight=weight
+    )
+
+
+@nx._dispatchable(edge_attrs="weight")
+def multi_source_dijkstra_path(G, sources, cutoff=None, weight="weight"):
+    """Find shortest weighted paths in G from a given set of source
+    nodes.
+
+    Compute shortest path between any of the source nodes and all other
+    reachable nodes for a weighted graph.
+
+    Parameters
+    ----------
+    G : NetworkX graph
+
+    sources : non-empty set of nodes
+        Starting nodes for paths. If this is just a set containing a
+        single node, then all paths computed by this function will start
+        from that node. If there are two or more nodes in the set, the
+        computed paths may begin from any one of the start nodes.
+
+    cutoff : integer or float, optional
+        Length (sum of edge weights) at which the search is stopped.
+        If cutoff is provided, only return paths with summed weight <= cutoff.
+
+    weight : string or function
+        If this is a string, then edge weights will be accessed via the
+        edge attribute with this key (that is, the weight of the edge
+        joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
+        such edge attribute exists, the weight of the edge is assumed to
+        be one.
+
+        If this is a function, the weight of an edge is the value
+        returned by the function. The function must accept exactly three
+        positional arguments: the two endpoints of an edge and the
+        dictionary of edge attributes for that edge. The function must
+        return a number or None to indicate a hidden edge.
+
+    Returns
+    -------
+    paths : dictionary
+        Dictionary of shortest paths keyed by target.
+
+    Examples
+    --------
+    >>> G = nx.path_graph(5)
+    >>> path = nx.multi_source_dijkstra_path(G, {0, 4})
+    >>> path[1]
+    [0, 1]
+    >>> path[3]
+    [4, 3]
+
+    Notes
+    -----
+    Edge weight attributes must be numerical.
+    Distances are calculated as sums of weighted edges traversed.
+
+    The weight function can be used to hide edges by returning None.
+    So ``weight = lambda u, v, d: 1 if d['color']=="red" else None``
+    will find the shortest red path.
+
+    Raises
+    ------
+    ValueError
+        If `sources` is empty.
+    NodeNotFound
+        If any of `sources` is not in `G`.
+
+    See Also
+    --------
+    multi_source_dijkstra, multi_source_bellman_ford
+
+    """
+    length, path = multi_source_dijkstra(G, sources, cutoff=cutoff, weight=weight)
+    return path
+
+
+@nx._dispatchable(edge_attrs="weight")
+def multi_source_dijkstra_path_length(G, sources, cutoff=None, weight="weight"):
+    """Find shortest weighted path lengths in G from a given set of
+    source nodes.
+
+    Compute the shortest path length between any of the source nodes and
+    all other reachable nodes for a weighted graph.
+
+    Parameters
+    ----------
+    G : NetworkX graph
+
+    sources : non-empty set of nodes
+        Starting nodes for paths. If this is just a set containing a
+        single node, then all paths computed by this function will start
+        from that node. If there are two or more nodes in the set, the
+        computed paths may begin from any one of the start nodes.
+
+    cutoff : integer or float, optional
+        Length (sum of edge weights) at which the search is stopped.
+        If cutoff is provided, only return paths with summed weight <= cutoff.
+
+    weight : string or function
+        If this is a string, then edge weights will be accessed via the
+        edge attribute with this key (that is, the weight of the edge
+        joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
+        such edge attribute exists, the weight of the edge is assumed to
+        be one.
+
+        If this is a function, the weight of an edge is the value
+        returned by the function. The function must accept exactly three
+        positional arguments: the two endpoints of an edge and the
+        dictionary of edge attributes for that edge. The function must
+        return a number or None to indicate a hidden edge.
+
+    Returns
+    -------
+    length : dict
+        Dict keyed by node to shortest path length to nearest source.
+
+    Examples
+    --------
+    >>> G = nx.path_graph(5)
+    >>> length = nx.multi_source_dijkstra_path_length(G, {0, 4})
+    >>> for node in [0, 1, 2, 3, 4]:
+    ...     print(f"{node}: {length[node]}")
+    0: 0
+    1: 1
+    2: 2
+    3: 1
+    4: 0
+
+    Notes
+    -----
+    Edge weight attributes must be numerical.
+    Distances are calculated as sums of weighted edges traversed.
+
+    The weight function can be used to hide edges by returning None.
+    So ``weight = lambda u, v, d: 1 if d['color']=="red" else None``
+    will find the shortest red path.
+
+    Raises
+    ------
+    ValueError
+        If `sources` is empty.
+    NodeNotFound
+        If any of `sources` is not in `G`.
+
+    See Also
+    --------
+    multi_source_dijkstra
+
+    """
+    if not sources:
+        raise ValueError("sources must not be empty")
+    for s in sources:
+        if s not in G:
+            raise nx.NodeNotFound(f"Node {s} not found in graph")
+    weight = _weight_function(G, weight)
+    return _dijkstra_multisource(G, sources, weight, cutoff=cutoff)
+
+
+@nx._dispatchable(edge_attrs="weight")
+def multi_source_dijkstra(G, sources, target=None, cutoff=None, weight="weight"):
+    """Find shortest weighted paths and lengths from a given set of
+    source nodes.
+
+    Uses Dijkstra's algorithm to compute the shortest paths and lengths
+    between one of the source nodes and the given `target`, or all other
+    reachable nodes if not specified, for a weighted graph.
+
+    Parameters
+    ----------
+    G : NetworkX graph
+
+    sources : non-empty set of nodes
+        Starting nodes for paths. If this is just a set containing a
+        single node, then all paths computed by this function will start
+        from that node. If there are two or more nodes in the set, the
+        computed paths may begin from any one of the start nodes.
+
+    target : node label, optional
+        Ending node for path
+
+    cutoff : integer or float, optional
+        Length (sum of edge weights) at which the search is stopped.
+        If cutoff is provided, only return paths with summed weight <= cutoff.
+
+    weight : string or function
+        If this is a string, then edge weights will be accessed via the
+        edge attribute with this key (that is, the weight of the edge
+        joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
+        such edge attribute exists, the weight of the edge is assumed to
+        be one.
+
+        If this is a function, the weight of an edge is the value
+        returned by the function. The function must accept exactly three
+        positional arguments: the two endpoints of an edge and the
+        dictionary of edge attributes for that edge. The function must
+        return a number or None to indicate a hidden edge.
+
+    Returns
+    -------
+    distance, path : pair of dictionaries, or numeric and list
+        If target is None, returns a tuple of two dictionaries keyed by node.
+        The first dictionary stores distance from one of the source nodes.
+        The second stores the path from one of the sources to that node.
+        If target is not None, returns a tuple of (distance, path) where
+        distance is the distance from source to target and path is a list
+        representing the path from source to target.
+
+    Examples
+    --------
+    >>> G = nx.path_graph(5)
+    >>> length, path = nx.multi_source_dijkstra(G, {0, 4})
+    >>> for node in [0, 1, 2, 3, 4]:
+    ...     print(f"{node}: {length[node]}")
+    0: 0
+    1: 1
+    2: 2
+    3: 1
+    4: 0
+    >>> path[1]
+    [0, 1]
+    >>> path[3]
+    [4, 3]
+
+    >>> length, path = nx.multi_source_dijkstra(G, {0, 4}, 1)
+    >>> length
+    1
+    >>> path
+    [0, 1]
+
+    Notes
+    -----
+    Edge weight attributes must be numerical.
+    Distances are calculated as sums of weighted edges traversed.
+
+    The weight function can be used to hide edges by returning None.
+    So ``weight = lambda u, v, d: 1 if d['color']=="red" else None``
+    will find the shortest red path.
+
+    Based on the Python cookbook recipe (119466) at
+    https://code.activestate.com/recipes/119466/
+
+    This algorithm is not guaranteed to work if edge weights
+    are negative or are floating point numbers
+    (overflows and roundoff errors can cause problems).
+
+    Raises
+    ------
+    ValueError
+        If `sources` is empty.
+    NodeNotFound
+        If any of `sources` is not in `G`.
+
+    See Also
+    --------
+    multi_source_dijkstra_path
+    multi_source_dijkstra_path_length
+
+    """
+    if not sources:
+        raise ValueError("sources must not be empty")
+    for s in sources:
+        if s not in G:
+            raise nx.NodeNotFound(f"Node {s} not found in graph")
+    if target in sources:
+        return (0, [target])
+    weight = _weight_function(G, weight)
+    paths = {source: [source] for source in sources}  # dictionary of paths
+    dist = _dijkstra_multisource(
+        G, sources, weight, paths=paths, cutoff=cutoff, target=target
+    )
+    if target is None:
+        return (dist, paths)
+    try:
+        return (dist[target], paths[target])
+    except KeyError as err:
+        raise nx.NetworkXNoPath(f"No path to {target}.") from err
+
+
+def _dijkstra(G, source, weight, pred=None, paths=None, cutoff=None, target=None):
+    """Uses Dijkstra's algorithm to find shortest weighted paths from a
+    single source.
+
+    This is a convenience function for :func:`_dijkstra_multisource`
+    with all the arguments the same, except the keyword argument
+    `sources` set to ``[source]``.
+
+    """
+    return _dijkstra_multisource(
+        G, [source], weight, pred=pred, paths=paths, cutoff=cutoff, target=target
+    )
+
+
+def _dijkstra_multisource(
+    G, sources, weight, pred=None, paths=None, cutoff=None, target=None
+):
+    """Uses Dijkstra's algorithm to find shortest weighted paths
+
+    Parameters
+    ----------
+    G : NetworkX graph
+
+    sources : non-empty iterable of nodes
+        Starting nodes for paths. If this is just an iterable containing
+        a single node, then all paths computed by this function will
+        start from that node. If there are two or more nodes in this
+        iterable, the computed paths may begin from any one of the start
+        nodes.
+
+    weight: function
+        Function with (u, v, data) input that returns that edge's weight
+        or None to indicate a hidden edge
+
+    pred: dict of lists, optional(default=None)
+        dict to store a list of predecessors keyed by that node
+        If None, predecessors are not stored.
+
+    paths: dict, optional (default=None)
+        dict to store the path list from source to each node, keyed by node.
+        If None, paths are not stored.
+
+    target : node label, optional
+        Ending node for path. Search is halted when target is found.
+
+    cutoff : integer or float, optional
+        Length (sum of edge weights) at which the search is stopped.
+        If cutoff is provided, only return paths with summed weight <= cutoff.
+
+    Returns
+    -------
+    distance : dictionary
+        A mapping from node to shortest distance to that node from one
+        of the source nodes.
+
+    Raises
+    ------
+    NodeNotFound
+        If any of `sources` is not in `G`.
+
+    Notes
+    -----
+    The optional predecessor and path dictionaries can be accessed by
+    the caller through the original pred and paths objects passed
+    as arguments. No need to explicitly return pred or paths.
+
+    """
+    G_succ = G._adj  # For speed-up (and works for both directed and undirected graphs)
+
+    push = heappush
+    pop = heappop
+    dist = {}  # dictionary of final distances
+    seen = {}
+    # fringe is heapq with 3-tuples (distance,c,node)
+    # use the count c to avoid comparing nodes (may not be able to)
+    c = count()
+    fringe = []
+    for source in sources:
+        seen[source] = 0
+        push(fringe, (0, next(c), source))
+    while fringe:
+        (d, _, v) = pop(fringe)
+        if v in dist:
+            continue  # already searched this node.
+        dist[v] = d
+        if v == target:
+            break
+        for u, e in G_succ[v].items():
+            cost = weight(v, u, e)
+            if cost is None:
+                continue
+            vu_dist = dist[v] + cost
+            if cutoff is not None:
+                if vu_dist > cutoff:
+                    continue
+            if u in dist:
+                u_dist = dist[u]
+                if vu_dist < u_dist:
+                    raise ValueError("Contradictory paths found:", "negative weights?")
+                elif pred is not None and vu_dist == u_dist:
+                    pred[u].append(v)
+            elif u not in seen or vu_dist < seen[u]:
+                seen[u] = vu_dist
+                push(fringe, (vu_dist, next(c), u))
+                if paths is not None:
+                    paths[u] = paths[v] + [u]
+                if pred is not None:
+                    pred[u] = [v]
+            elif vu_dist == seen[u]:
+                if pred is not None:
+                    pred[u].append(v)
+
+    # The optional predecessor and path dictionaries can be accessed
+    # by the caller via the pred and paths objects passed as arguments.
+    return dist
+
+
+@nx._dispatchable(edge_attrs="weight")
+def dijkstra_predecessor_and_distance(G, source, cutoff=None, weight="weight"):
+    """Compute weighted shortest path length and predecessors.
+
+    Uses Dijkstra's Method to obtain the shortest weighted paths
+    and return dictionaries of predecessors for each node and
+    distance for each node from the `source`.
+
+    Parameters
+    ----------
+    G : NetworkX graph
+
+    source : node label
+        Starting node for path
+
+    cutoff : integer or float, optional
+        Length (sum of edge weights) at which the search is stopped.
+        If cutoff is provided, only return paths with summed weight <= cutoff.
+
+    weight : string or function
+        If this is a string, then edge weights will be accessed via the
+        edge attribute with this key (that is, the weight of the edge
+        joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
+        such edge attribute exists, the weight of the edge is assumed to
+        be one.
+
+        If this is a function, the weight of an edge is the value
+        returned by the function. The function must accept exactly three
+        positional arguments: the two endpoints of an edge and the
+        dictionary of edge attributes for that edge. The function must
+        return a number or None to indicate a hidden edge.
+
+    Returns
+    -------
+    pred, distance : dictionaries
+        Returns two dictionaries representing a list of predecessors
+        of a node and the distance to each node.
+
+    Raises
+    ------
+    NodeNotFound
+        If `source` is not in `G`.
+
+    Notes
+    -----
+    Edge weight attributes must be numerical.
+    Distances are calculated as sums of weighted edges traversed.
+
+    The list of predecessors contains more than one element only when
+    there are more than one shortest paths to the key node.
+
+    Examples
+    --------
+    >>> G = nx.path_graph(5, create_using=nx.DiGraph())
+    >>> pred, dist = nx.dijkstra_predecessor_and_distance(G, 0)
+    >>> sorted(pred.items())
+    [(0, []), (1, [0]), (2, [1]), (3, [2]), (4, [3])]
+    >>> sorted(dist.items())
+    [(0, 0), (1, 1), (2, 2), (3, 3), (4, 4)]
+
+    >>> pred, dist = nx.dijkstra_predecessor_and_distance(G, 0, 1)
+    >>> sorted(pred.items())
+    [(0, []), (1, [0])]
+    >>> sorted(dist.items())
+    [(0, 0), (1, 1)]
+    """
+    if source not in G:
+        raise nx.NodeNotFound(f"Node {source} is not found in the graph")
+    weight = _weight_function(G, weight)
+    pred = {source: []}  # dictionary of predecessors
+    return (pred, _dijkstra(G, source, weight, pred=pred, cutoff=cutoff))
+
+
+@nx._dispatchable(edge_attrs="weight")
+def all_pairs_dijkstra(G, cutoff=None, weight="weight"):
+    """Find shortest weighted paths and lengths between all nodes.
+
+    Parameters
+    ----------
+    G : NetworkX graph
+
+    cutoff : integer or float, optional
+        Length (sum of edge weights) at which the search is stopped.
+        If cutoff is provided, only return paths with summed weight <= cutoff.
+
+    weight : string or function
+        If this is a string, then edge weights will be accessed via the
+        edge attribute with this key (that is, the weight of the edge
+        joining `u` to `v` will be ``G.edge[u][v][weight]``). If no
+        such edge attribute exists, the weight of the edge is assumed to
+        be one.
+
+        If this is a function, the weight of an edge is the value
+        returned by the function. The function must accept exactly three
+        positional arguments: the two endpoints of an edge and the
+        dictionary of edge attributes for that edge. The function must
+        return a number or None to indicate a hidden edge.
+
+    Yields
+    ------
+    (node, (distance, path)) : (node obj, (dict, dict))
+        Each source node has two associated dicts. The first holds distance
+        keyed by target and the second holds paths keyed by target.
+        (See single_source_dijkstra for the source/target node terminology.)
+        If desired you can apply `dict()` to this function to create a dict
+        keyed by source node to the two dicts.
+
+    Examples
+    --------
+    >>> G = nx.path_graph(5)
+    >>> len_path = dict(nx.all_pairs_dijkstra(G))
+    >>> len_path[3][0][1]
+    2
+    >>> for node in [0, 1, 2, 3, 4]:
+    ...     print(f"3 - {node}: {len_path[3][0][node]}")
+    3 - 0: 3
+    3 - 1: 2
+    3 - 2: 1
+    3 - 3: 0
+    3 - 4: 1
+    >>> len_path[3][1][1]
+    [3, 2, 1]
+    >>> for n, (dist, path) in nx.all_pairs_dijkstra(G):
+    ...     print(path[1])
+    [0, 1]
+    [1]
+    [2, 1]
+    [3, 2, 1]
+    [4, 3, 2, 1]
+
+    Notes
+    -----
+    Edge weight attributes must be numerical.
+    Distances are calculated as sums of weighted edges traversed.
+
+    The yielded dicts only have keys for reachable nodes.
+    """
+    for n in G:
+        dist, path = single_source_dijkstra(G, n, cutoff=cutoff, weight=weight)
+        yield (n, (dist, path))
+
+
+@nx._dispatchable(edge_attrs="weight")
+def all_pairs_dijkstra_path_length(G, cutoff=None, weight="weight"):
+    """Compute shortest path lengths between all nodes in a weighted graph.
+
+    Parameters
+    ----------
+    G : NetworkX graph
+
+    cutoff : integer or float, optional
+        Length (sum of edge weights) at which the search is stopped.
+        If cutoff is provided, only return paths with summed weight <= cutoff.
+
+    weight : string or function
+        If this is a string, then edge weights will be accessed via the
+        edge attribute with this key (that is, the weight of the edge
+        joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
+        such edge attribute exists, the weight of the edge is assumed to
+        be one.
+
+        If this is a function, the weight of an edge is the value
+        returned by the function. The function must accept exactly three
+        positional arguments: the two endpoints of an edge and the
+        dictionary of edge attributes for that edge. The function must
+        return a number or None to indicate a hidden edge.
+
+    Returns
+    -------
+    distance : iterator
+        (source, dictionary) iterator with dictionary keyed by target and
+        shortest path length as the key value.
+
+    Examples
+    --------
+    >>> G = nx.path_graph(5)
+    >>> length = dict(nx.all_pairs_dijkstra_path_length(G))
+    >>> for node in [0, 1, 2, 3, 4]:
+    ...     print(f"1 - {node}: {length[1][node]}")
+    1 - 0: 1
+    1 - 1: 0
+    1 - 2: 1
+    1 - 3: 2
+    1 - 4: 3
+    >>> length[3][2]
+    1
+    >>> length[2][2]
+    0
+
+    Notes
+    -----
+    Edge weight attributes must be numerical.
+    Distances are calculated as sums of weighted edges traversed.
+
+    The dictionary returned only has keys for reachable node pairs.
+    """
+    length = single_source_dijkstra_path_length
+    for n in G:
+        yield (n, length(G, n, cutoff=cutoff, weight=weight))
+
+
+@nx._dispatchable(edge_attrs="weight")
+def all_pairs_dijkstra_path(G, cutoff=None, weight="weight"):
+    """Compute shortest paths between all nodes in a weighted graph.
+
+    Parameters
+    ----------
+    G : NetworkX graph
+
+    cutoff : integer or float, optional
+        Length (sum of edge weights) at which the search is stopped.
+        If cutoff is provided, only return paths with summed weight <= cutoff.
+
+    weight : string or function
+        If this is a string, then edge weights will be accessed via the
+        edge attribute with this key (that is, the weight of the edge
+        joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
+        such edge attribute exists, the weight of the edge is assumed to
+        be one.
+
+        If this is a function, the weight of an edge is the value
+        returned by the function. The function must accept exactly three
+        positional arguments: the two endpoints of an edge and the
+        dictionary of edge attributes for that edge. The function must
+        return a number or None to indicate a hidden edge.
+
+    Returns
+    -------
+    paths : iterator
+        (source, dictionary) iterator with dictionary keyed by target and
+        shortest path as the key value.
+
+    Examples
+    --------
+    >>> G = nx.path_graph(5)
+    >>> path = dict(nx.all_pairs_dijkstra_path(G))
+    >>> path[0][4]
+    [0, 1, 2, 3, 4]
+
+    Notes
+    -----
+    Edge weight attributes must be numerical.
+    Distances are calculated as sums of weighted edges traversed.
+
+    See Also
+    --------
+    floyd_warshall, all_pairs_bellman_ford_path
+
+    """
+    path = single_source_dijkstra_path
+    # TODO This can be trivially parallelized.
+    for n in G:
+        yield (n, path(G, n, cutoff=cutoff, weight=weight))
+
+
+@nx._dispatchable(edge_attrs="weight")
+def bellman_ford_predecessor_and_distance(
+    G, source, target=None, weight="weight", heuristic=False
+):
+    """Compute shortest path lengths and predecessors on shortest paths
+    in weighted graphs.
+
+    The algorithm has a running time of $O(mn)$ where $n$ is the number of
+    nodes and $m$ is the number of edges.  It is slower than Dijkstra but
+    can handle negative edge weights.
+
+    If a negative cycle is detected, you can use :func:`find_negative_cycle`
+    to return the cycle and examine it. Shortest paths are not defined when
+    a negative cycle exists because once reached, the path can cycle forever
+    to build up arbitrarily low weights.
+
+    Parameters
+    ----------
+    G : NetworkX graph
+        The algorithm works for all types of graphs, including directed
+        graphs and multigraphs.
+
+    source: node label
+        Starting node for path
+
+    target : node label, optional
+        Ending node for path
+
+    weight : string or function
+        If this is a string, then edge weights will be accessed via the
+        edge attribute with this key (that is, the weight of the edge
+        joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
+        such edge attribute exists, the weight of the edge is assumed to
+        be one.
+
+        If this is a function, the weight of an edge is the value
+        returned by the function. The function must accept exactly three
+        positional arguments: the two endpoints of an edge and the
+        dictionary of edge attributes for that edge. The function must
+        return a number.
+
+    heuristic : bool
+        Determines whether to use a heuristic to early detect negative
+        cycles at a hopefully negligible cost.
+
+    Returns
+    -------
+    pred, dist : dictionaries
+        Returns two dictionaries keyed by node to predecessor in the
+        path and to the distance from the source respectively.
+
+    Raises
+    ------
+    NodeNotFound
+        If `source` is not in `G`.
+
+    NetworkXUnbounded
+        If the (di)graph contains a negative (di)cycle, the
+        algorithm raises an exception to indicate the presence of the
+        negative (di)cycle.  Note: any negative weight edge in an
+        undirected graph is a negative cycle.
+
+    Examples
+    --------
+    >>> G = nx.path_graph(5, create_using=nx.DiGraph())
+    >>> pred, dist = nx.bellman_ford_predecessor_and_distance(G, 0)
+    >>> sorted(pred.items())
+    [(0, []), (1, [0]), (2, [1]), (3, [2]), (4, [3])]
+    >>> sorted(dist.items())
+    [(0, 0), (1, 1), (2, 2), (3, 3), (4, 4)]
+
+    >>> pred, dist = nx.bellman_ford_predecessor_and_distance(G, 0, 1)
+    >>> sorted(pred.items())
+    [(0, []), (1, [0]), (2, [1]), (3, [2]), (4, [3])]
+    >>> sorted(dist.items())
+    [(0, 0), (1, 1), (2, 2), (3, 3), (4, 4)]
+
+    >>> G = nx.cycle_graph(5, create_using=nx.DiGraph())
+    >>> G[1][2]["weight"] = -7
+    >>> nx.bellman_ford_predecessor_and_distance(G, 0)
+    Traceback (most recent call last):
+        ...
+    networkx.exception.NetworkXUnbounded: Negative cycle detected.
+
+    See Also
+    --------
+    find_negative_cycle
+
+    Notes
+    -----
+    Edge weight attributes must be numerical.
+    Distances are calculated as sums of weighted edges traversed.
+
+    The dictionaries returned only have keys for nodes reachable from
+    the source.
+
+    In the case where the (di)graph is not connected, if a component
+    not containing the source contains a negative (di)cycle, it
+    will not be detected.
+
+    In NetworkX v2.1 and prior, the source node had predecessor `[None]`.
+    In NetworkX v2.2 this changed to the source node having predecessor `[]`
+    """
+    if source not in G:
+        raise nx.NodeNotFound(f"Node {source} is not found in the graph")
+    weight = _weight_function(G, weight)
+    if G.is_multigraph():
+        if any(
+            weight(u, v, {k: d}) < 0
+            for u, v, k, d in nx.selfloop_edges(G, keys=True, data=True)
+        ):
+            raise nx.NetworkXUnbounded("Negative cycle detected.")
+    else:
+        if any(weight(u, v, d) < 0 for u, v, d in nx.selfloop_edges(G, data=True)):
+            raise nx.NetworkXUnbounded("Negative cycle detected.")
+
+    dist = {source: 0}
+    pred = {source: []}
+
+    if len(G) == 1:
+        return pred, dist
+
+    weight = _weight_function(G, weight)
+
+    dist = _bellman_ford(
+        G, [source], weight, pred=pred, dist=dist, target=target, heuristic=heuristic
+    )
+    return (pred, dist)
+
+
+def _bellman_ford(
+    G,
+    source,
+    weight,
+    pred=None,
+    paths=None,
+    dist=None,
+    target=None,
+    heuristic=True,
+):
+    """Calls relaxation loop for Bellman–Ford algorithm and builds paths
+
+    This is an implementation of the SPFA variant.
+    See https://en.wikipedia.org/wiki/Shortest_Path_Faster_Algorithm
+
+    Parameters
+    ----------
+    G : NetworkX graph
+
+    source: list
+        List of source nodes. The shortest path from any of the source
+        nodes will be found if multiple sources are provided.
+
+    weight : function
+        The weight of an edge is the value returned by the function. The
+        function must accept exactly three positional arguments: the two
+        endpoints of an edge and the dictionary of edge attributes for
+        that edge. The function must return a number.
+
+    pred: dict of lists, optional (default=None)
+        dict to store a list of predecessors keyed by that node
+        If None, predecessors are not stored
+
+    paths: dict, optional (default=None)
+        dict to store the path list from source to each node, keyed by node
+        If None, paths are not stored
+
+    dist: dict, optional (default=None)
+        dict to store distance from source to the keyed node
+        If None, returned dist dict contents default to 0 for every node in the
+        source list
+
+    target: node label, optional
+        Ending node for path. Path lengths to other destinations may (and
+        probably will) be incorrect.
+
+    heuristic : bool
+        Determines whether to use a heuristic to early detect negative
+        cycles at a hopefully negligible cost.
+
+    Returns
+    -------
+    dist : dict
+        Returns a dict keyed by node to the distance from the source.
+        Dicts for paths and pred are in the mutated input dicts by those names.
+
+    Raises
+    ------
+    NodeNotFound
+        If any of `source` is not in `G`.
+
+    NetworkXUnbounded
+        If the (di)graph contains a negative (di)cycle, the
+        algorithm raises an exception to indicate the presence of the
+        negative (di)cycle.  Note: any negative weight edge in an
+        undirected graph is a negative cycle
+    """
+    if pred is None:
+        pred = {v: [] for v in source}
+
+    if dist is None:
+        dist = {v: 0 for v in source}
+
+    negative_cycle_found = _inner_bellman_ford(
+        G,
+        source,
+        weight,
+        pred,
+        dist,
+        heuristic,
+    )
+    if negative_cycle_found is not None:
+        raise nx.NetworkXUnbounded("Negative cycle detected.")
+
+    if paths is not None:
+        sources = set(source)
+        dsts = [target] if target is not None else pred
+        for dst in dsts:
+            gen = _build_paths_from_predecessors(sources, dst, pred)
+            paths[dst] = next(gen)
+
+    return dist
+
+
+def _inner_bellman_ford(
+    G,
+    sources,
+    weight,
+    pred,
+    dist=None,
+    heuristic=True,
+):
+    """Inner Relaxation loop for Bellman–Ford algorithm.
+
+    This is an implementation of the SPFA variant.
+    See https://en.wikipedia.org/wiki/Shortest_Path_Faster_Algorithm
+
+    Parameters
+    ----------
+    G : NetworkX graph
+
+    source: list
+        List of source nodes. The shortest path from any of the source
+        nodes will be found if multiple sources are provided.
+
+    weight : function
+        The weight of an edge is the value returned by the function. The
+        function must accept exactly three positional arguments: the two
+        endpoints of an edge and the dictionary of edge attributes for
+        that edge. The function must return a number.
+
+    pred: dict of lists
+        dict to store a list of predecessors keyed by that node
+
+    dist: dict, optional (default=None)
+        dict to store distance from source to the keyed node
+        If None, returned dist dict contents default to 0 for every node in the
+        source list
+
+    heuristic : bool
+        Determines whether to use a heuristic to early detect negative
+        cycles at a hopefully negligible cost.
+
+    Returns
+    -------
+    node or None
+        Return a node `v` where processing discovered a negative cycle.
+        If no negative cycle found, return None.
+
+    Raises
+    ------
+    NodeNotFound
+        If any of `source` is not in `G`.
+    """
+    for s in sources:
+        if s not in G:
+            raise nx.NodeNotFound(f"Source {s} not in G")
+
+    if pred is None:
+        pred = {v: [] for v in sources}
+
+    if dist is None:
+        dist = {v: 0 for v in sources}
+
+    # Heuristic Storage setup. Note: use None because nodes cannot be None
+    nonexistent_edge = (None, None)
+    pred_edge = {v: None for v in sources}
+    recent_update = {v: nonexistent_edge for v in sources}
+
+    G_succ = G._adj  # For speed-up (and works for both directed and undirected graphs)
+    inf = float("inf")
+    n = len(G)
+
+    count = {}
+    q = deque(sources)
+    in_q = set(sources)
+    while q:
+        u = q.popleft()
+        in_q.remove(u)
+
+        # Skip relaxations if any of the predecessors of u is in the queue.
+        if all(pred_u not in in_q for pred_u in pred[u]):
+            dist_u = dist[u]
+            for v, e in G_succ[u].items():
+                dist_v = dist_u + weight(u, v, e)
+
+                if dist_v < dist.get(v, inf):
+                    # In this conditional branch we are updating the path with v.
+                    # If it happens that some earlier update also added node v
+                    # that implies the existence of a negative cycle since
+                    # after the update node v would lie on the update path twice.
+                    # The update path is stored up to one of the source nodes,
+                    # therefore u is always in the dict recent_update
+                    if heuristic:
+                        if v in recent_update[u]:
+                            # Negative cycle found!
+                            pred[v].append(u)
+                            return v
+
+                        # Transfer the recent update info from u to v if the
+                        # same source node is the head of the update path.
+                        # If the source node is responsible for the cost update,
+                        # then clear the history and use it instead.
+                        if v in pred_edge and pred_edge[v] == u:
+                            recent_update[v] = recent_update[u]
+                        else:
+                            recent_update[v] = (u, v)
+
+                    if v not in in_q:
+                        q.append(v)
+                        in_q.add(v)
+                        count_v = count.get(v, 0) + 1
+                        if count_v == n:
+                            # Negative cycle found!
+                            return v
+
+                        count[v] = count_v
+                    dist[v] = dist_v
+                    pred[v] = [u]
+                    pred_edge[v] = u
+
+                elif dist.get(v) is not None and dist_v == dist.get(v):
+                    pred[v].append(u)
+
+    # successfully found shortest_path. No negative cycles found.
+    return None
+
+
+@nx._dispatchable(edge_attrs="weight")
+def bellman_ford_path(G, source, target, weight="weight"):
+    """Returns the shortest path from source to target in a weighted graph G.
+
+    Parameters
+    ----------
+    G : NetworkX graph
+
+    source : node
+        Starting node
+
+    target : node
+        Ending node
+
+    weight : string or function (default="weight")
+        If this is a string, then edge weights will be accessed via the
+        edge attribute with this key (that is, the weight of the edge
+        joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
+        such edge attribute exists, the weight of the edge is assumed to
+        be one.
+
+        If this is a function, the weight of an edge is the value
+        returned by the function. The function must accept exactly three
+        positional arguments: the two endpoints of an edge and the
+        dictionary of edge attributes for that edge. The function must
+        return a number.
+
+    Returns
+    -------
+    path : list
+        List of nodes in a shortest path.
+
+    Raises
+    ------
+    NodeNotFound
+        If `source` is not in `G`.
+
+    NetworkXNoPath
+        If no path exists between source and target.
+
+    Examples
+    --------
+    >>> G = nx.path_graph(5)
+    >>> nx.bellman_ford_path(G, 0, 4)
+    [0, 1, 2, 3, 4]
+
+    Notes
+    -----
+    Edge weight attributes must be numerical.
+    Distances are calculated as sums of weighted edges traversed.
+
+    See Also
+    --------
+    dijkstra_path, bellman_ford_path_length
+    """
+    length, path = single_source_bellman_ford(G, source, target=target, weight=weight)
+    return path
+
+
+@nx._dispatchable(edge_attrs="weight")
+def bellman_ford_path_length(G, source, target, weight="weight"):
+    """Returns the shortest path length from source to target
+    in a weighted graph.
+
+    Parameters
+    ----------
+    G : NetworkX graph
+
+    source : node label
+        starting node for path
+
+    target : node label
+        ending node for path
+
+    weight : string or function (default="weight")
+        If this is a string, then edge weights will be accessed via the
+        edge attribute with this key (that is, the weight of the edge
+        joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
+        such edge attribute exists, the weight of the edge is assumed to
+        be one.
+
+        If this is a function, the weight of an edge is the value
+        returned by the function. The function must accept exactly three
+        positional arguments: the two endpoints of an edge and the
+        dictionary of edge attributes for that edge. The function must
+        return a number.
+
+    Returns
+    -------
+    length : number
+        Shortest path length.
+
+    Raises
+    ------
+    NodeNotFound
+        If `source` is not in `G`.
+
+    NetworkXNoPath
+        If no path exists between source and target.
+
+    Examples
+    --------
+    >>> G = nx.path_graph(5)
+    >>> nx.bellman_ford_path_length(G, 0, 4)
+    4
+
+    Notes
+    -----
+    Edge weight attributes must be numerical.
+    Distances are calculated as sums of weighted edges traversed.
+
+    See Also
+    --------
+    dijkstra_path_length, bellman_ford_path
+    """
+    if source == target:
+        if source not in G:
+            raise nx.NodeNotFound(f"Node {source} not found in graph")
+        return 0
+
+    weight = _weight_function(G, weight)
+
+    length = _bellman_ford(G, [source], weight, target=target)
+
+    try:
+        return length[target]
+    except KeyError as err:
+        raise nx.NetworkXNoPath(f"node {target} not reachable from {source}") from err
+
+
+@nx._dispatchable(edge_attrs="weight")
+def single_source_bellman_ford_path(G, source, weight="weight"):
+    """Compute shortest path between source and all other reachable
+    nodes for a weighted graph.
+
+    Parameters
+    ----------
+    G : NetworkX graph
+
+    source : node
+        Starting node for path.
+
+    weight : string or function (default="weight")
+        If this is a string, then edge weights will be accessed via the
+        edge attribute with this key (that is, the weight of the edge
+        joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
+        such edge attribute exists, the weight of the edge is assumed to
+        be one.
+
+        If this is a function, the weight of an edge is the value
+        returned by the function. The function must accept exactly three
+        positional arguments: the two endpoints of an edge and the
+        dictionary of edge attributes for that edge. The function must
+        return a number.
+
+    Returns
+    -------
+    paths : dictionary
+        Dictionary of shortest path lengths keyed by target.
+
+    Raises
+    ------
+    NodeNotFound
+        If `source` is not in `G`.
+
+    Examples
+    --------
+    >>> G = nx.path_graph(5)
+    >>> path = nx.single_source_bellman_ford_path(G, 0)
+    >>> path[4]
+    [0, 1, 2, 3, 4]
+
+    Notes
+    -----
+    Edge weight attributes must be numerical.
+    Distances are calculated as sums of weighted edges traversed.
+
+    See Also
+    --------
+    single_source_dijkstra, single_source_bellman_ford
+
+    """
+    (length, path) = single_source_bellman_ford(G, source, weight=weight)
+    return path
+
+
+@nx._dispatchable(edge_attrs="weight")
+def single_source_bellman_ford_path_length(G, source, weight="weight"):
+    """Compute the shortest path length between source and all other
+    reachable nodes for a weighted graph.
+
+    Parameters
+    ----------
+    G : NetworkX graph
+
+    source : node label
+        Starting node for path
+
+    weight : string or function (default="weight")
+        If this is a string, then edge weights will be accessed via the
+        edge attribute with this key (that is, the weight of the edge
+        joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
+        such edge attribute exists, the weight of the edge is assumed to
+        be one.
+
+        If this is a function, the weight of an edge is the value
+        returned by the function. The function must accept exactly three
+        positional arguments: the two endpoints of an edge and the
+        dictionary of edge attributes for that edge. The function must
+        return a number.
+
+    Returns
+    -------
+    length : dictionary
+        Dictionary of shortest path length keyed by target
+
+    Raises
+    ------
+    NodeNotFound
+        If `source` is not in `G`.
+
+    Examples
+    --------
+    >>> G = nx.path_graph(5)
+    >>> length = nx.single_source_bellman_ford_path_length(G, 0)
+    >>> length[4]
+    4
+    >>> for node in [0, 1, 2, 3, 4]:
+    ...     print(f"{node}: {length[node]}")
+    0: 0
+    1: 1
+    2: 2
+    3: 3
+    4: 4
+
+    Notes
+    -----
+    Edge weight attributes must be numerical.
+    Distances are calculated as sums of weighted edges traversed.
+
+    See Also
+    --------
+    single_source_dijkstra, single_source_bellman_ford
+
+    """
+    weight = _weight_function(G, weight)
+    return _bellman_ford(G, [source], weight)
+
+
+@nx._dispatchable(edge_attrs="weight")
+def single_source_bellman_ford(G, source, target=None, weight="weight"):
+    """Compute shortest paths and lengths in a weighted graph G.
+
+    Uses Bellman-Ford algorithm for shortest paths.
+
+    Parameters
+    ----------
+    G : NetworkX graph
+
+    source : node label
+        Starting node for path
+
+    target : node label, optional
+        Ending node for path
+
+    weight : string or function
+        If this is a string, then edge weights will be accessed via the
+        edge attribute with this key (that is, the weight of the edge
+        joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
+        such edge attribute exists, the weight of the edge is assumed to
+        be one.
+
+        If this is a function, the weight of an edge is the value
+        returned by the function. The function must accept exactly three
+        positional arguments: the two endpoints of an edge and the
+        dictionary of edge attributes for that edge. The function must
+        return a number.
+
+    Returns
+    -------
+    distance, path : pair of dictionaries, or numeric and list
+        If target is None, returns a tuple of two dictionaries keyed by node.
+        The first dictionary stores distance from one of the source nodes.
+        The second stores the path from one of the sources to that node.
+        If target is not None, returns a tuple of (distance, path) where
+        distance is the distance from source to target and path is a list
+        representing the path from source to target.
+
+    Raises
+    ------
+    NodeNotFound
+        If `source` is not in `G`.
+
+    Examples
+    --------
+    >>> G = nx.path_graph(5)
+    >>> length, path = nx.single_source_bellman_ford(G, 0)
+    >>> length[4]
+    4
+    >>> for node in [0, 1, 2, 3, 4]:
+    ...     print(f"{node}: {length[node]}")
+    0: 0
+    1: 1
+    2: 2
+    3: 3
+    4: 4
+    >>> path[4]
+    [0, 1, 2, 3, 4]
+    >>> length, path = nx.single_source_bellman_ford(G, 0, 1)
+    >>> length
+    1
+    >>> path
+    [0, 1]
+
+    Notes
+    -----
+    Edge weight attributes must be numerical.
+    Distances are calculated as sums of weighted edges traversed.
+
+    See Also
+    --------
+    single_source_dijkstra
+    single_source_bellman_ford_path
+    single_source_bellman_ford_path_length
+    """
+    if source == target:
+        if source not in G:
+            raise nx.NodeNotFound(f"Node {source} is not found in the graph")
+        return (0, [source])
+
+    weight = _weight_function(G, weight)
+
+    paths = {source: [source]}  # dictionary of paths
+    dist = _bellman_ford(G, [source], weight, paths=paths, target=target)
+    if target is None:
+        return (dist, paths)
+    try:
+        return (dist[target], paths[target])
+    except KeyError as err:
+        msg = f"Node {target} not reachable from {source}"
+        raise nx.NetworkXNoPath(msg) from err
+
+
+@nx._dispatchable(edge_attrs="weight")
+def all_pairs_bellman_ford_path_length(G, weight="weight"):
+    """Compute shortest path lengths between all nodes in a weighted graph.
+
+    Parameters
+    ----------
+    G : NetworkX graph
+
+    weight : string or function (default="weight")
+        If this is a string, then edge weights will be accessed via the
+        edge attribute with this key (that is, the weight of the edge
+        joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
+        such edge attribute exists, the weight of the edge is assumed to
+        be one.
+
+        If this is a function, the weight of an edge is the value
+        returned by the function. The function must accept exactly three
+        positional arguments: the two endpoints of an edge and the
+        dictionary of edge attributes for that edge. The function must
+        return a number.
+
+    Returns
+    -------
+    distance : iterator
+        (source, dictionary) iterator with dictionary keyed by target and
+        shortest path length as the key value.
+
+    Examples
+    --------
+    >>> G = nx.path_graph(5)
+    >>> length = dict(nx.all_pairs_bellman_ford_path_length(G))
+    >>> for node in [0, 1, 2, 3, 4]:
+    ...     print(f"1 - {node}: {length[1][node]}")
+    1 - 0: 1
+    1 - 1: 0
+    1 - 2: 1
+    1 - 3: 2
+    1 - 4: 3
+    >>> length[3][2]
+    1
+    >>> length[2][2]
+    0
+
+    Notes
+    -----
+    Edge weight attributes must be numerical.
+    Distances are calculated as sums of weighted edges traversed.
+
+    The dictionary returned only has keys for reachable node pairs.
+    """
+    length = single_source_bellman_ford_path_length
+    for n in G:
+        yield (n, dict(length(G, n, weight=weight)))
+
+
+@nx._dispatchable(edge_attrs="weight")
+def all_pairs_bellman_ford_path(G, weight="weight"):
+    """Compute shortest paths between all nodes in a weighted graph.
+
+    Parameters
+    ----------
+    G : NetworkX graph
+
+    weight : string or function (default="weight")
+        If this is a string, then edge weights will be accessed via the
+        edge attribute with this key (that is, the weight of the edge
+        joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
+        such edge attribute exists, the weight of the edge is assumed to
+        be one.
+
+        If this is a function, the weight of an edge is the value
+        returned by the function. The function must accept exactly three
+        positional arguments: the two endpoints of an edge and the
+        dictionary of edge attributes for that edge. The function must
+        return a number.
+
+    Returns
+    -------
+    paths : iterator
+        (source, dictionary) iterator with dictionary keyed by target and
+        shortest path as the key value.
+
+    Examples
+    --------
+    >>> G = nx.path_graph(5)
+    >>> path = dict(nx.all_pairs_bellman_ford_path(G))
+    >>> path[0][4]
+    [0, 1, 2, 3, 4]
+
+    Notes
+    -----
+    Edge weight attributes must be numerical.
+    Distances are calculated as sums of weighted edges traversed.
+
+    See Also
+    --------
+    floyd_warshall, all_pairs_dijkstra_path
+
+    """
+    path = single_source_bellman_ford_path
+    for n in G:
+        yield (n, path(G, n, weight=weight))
+
+
+@nx._dispatchable(edge_attrs="weight")
+def goldberg_radzik(G, source, weight="weight"):
+    """Compute shortest path lengths and predecessors on shortest paths
+    in weighted graphs.
+
+    The algorithm has a running time of $O(mn)$ where $n$ is the number of
+    nodes and $m$ is the number of edges.  It is slower than Dijkstra but
+    can handle negative edge weights.
+
+    Parameters
+    ----------
+    G : NetworkX graph
+        The algorithm works for all types of graphs, including directed
+        graphs and multigraphs.
+
+    source: node label
+        Starting node for path
+
+    weight : string or function
+        If this is a string, then edge weights will be accessed via the
+        edge attribute with this key (that is, the weight of the edge
+        joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
+        such edge attribute exists, the weight of the edge is assumed to
+        be one.
+
+        If this is a function, the weight of an edge is the value
+        returned by the function. The function must accept exactly three
+        positional arguments: the two endpoints of an edge and the
+        dictionary of edge attributes for that edge. The function must
+        return a number.
+
+    Returns
+    -------
+    pred, dist : dictionaries
+        Returns two dictionaries keyed by node to predecessor in the
+        path and to the distance from the source respectively.
+
+    Raises
+    ------
+    NodeNotFound
+        If `source` is not in `G`.
+
+    NetworkXUnbounded
+        If the (di)graph contains a negative (di)cycle, the
+        algorithm raises an exception to indicate the presence of the
+        negative (di)cycle.  Note: any negative weight edge in an
+        undirected graph is a negative cycle.
+
+        As of NetworkX v3.2, a zero weight cycle is no longer
+        incorrectly reported as a negative weight cycle.
+
+
+    Examples
+    --------
+    >>> G = nx.path_graph(5, create_using=nx.DiGraph())
+    >>> pred, dist = nx.goldberg_radzik(G, 0)
+    >>> sorted(pred.items())
+    [(0, None), (1, 0), (2, 1), (3, 2), (4, 3)]
+    >>> sorted(dist.items())
+    [(0, 0), (1, 1), (2, 2), (3, 3), (4, 4)]
+
+    >>> G = nx.cycle_graph(5, create_using=nx.DiGraph())
+    >>> G[1][2]["weight"] = -7
+    >>> nx.goldberg_radzik(G, 0)
+    Traceback (most recent call last):
+        ...
+    networkx.exception.NetworkXUnbounded: Negative cycle detected.
+
+    Notes
+    -----
+    Edge weight attributes must be numerical.
+    Distances are calculated as sums of weighted edges traversed.
+
+    The dictionaries returned only have keys for nodes reachable from
+    the source.
+
+    In the case where the (di)graph is not connected, if a component
+    not containing the source contains a negative (di)cycle, it
+    will not be detected.
+
+    """
+    if source not in G:
+        raise nx.NodeNotFound(f"Node {source} is not found in the graph")
+    weight = _weight_function(G, weight)
+    if G.is_multigraph():
+        if any(
+            weight(u, v, {k: d}) < 0
+            for u, v, k, d in nx.selfloop_edges(G, keys=True, data=True)
+        ):
+            raise nx.NetworkXUnbounded("Negative cycle detected.")
+    else:
+        if any(weight(u, v, d) < 0 for u, v, d in nx.selfloop_edges(G, data=True)):
+            raise nx.NetworkXUnbounded("Negative cycle detected.")
+
+    if len(G) == 1:
+        return {source: None}, {source: 0}
+
+    G_succ = G._adj  # For speed-up (and works for both directed and undirected graphs)
+
+    inf = float("inf")
+    d = {u: inf for u in G}
+    d[source] = 0
+    pred = {source: None}
+
+    def topo_sort(relabeled):
+        """Topologically sort nodes relabeled in the previous round and detect
+        negative cycles.
+        """
+        # List of nodes to scan in this round. Denoted by A in Goldberg and
+        # Radzik's paper.
+        to_scan = []
+        # In the DFS in the loop below, neg_count records for each node the
+        # number of edges of negative reduced costs on the path from a DFS root
+        # to the node in the DFS forest. The reduced cost of an edge (u, v) is
+        # defined as d[u] + weight[u][v] - d[v].
+        #
+        # neg_count also doubles as the DFS visit marker array.
+        neg_count = {}
+        for u in relabeled:
+            # Skip visited nodes.
+            if u in neg_count:
+                continue
+            d_u = d[u]
+            # Skip nodes without out-edges of negative reduced costs.
+            if all(d_u + weight(u, v, e) >= d[v] for v, e in G_succ[u].items()):
+                continue
+            # Nonrecursive DFS that inserts nodes reachable from u via edges of
+            # nonpositive reduced costs into to_scan in (reverse) topological
+            # order.
+            stack = [(u, iter(G_succ[u].items()))]
+            in_stack = {u}
+            neg_count[u] = 0
+            while stack:
+                u, it = stack[-1]
+                try:
+                    v, e = next(it)
+                except StopIteration:
+                    to_scan.append(u)
+                    stack.pop()
+                    in_stack.remove(u)
+                    continue
+                t = d[u] + weight(u, v, e)
+                d_v = d[v]
+                if t < d_v:
+                    is_neg = t < d_v
+                    d[v] = t
+                    pred[v] = u
+                    if v not in neg_count:
+                        neg_count[v] = neg_count[u] + int(is_neg)
+                        stack.append((v, iter(G_succ[v].items())))
+                        in_stack.add(v)
+                    elif v in in_stack and neg_count[u] + int(is_neg) > neg_count[v]:
+                        # (u, v) is a back edge, and the cycle formed by the
+                        # path v to u and (u, v) contains at least one edge of
+                        # negative reduced cost. The cycle must be of negative
+                        # cost.
+                        raise nx.NetworkXUnbounded("Negative cycle detected.")
+        to_scan.reverse()
+        return to_scan
+
+    def relax(to_scan):
+        """Relax out-edges of relabeled nodes."""
+        relabeled = set()
+        # Scan nodes in to_scan in topological order and relax incident
+        # out-edges. Add the relabled nodes to labeled.
+        for u in to_scan:
+            d_u = d[u]
+            for v, e in G_succ[u].items():
+                w_e = weight(u, v, e)
+                if d_u + w_e < d[v]:
+                    d[v] = d_u + w_e
+                    pred[v] = u
+                    relabeled.add(v)
+        return relabeled
+
+    # Set of nodes relabled in the last round of scan operations. Denoted by B
+    # in Goldberg and Radzik's paper.
+    relabeled = {source}
+
+    while relabeled:
+        to_scan = topo_sort(relabeled)
+        relabeled = relax(to_scan)
+
+    d = {u: d[u] for u in pred}
+    return pred, d
+
+
+@nx._dispatchable(edge_attrs="weight")
+def negative_edge_cycle(G, weight="weight", heuristic=True):
+    """Returns True if there exists a negative edge cycle anywhere in G.
+
+    Parameters
+    ----------
+    G : NetworkX graph
+
+    weight : string or function
+        If this is a string, then edge weights will be accessed via the
+        edge attribute with this key (that is, the weight of the edge
+        joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
+        such edge attribute exists, the weight of the edge is assumed to
+        be one.
+
+        If this is a function, the weight of an edge is the value
+        returned by the function. The function must accept exactly three
+        positional arguments: the two endpoints of an edge and the
+        dictionary of edge attributes for that edge. The function must
+        return a number.
+
+    heuristic : bool
+        Determines whether to use a heuristic to early detect negative
+        cycles at a negligible cost. In case of graphs with a negative cycle,
+        the performance of detection increases by at least an order of magnitude.
+
+    Returns
+    -------
+    negative_cycle : bool
+        True if a negative edge cycle exists, otherwise False.
+
+    Examples
+    --------
+    >>> G = nx.cycle_graph(5, create_using=nx.DiGraph())
+    >>> print(nx.negative_edge_cycle(G))
+    False
+    >>> G[1][2]["weight"] = -7
+    >>> print(nx.negative_edge_cycle(G))
+    True
+
+    Notes
+    -----
+    Edge weight attributes must be numerical.
+    Distances are calculated as sums of weighted edges traversed.
+
+    This algorithm uses bellman_ford_predecessor_and_distance() but finds
+    negative cycles on any component by first adding a new node connected to
+    every node, and starting bellman_ford_predecessor_and_distance on that
+    node.  It then removes that extra node.
+    """
+    if G.size() == 0:
+        return False
+
+    # find unused node to use temporarily
+    newnode = -1
+    while newnode in G:
+        newnode -= 1
+    # connect it to all nodes
+    G.add_edges_from([(newnode, n) for n in G])
+
+    try:
+        bellman_ford_predecessor_and_distance(
+            G, newnode, weight=weight, heuristic=heuristic
+        )
+    except nx.NetworkXUnbounded:
+        return True
+    finally:
+        G.remove_node(newnode)
+    return False
+
+
+@nx._dispatchable(edge_attrs="weight")
+def find_negative_cycle(G, source, weight="weight"):
+    """Returns a cycle with negative total weight if it exists.
+
+    Bellman-Ford is used to find shortest_paths. That algorithm
+    stops if there exists a negative cycle. This algorithm
+    picks up from there and returns the found negative cycle.
+
+    The cycle consists of a list of nodes in the cycle order. The last
+    node equals the first to make it a cycle.
+    You can look up the edge weights in the original graph. In the case
+    of multigraphs the relevant edge is the minimal weight edge between
+    the nodes in the 2-tuple.
+
+    If the graph has no negative cycle, a NetworkXError is raised.
+
+    Parameters
+    ----------
+    G : NetworkX graph
+
+    source: node label
+        The search for the negative cycle will start from this node.
+
+    weight : string or function
+        If this is a string, then edge weights will be accessed via the
+        edge attribute with this key (that is, the weight of the edge
+        joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
+        such edge attribute exists, the weight of the edge is assumed to
+        be one.
+
+        If this is a function, the weight of an edge is the value
+        returned by the function. The function must accept exactly three
+        positional arguments: the two endpoints of an edge and the
+        dictionary of edge attributes for that edge. The function must
+        return a number.
+
+    Examples
+    --------
+    >>> G = nx.DiGraph()
+    >>> G.add_weighted_edges_from(
+    ...     [(0, 1, 2), (1, 2, 2), (2, 0, 1), (1, 4, 2), (4, 0, -5)]
+    ... )
+    >>> nx.find_negative_cycle(G, 0)
+    [4, 0, 1, 4]
+
+    Returns
+    -------
+    cycle : list
+        A list of nodes in the order of the cycle found. The last node
+        equals the first to indicate a cycle.
+
+    Raises
+    ------
+    NetworkXError
+        If no negative cycle is found.
+    """
+    weight = _weight_function(G, weight)
+    pred = {source: []}
+
+    v = _inner_bellman_ford(G, [source], weight, pred=pred)
+    if v is None:
+        raise nx.NetworkXError("No negative cycles detected.")
+
+    # negative cycle detected... find it
+    neg_cycle = []
+    stack = [(v, list(pred[v]))]
+    seen = {v}
+    while stack:
+        node, preds = stack[-1]
+        if v in preds:
+            # found the cycle
+            neg_cycle.extend([node, v])
+            neg_cycle = list(reversed(neg_cycle))
+            return neg_cycle
+
+        if preds:
+            nbr = preds.pop()
+            if nbr not in seen:
+                stack.append((nbr, list(pred[nbr])))
+                neg_cycle.append(node)
+                seen.add(nbr)
+        else:
+            stack.pop()
+            if neg_cycle:
+                neg_cycle.pop()
+            else:
+                if v in G[v] and weight(G, v, v) < 0:
+                    return [v, v]
+                # should not reach here
+                raise nx.NetworkXError("Negative cycle is detected but not found")
+    # should not get here...
+    msg = "negative cycle detected but not identified"
+    raise nx.NetworkXUnbounded(msg)
+
+
+@nx._dispatchable(edge_attrs="weight")
+def bidirectional_dijkstra(G, source, target, weight="weight"):
+    r"""Dijkstra's algorithm for shortest paths using bidirectional search.
+
+    Parameters
+    ----------
+    G : NetworkX graph
+
+    source : node
+        Starting node.
+
+    target : node
+        Ending node.
+
+    weight : string or function
+        If this is a string, then edge weights will be accessed via the
+        edge attribute with this key (that is, the weight of the edge
+        joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
+        such edge attribute exists, the weight of the edge is assumed to
+        be one.
+
+        If this is a function, the weight of an edge is the value
+        returned by the function. The function must accept exactly three
+        positional arguments: the two endpoints of an edge and the
+        dictionary of edge attributes for that edge. The function must
+        return a number or None to indicate a hidden edge.
+
+    Returns
+    -------
+    length, path : number and list
+        length is the distance from source to target.
+        path is a list of nodes on a path from source to target.
+
+    Raises
+    ------
+    NodeNotFound
+        If `source` or `target` is not in `G`.
+
+    NetworkXNoPath
+        If no path exists between source and target.
+
+    Examples
+    --------
+    >>> G = nx.path_graph(5)
+    >>> length, path = nx.bidirectional_dijkstra(G, 0, 4)
+    >>> print(length)
+    4
+    >>> print(path)
+    [0, 1, 2, 3, 4]
+
+    Notes
+    -----
+    Edge weight attributes must be numerical.
+    Distances are calculated as sums of weighted edges traversed.
+
+    The weight function can be used to hide edges by returning None.
+    So ``weight = lambda u, v, d: 1 if d['color']=="red" else None``
+    will find the shortest red path.
+
+    In practice  bidirectional Dijkstra is much more than twice as fast as
+    ordinary Dijkstra.
+
+    Ordinary Dijkstra expands nodes in a sphere-like manner from the
+    source. The radius of this sphere will eventually be the length
+    of the shortest path. Bidirectional Dijkstra will expand nodes
+    from both the source and the target, making two spheres of half
+    this radius. Volume of the first sphere is `\pi*r*r` while the
+    others are `2*\pi*r/2*r/2`, making up half the volume.
+
+    This algorithm is not guaranteed to work if edge weights
+    are negative or are floating point numbers
+    (overflows and roundoff errors can cause problems).
+
+    See Also
+    --------
+    shortest_path
+    shortest_path_length
+    """
+    if source not in G:
+        raise nx.NodeNotFound(f"Source {source} is not in G")
+
+    if target not in G:
+        raise nx.NodeNotFound(f"Target {target} is not in G")
+
+    if source == target:
+        return (0, [source])
+
+    weight = _weight_function(G, weight)
+    push = heappush
+    pop = heappop
+    # Init:  [Forward, Backward]
+    dists = [{}, {}]  # dictionary of final distances
+    paths = [{source: [source]}, {target: [target]}]  # dictionary of paths
+    fringe = [[], []]  # heap of (distance, node) for choosing node to expand
+    seen = [{source: 0}, {target: 0}]  # dict of distances to seen nodes
+    c = count()
+    # initialize fringe heap
+    push(fringe[0], (0, next(c), source))
+    push(fringe[1], (0, next(c), target))
+    # neighs for extracting correct neighbor information
+    if G.is_directed():
+        neighs = [G._succ, G._pred]
+    else:
+        neighs = [G._adj, G._adj]
+    # variables to hold shortest discovered path
+    # finaldist = 1e30000
+    finalpath = []
+    dir = 1
+    while fringe[0] and fringe[1]:
+        # choose direction
+        # dir == 0 is forward direction and dir == 1 is back
+        dir = 1 - dir
+        # extract closest to expand
+        (dist, _, v) = pop(fringe[dir])
+        if v in dists[dir]:
+            # Shortest path to v has already been found
+            continue
+        # update distance
+        dists[dir][v] = dist  # equal to seen[dir][v]
+        if v in dists[1 - dir]:
+            # if we have scanned v in both directions we are done
+            # we have now discovered the shortest path
+            return (finaldist, finalpath)
+
+        for w, d in neighs[dir][v].items():
+            # weight(v, w, d) for forward and weight(w, v, d) for back direction
+            cost = weight(v, w, d) if dir == 0 else weight(w, v, d)
+            if cost is None:
+                continue
+            vwLength = dists[dir][v] + cost
+            if w in dists[dir]:
+                if vwLength < dists[dir][w]:
+                    raise ValueError("Contradictory paths found: negative weights?")
+            elif w not in seen[dir] or vwLength < seen[dir][w]:
+                # relaxing
+                seen[dir][w] = vwLength
+                push(fringe[dir], (vwLength, next(c), w))
+                paths[dir][w] = paths[dir][v] + [w]
+                if w in seen[0] and w in seen[1]:
+                    # see if this path is better than the already
+                    # discovered shortest path
+                    totaldist = seen[0][w] + seen[1][w]
+                    if finalpath == [] or finaldist > totaldist:
+                        finaldist = totaldist
+                        revpath = paths[1][w][:]
+                        revpath.reverse()
+                        finalpath = paths[0][w] + revpath[1:]
+    raise nx.NetworkXNoPath(f"No path between {source} and {target}.")
+
+
+@nx._dispatchable(edge_attrs="weight")
+def johnson(G, weight="weight"):
+    r"""Uses Johnson's Algorithm to compute shortest paths.
+
+    Johnson's Algorithm finds a shortest path between each pair of
+    nodes in a weighted graph even if negative weights are present.
+
+    Parameters
+    ----------
+    G : NetworkX graph
+
+    weight : string or function
+        If this is a string, then edge weights will be accessed via the
+        edge attribute with this key (that is, the weight of the edge
+        joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
+        such edge attribute exists, the weight of the edge is assumed to
+        be one.
+
+        If this is a function, the weight of an edge is the value
+        returned by the function. The function must accept exactly three
+        positional arguments: the two endpoints of an edge and the
+        dictionary of edge attributes for that edge. The function must
+        return a number.
+
+    Returns
+    -------
+    distance : dictionary
+        Dictionary, keyed by source and target, of shortest paths.
+
+    Examples
+    --------
+    >>> graph = nx.DiGraph()
+    >>> graph.add_weighted_edges_from(
+    ...     [("0", "3", 3), ("0", "1", -5), ("0", "2", 2), ("1", "2", 4), ("2", "3", 1)]
+    ... )
+    >>> paths = nx.johnson(graph, weight="weight")
+    >>> paths["0"]["2"]
+    ['0', '1', '2']
+
+    Notes
+    -----
+    Johnson's algorithm is suitable even for graphs with negative weights. It
+    works by using the Bellman–Ford algorithm to compute a transformation of
+    the input graph that removes all negative weights, allowing Dijkstra's
+    algorithm to be used on the transformed graph.
+
+    The time complexity of this algorithm is $O(n^2 \log n + n m)$,
+    where $n$ is the number of nodes and $m$ the number of edges in the
+    graph. For dense graphs, this may be faster than the Floyd–Warshall
+    algorithm.
+
+    See Also
+    --------
+    floyd_warshall_predecessor_and_distance
+    floyd_warshall_numpy
+    all_pairs_shortest_path
+    all_pairs_shortest_path_length
+    all_pairs_dijkstra_path
+    bellman_ford_predecessor_and_distance
+    all_pairs_bellman_ford_path
+    all_pairs_bellman_ford_path_length
+
+    """
+    dist = {v: 0 for v in G}
+    pred = {v: [] for v in G}
+    weight = _weight_function(G, weight)
+
+    # Calculate distance of shortest paths
+    dist_bellman = _bellman_ford(G, list(G), weight, pred=pred, dist=dist)
+
+    # Update the weight function to take into account the Bellman--Ford
+    # relaxation distances.
+    def new_weight(u, v, d):
+        return weight(u, v, d) + dist_bellman[u] - dist_bellman[v]
+
+    def dist_path(v):
+        paths = {v: [v]}
+        _dijkstra(G, v, new_weight, paths=paths)
+        return paths
+
+    return {v: dist_path(v) for v in G}