calculate shortest path using dijkstra's algorithm

dijkstra_example.py

# define distance matrix
import scipy as sp

A = sp.array([[0,2,0,5,0,0],
              [2,0,1,3,4,0],
              [0,1,0,4,0,0],
              [5,3,4,0,2,4],
              [0,4,0,2,0,1],
              [0,0,0,4,1,0]])

num_node = A.shape[0]

# make a sparse matrix
from scipy.sparse import csr_matrix
dist_sparse = csr_matrix(A)

# run Dijkstra's algorithm
start_node = 0
end_node   = 5
from scipy.sparse.csgraph import dijkstra
dist, pred = dijkstra(dist_sparse, indices = start_node, return_predecessors=True)

# print out the distance from start_node to end_node
print("distance from {0:d} to {1:d}: {2:4.2f}.".format(start_node,end_node,dist[end_node]))

# print out the path
path = []
i=end_node

if sp.isinf(dist[end_node]):
    print('the path does not exist!')
else:
    while i!=start_node:
            path.append(i)
            i = pred[i]
            
    path.append(start_node)
    print('path=',path[::-1])

# show the sparsity of the distance matrix
import matplotlib.pyplot as plt
plt.spy(dist_sparse)