Repository: scipy/scipy
Pull request: BUG: scipy.sparse.csgraph: fixed issue #10774
<!-- 
Thanks for contributing a pull request! Please ensure that
your PR satisfies the checklist before submitting:
http://scipy.github.io/devdocs/dev/contributor/development_workflow.html#checklist-before-submitting-a-pr

Also, please name and describe your PR as you would write a
commit message:
https://docs.scipy.org/doc/numpy/dev/development_workflow.html#writing-the-commit-message

Note that we are a team of volunteers; we appreciate your
patience during the review process.

Again, thanks for contributing!
-->

#### Reference issue
<!--Example: Closes gh-WXYZ.-->
Closes #10774
#### What does this implement/fix?

When duplicate indices were passed to scipy.sparse.csgraph.djisktra with the min_only=True option the same vertex was added multiple times to the heap which later resulted in an infinite loop. Fixed by adding a check before insertion. 

Problem statement:
min_only=true djisktra infinite loop with duplicate indices
<!-- 
Thank you for taking the time to file a bug report. 
Please fill in the fields below, deleting the sections that 
don't apply to your issue. You can view the final output
by clicking the preview button above.
Note: This is a comment, and won't appear in the output.
-->

My issue is about scipy.sparse.csgraph.djisktra with the min_only=True option.

Seems that if you pass duplicate indices into this function you can induce an infinite loop. 

Solution would maybe be to raise an exception in this case?
Or is there a way to a handle it? Take the first unique index as the true target and throw out the others so that no paths lead to them?

#### Reproducing code example:
<!-- 
dist=scipy.sparse.csgraph.djiskstra(csgraph, directed=False, indices = np.array([1,2,2]))
-->

```
Sample code to reproduce the problem
```

#### Error message:
code never returns..



#### Scipy/Numpy/Python version information:
```
1.1.0 1.14.3 sys.version_info(major=3, minor=6, micro=6, releaselevel='final', serial=0)
```
<!-- You can simply run the following and paste the result in a code block
```
>>> import sys, scipy, numpy; print(scipy.__version__, numpy.__version__, sys.version_info)

```
-->

Hints from issue discussion:
@fcollman thanks for the report. Can you add a self-contained code example to reproduce the issue you're seeing?
sure working on it now... I think this is likely a bug with code i submitted so was going to follow it up with a PR that at least has a test with a failure, but hopefully a fix too.
@fcollman that would be great, thanks for looking into it

Commit message: BUG: remove repeated insertion of the same node to the heap in dijkstra

Patch to review:
diff --git a/scipy/sparse/csgraph/_shortest_path.pyx b/scipy/sparse/csgraph/_shortest_path.pyx
index 278d4b96ce59..0ca34303b0d6 100644
--- a/scipy/sparse/csgraph/_shortest_path.pyx
+++ b/scipy/sparse/csgraph/_shortest_path.pyx
@@ -630,6 +630,8 @@ cdef _dijkstra_setup_heap_multi(FibonacciHeap *heap,
     heap.min_node = NULL
     for i in range(Nind):
         j_source = source_indices[i]
+        if nodes[j_source].state == SCANNED:
+            continue
         dist_matrix[j_source] = 0
         if return_pred:
             sources[j_source] = j_source
diff --git a/scipy/sparse/csgraph/tests/test_shortest_path.py b/scipy/sparse/csgraph/tests/test_shortest_path.py
index 0975bc9dace7..946ad06cde84 100644
--- a/scipy/sparse/csgraph/tests/test_shortest_path.py
+++ b/scipy/sparse/csgraph/tests/test_shortest_path.py
@@ -149,7 +149,7 @@ def check(method, directed_in):
 @pytest.mark.parametrize('directed, SP_ans',
                          ((True, directed_SP),
                           (False, undirected_SP)))
-@pytest.mark.parametrize('indices', ([0, 2, 4], [0, 4], [3, 4]))
+@pytest.mark.parametrize('indices', ([0, 2, 4], [0, 4], [3, 4], [0, 0]))
 def test_dijkstra_indices_min_only(directed, SP_ans, indices):
     SP_ans = np.array(SP_ans)
     indices = np.array(indices, dtype=np.int64)


Code review comments:
diff_hunk: @@ -630,6 +630,8 @@ cdef _dijkstra_setup_heap_multi(FibonacciHeap *heap,
     heap.min_node = NULL
     for i in range(Nind):
         j_source = source_indices[i]
+        if nodes[j_source].state == SCANNED:
path: scipy/sparse/csgraph/_shortest_path.pyx
text: @user1:
This might be clearer if you move the `current_node = &nodes[j_source]` line up above this one, then refer to `current_node.state`.