graphs.dijkstra_binary_grid

This script implements the Dijkstra algorithm on a binary grid. The grid consists of 0s and 1s, where 1 represents a walkable node and 0 represents an obstacle. The algorithm finds the shortest path from a start node to a destination node. Diagonal movement can be allowed or disallowed.

Functions

dijkstra(→ tuple[float | int, list[tuple[int, int]]])

Implements Dijkstra's algorithm on a binary grid.

Module Contents

graphs.dijkstra_binary_grid.dijkstra(grid: numpy.ndarray, source: tuple[int, int], destination: tuple[int, int], allow_diagonal: bool) → tuple[float | int, list[tuple[int, int]]]

Implements Dijkstra’s algorithm on a binary grid.

Args:

grid (np.ndarray): A 2D numpy array representing the grid. 1 represents a walkable node and 0 represents an obstacle. source (Tuple[int, int]): A tuple representing the start node. destination (Tuple[int, int]): A tuple representing the destination node. allow_diagonal (bool): A boolean determining whether diagonal movements are allowed.

Returns:

Tuple[Union[float, int], List[Tuple[int, int]]]: The shortest distance from the start node to the destination node and the shortest path as a list of nodes.

>>> dijkstra(np.array([[1, 1, 1], [0, 1, 0], [0, 1, 1]]), (0, 0), (2, 2), False)
(4.0, [(0, 0), (0, 1), (1, 1), (2, 1), (2, 2)])

>>> dijkstra(np.array([[1, 1, 1], [0, 1, 0], [0, 1, 1]]), (0, 0), (2, 2), True)
(2.0, [(0, 0), (1, 1), (2, 2)])

>>> dijkstra(np.array([[1, 1, 1], [0, 0, 1], [0, 1, 1]]), (0, 0), (2, 2), False)
(4.0, [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2)])