在Python中使用Dijkstra算法求矩阵中所有路径的成本

import numpy as np
from heapq import heappop, heappush

def dijkstra(matrix, start):
    rows, cols = matrix.shape
    distances = np.full((rows, cols), np.inf)  # 初始化距离矩阵为无穷大
    distances[start] = 0  # 起始点到自身的距离为0
    heap = [(0, start)]  # 使用堆来保存待处理的节点

    while heap:
        cost, current = heappop(heap)  # 弹出当前最小距离的节点
        if cost > distances[current]:  # 如果当前距离大于已知最小距离，则跳过
            continue

        neighbors = get_neighbors(matrix, current)  # 获取当前节点的邻居节点
        for neighbor in neighbors:
            new_cost = cost + matrix[current][neighbor]  # 计算新的距离
            if new_cost < distances[neighbor]:  # 如果新的距离更小，则更新距离矩阵和堆
                distances[neighbor] = new_cost
                heappush(heap, (new_cost, neighbor))

    return distances

def get_neighbors(matrix, current):
    rows, cols = matrix.shape
    neighbors = []
    if current[0] > 0:  # 上方节点
        neighbors.append((current[0] - 1, current[1]))
    if current[0] < rows - 1:  # 下方节点
        neighbors.append((current[0] + 1, current[1]))
    if current[1] > 0:  # 左方节点
        neighbors.append((current[0], current[1] - 1))
    if current[1] < cols - 1:  # 右方节点
        neighbors.append((current[0], current[1] + 1))
    return neighbors

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

start = (0, 0)
distances = dijkstra(matrix, start)
print(distances)