[QST]: How does SSSP sort distance and predecessor output (old: SSSP returns incorrect distances/costs)

[Friedemannn]

What is your question?

Edit: This is because SSSP returns only predecessors and distances for connected nodes, so the resulting arrays don't have the same size as the input adjaceny matrix dimensions.

Now I'm wondering how I can connect the SSSP results to my old larger index, which relates to the input dimensions.

Original: Hi,

I'm trying SSSP on a undirected weighted graph represented by a scipy COO adjacency matrix of a cost raster (roughly 4000*5000 grid cells) where each fully connected node has 8 neighbors/edges. Connecting the grid cells to their first and second order neighbors.

Because it's undirected only one edge direction is declared in the adjacency matrix, the other is left out.

If I run following code I get wrong distance and predecessor values:

import scipy as sp
import time
import cugraph
#import adjacency matrix
adj = sp.sparse.load_npz('/content/drive/MyDrive/graphs/mb_50m_cost0-union_adj-COO-arr.npz')
#run sssp
a= time.time()
dist, pred = cugraph.sssp(adj, source=10000000, unweighted =True, directed = False)
print(time.time()-a)
>>> /usr/local/lib/python3.10/dist-packages/cugraph/structure/symmetrize.py:92: FutureWarning: Multi is deprecated and the removal of multi edges will no longer be supported from 'symmetrize'. Multi edges will be removed upon creation of graph instance. warnings.warn(
>>> 9.302005767822266

dist[10005000]
>>> 3.0163074

pred[10000001]
>>> 16485534

From other packages such as networkit, networkx, scipy and graph-tool I know that the distance from node 10005000 should be 1.0297332260524854 and the predecessor of node 10000001 should be 10000000.

Did I do something wrong? Should I input a matrix where every edge is explicitly defined?

You can find the adjacency matrix I used here, together with the google colab notebook I used.

Code of Conduct

• [X] I agree to follow cuGraph's Code of Conduct
• [X] I have searched the open issues and have found no duplicates for this question