Bug fix for issue #5023 : corner-case bug in single_source_dijkstra (#5033)

Some of the shortest_path functions have a fast-path for the case when source==target.
In some of these functions, there was no check that the source node was in the graph,
leading to incorrect results when a NodeNotFound error would be more appropriate.
This PR fixes these cases.

In addition, checking that nodes are actually in the graph was formerly done in the internal
`_dijkstra_multisource` function. These checks have been factored out and moved to the
client functions for efficiency and to prevent redundant checking.

Co-authored-by: Ross Barnowski <rossbar@berkeley.edu>

3 files changed, 20 insertions, 6 deletions

diff --git a/networkx/algorithms/shortest_paths/tests/test_weighted.py b/networkx/algorithms/shortest_paths/tests/test_weighted.py
index 57638253..75fbe369 100644
--- a/networkx/algorithms/shortest_paths/tests/test_weighted.py
+++ b/networkx/algorithms/shortest_paths/tests/test_weighted.py
@@ -250,9 +250,6 @@ class TestWeightedPath(WeightedTestBase):
             path = nx.bidirectional_dijkstra(G, 1, 6)
 
     def test_absent_source(self):
-        # the check is in _dijkstra_multisource, but this will provide
-        # regression testing against later changes to any of the "client"
-        # Dijkstra or Bellman-Ford functions
         G = nx.path_graph(2)
         for fn in (
             nx.dijkstra_path,
@@ -263,6 +260,9 @@ class TestWeightedPath(WeightedTestBase):
             nx.dijkstra_predecessor_and_distance,
         ):
             pytest.raises(nx.NodeNotFound, fn, G, 3, 0)
+            # Test when source == target, which is handled specially by some
+            # functions
+            pytest.raises(nx.NodeNotFound, fn, G, 3, 3)
 
     def test_dijkstra_predecessor1(self):
         G = nx.path_graph(4)
@@ -506,6 +506,7 @@ class TestBellmanFordAndGoldbergRadzik(WeightedTestBase):
             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):
diff --git a/networkx/algorithms/shortest_paths/weighted.py b/networkx/algorithms/shortest_paths/weighted.py
index f721a1be..5a03f66c 100644
--- a/networkx/algorithms/shortest_paths/weighted.py
+++ b/networkx/algorithms/shortest_paths/weighted.py
@@ -225,6 +225,8 @@ def dijkstra_path_length(G, source, target, weight="weight"):
     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)
@@ -618,6 +620,9 @@ def multi_source_dijkstra_path_length(G, sources, cutoff=None, weight="weight"):
     """
     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)
 
@@ -723,6 +728,9 @@ def multi_source_dijkstra(G, sources, target=None, cutoff=None, weight="weight")
     """
     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)
@@ -815,8 +823,6 @@ def _dijkstra_multisource(
     c = count()
     fringe = []
     for source in sources:
-        if source not in G:
-            raise nx.NodeNotFound(f"Source {source} not in G")
         seen[source] = 0
         push(fringe, (0, next(c), source))
     while fringe:
@@ -923,7 +929,8 @@ def dijkstra_predecessor_and_distance(G, source, cutoff=None, weight="weight"):
     >>> 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))
@@ -1448,6 +1455,8 @@ def bellman_ford_path_length(G, source, target, weight="weight"):
     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)
@@ -1633,6 +1642,8 @@ def single_source_bellman_ford(G, source, target=None, weight="weight"):
     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)
diff --git a/networkx/algorithms/simple_paths.py b/networkx/algorithms/simple_paths.py
index 4b1f60ac..e4a53b24 100644
--- a/networkx/algorithms/simple_paths.py
+++ b/networkx/algorithms/simple_paths.py
@@ -825,6 +825,8 @@ def _bidirectional_dijkstra(
     if ignore_nodes and (source in ignore_nodes or target in ignore_nodes):
         raise nx.NetworkXNoPath(f"No path between {source} and {target}.")
     if source == target:
+        if source not in G:
+            raise nx.NodeNotFound(f"Node {source} not in graph")
         return (0, [source])
 
     # handle either directed or undirected