o1-preview-2024-09-12· OpenAI WildChat-4.8M (AI2)
Implement dijkstra algorithm in 3d, optimized and professional
- User
Implement dijkstra algorithm in 3d, optimized and professional
- Assistant
Certainly! Below is an optimized and professional implementation of Dijkstra's algorithm for a 3D grid using Python. This implementation utilizes a priority queue for efficient selection of the next node with the smallest tentative distance and is designed to handle grids with varying costs for moving through cells.
import heapq from typing import List, Tuple, Optional import numpy as np def dijkstra_3d( grid: np.ndarray, start: Tuple[int, int, int], end: Optional[Tuple[int, int, int]] = None ) -> Tuple[np.ndarray, Optional[List[Tuple[int, int, int]]]]: """ Performs Dijkstra's algorithm on a 3D grid to find the shortest path from start to end. Parameters: grid (np.ndarray): A 3D numpy array representing the grid with traversal costs. grid[z, y, x] gives the cost to move through cell (x, y, z). start (Tuple[int, int, int]): The starting cell coordinates as (x, y, z). end (Optional[Tuple[int, int, int]]): The target cell coordinates as (x, y, z). If None, calculates distances to all reachable cells. Returns: Tuple[np.ndarray, Optional[List[Tuple[int, int, int]]]]: A tuple containing: - distances: A 3D numpy array with the minimum distances from start to each cell. - path: A list of cell coordinates representing the shortest path from start to end. Returns None if end is None or no path is found. """ # Validate input coordinates assert grid.ndim == 3, "Grid must be a 3D numpy array." Nz, Ny, Nx = grid.shape sx, sy, sz = start assert 0 <= sx < Nx and 0 <= sy < Ny and 0 <= sz < Nz, "Start coordinates out of grid bounds." if end is not None: ex, ey, ez = end assert 0 <= ex < Nx and 0 <= ey < Ny and 0 <= ez < Nz, "End coordinates out of grid bounds." # Initialize distances array with infinity and set the start cell distance to its cost distances = np.full((Nz, Ny, Nx), np.inf, dtype=np.float64) distances[sz, sy, sx] = grid[sz, sy, sx] # Initialize priority queue with the start cell heap: List[Tuple[float, Tuple[int, int, int]]] = [] heapq.heappush(heap, (distances[sz, sy, sx], (sx, sy, sz))) # Directions for movement in 3D (6-connected grid) directions = [ (-1, 0, 0), (1, 0, 0), # X-axis neighbors (0, -1, 0), (0, 1, 0), # Y-axis neighbors (0, 0, -1), (0, 0, 1) # Z-axis neighbors ] # Array to keep track of visited cells visited = np.zeros((Nz, Ny, Nx), dtype=bool) # Parent dictionary to reconstruct the shortest path parents: Dict[Tuple[int, int, int], Tuple[int, int, int]] = {} while heap: current_dist, (x, y, z) = heapq.heappop(heap) if visited[z, y, x]: continue visited[z, y, x] = True if end is not None and (x, y, z) == end: break # Target reached # Explore neighboring cells for dx, dy, dz in directions: nx, ny, nz = x + dx, y + dy, z + dz # Check bounds and whether the neighbor has been visited if 0 <= nx < Nx and 0 <= ny < Ny and 0 <= nz < Nz and not visited[nz, ny, nx]: cost = grid[nz, ny, nx] if np.isinf(cost): continue # Impassable cell new_dist = current_dist + cost if new_dist < distances[nz, ny, nx]: distances[nz, ny, nx] = new_dist heapq.heappush(heap, (new_dist, (nx, ny, nz))) parents[(nx, ny, nz)] = (x, y, z) # Reconstruct the shortest path from start to end path: Optional[List[Tuple[int, int, int]]] = None if end is not None: if visited[ez, ey, ex]: # Path exists, reconstruct it path = [] cell = end while cell != start: path.append(cell) cell = parents[cell] path.append(start) path.reverse() else: path = None # No path found return distances, pathImplementation Details:
-
Data Structures:
- Grid (
np.ndarray): Represents the 3D grid where each cell contains the cost to traverse that cell. - Distances (
np.ndarray): Holds the minimum distances from the start to every other cell initialized withnp.inf. - Visited (
np.ndarray): A boolean array to keep track of visited cells. - Heap (
List): A priority queue (min-heap) to select the next node with the smallest tentative distance. - Parents (
Dict): A dictionary to reconstruct the shortest path from the end node back to the start node.
- Grid (
-
Algorithm Steps:
- Initialization: Set the distance to the start node as its traversal cost and add it to the priority queue.
- Main Loop: While the priority queue is not empty:
- Pop the cell with the smallest tentative distance.
- Mark it as visited.
- If the end cell is reached, exit the loop.
- For all unvisited neighbors:
- Calculate the new tentative distance.
- If the new distance is less than the previously recorded distance, update it.
- Push the neighbor onto the heap with the updated distance.
- Record the current cell as the parent of the neighbor.
- Path Reconstruction: If an end node was specified and reached, reconstruct the path from the end node back to the start node using the
parentsdictionary.
-
Optimization Techniques:
- Priority Queue: Efficiently retrieves the cell with the smallest tentative distance.
- Early Exit: Stops the algorithm once the end cell is reached to avoid unnecessary computations.
- NumPy Arrays: Efficient numerical operations and memory usage for large grids.
- Type Hinting: Improves code readability and catches potential type-related bugs.
Usage Example:
# Example grid (3D numpy array) import numpy as np # Create a 5x5x5 grid with traversal cost of 1 for all cells grid_size = (5, 5, 5) grid = np.ones(grid_size) # Impassable cell (setting cost to infinity) grid[2, 2, 2] = np.inf start = (0, 0, 0) end = (4, 4, 4) # Find shortest path using Dijkstra's algorithm distances, path = dijkstra_3d(grid, start, end) if path is not None: print(f"Shortest path from {start} to {end}:") for cell in path: print(cell) else: print(f"No path found from {start} to {end}.")Notes:
- The function can calculate distances to all reachable cells if
endis set toNone. In this case, it returns thedistancesarray andpathwill beNone. - Cells with infinite cost (
np.inf) are considered impassable. - Adjust the
directionslist if diagonal movement is allowed or different connectivity is required.
This implementation provides a solid foundation for pathfinding in a 3D environment and can be adapted or extended for specific applications, such as robotics, gaming, or 3D mapping.
-