Bellman Ford

The bellman_ford() method can also compute the shortest paths between all pairs of elements and is capable of handling negative edge weights.

Example

Determine the shortest path from element 1 to element 2 in the given graph, which includes a negative weight.

import numpy as np
from scipy.sparse.csgraph import bellman_ford
from scipy.sparse import csr_matrix

arr = np.array([
  [0, –1, 2],
  [1, 0, 0],
  [2, 0, 0]
])

newarr = csr_matrix(arr)

print(bellman_ford(newarr, return_predecessors=True, indices=0))

Depth First Order

The depth_first_order() method performs a depth-first traversal starting from a given node.

It takes the following arguments:

The graph.
The starting element for the traversal.

Example

Perform a depth-first traversal on the graph using the given adjacency matrix.

import numpy as np
from scipy.sparse.csgraph import depth_first_order
from scipy.sparse import csr_matrix

arr = np.array([
  [0, 1, 0, 1],
  [1, 1, 1, 1],
  [2, 1, 1, 0],
  [0, 1, 0, 1]
])

newarr = csr_matrix(arr)

print(depth_first_order(newarr, 1))

Breadth First Order

The breadth_first_order() method returns a breadth-first traversal starting from a specified node.

It accepts the following arguments:

The graph.
The starting element from which to begin the traversal.

Example

Perform a breadth-first traversal on the graph using the given adjacency matrix.

import numpy as np
from scipy.sparse.csgraph import breadth_first_order
from scipy.sparse import csr_matrix

arr = np.array([
  [0, 1, 0, 1],
  [1, 1, 1, 1],
  [2, 1, 1, 0],
  [0, 1, 0, 1]
])

newarr = csr_matrix(arr)

print(breadth_first_order(newarr, 1))