Shortest Path (Dijkstra) algorithm using NumPy

Code Feedback
1

Hello there!
I just finished the Shortest Path Algorithm project in Python curriculum. To understand it deeper I’ve readen some materials on this topic and decided to try to write my own implementation using adjecency matrix.

Here is my code. Would appreciate any comments and suggests how it could be improved!

import numpy as np

na = np.nan
graph = np.array([[0, 7, 9, na, na, 14],
                  [7, 0, 10, 15, na, na],
                  [9, 10, 0, 11, na, 2],
                  [na, 15, 11, 0, 6, na],
                  [na, na, na, 6, 0, 9],
                  [14, na, 2, na, 9, 0]])

def dijkstra(graph, start):
    distances = np.fromiter((0 if i == start else np.inf for i in range(len(graph))), dtype='float')
    visited = np.full_like(graph[start], 0, dtype='bool')
    paths = dict.fromkeys(range(len(graph)), [str(start)])

    for _ in range(len(graph)):
        min_distance_node = np.where(distances == distances[~visited].min())[0][0]
        
        for node in range(len(graph)):
            if not graph[min_distance_node, node] > 0:
                continue
            distance_to_node = distances[min_distance_node] + graph[min_distance_node, node]
            if distance_to_node < distances[node] and visited[node] == False:
                distances[node] = distance_to_node
                paths[node] = paths[min_distance_node].copy()
                paths[node].append(str(node))

        visited[min_distance_node] = True

    for node, path in paths.items():
        print(f'The shortest path from node {start} to node {node} is:\n{' -> '.join(path)}\nTotal distance: {distances[node]}', end='\n\n')

    return paths
2

This topic was automatically closed 182 days after the last reply. New replies are no longer allowed.