Inf = float('inf')

# 输入矩阵，获取矩阵的行列数
arr = [[0, 0, 1, 2, 3],
       [0, 4, 0, 0, 0],
       [0, 0, 0, 5, 0],
       [6, 7, 8, 9, 0]]
rows, cols = len(arr), len(arr[0])

# 初始化距离邻接表，端点编号从左到右从上到下依次排序。如上面的arr第一排编号为0,1,2,3,4,第二排为5,6,7,8,9.
Adjacent = []
for row in range(rows):
    for col in range(cols):
        tmp = []
        for a in range(rows):
            for b in range(cols):
                if abs(a - row) + abs(b - col) <= 1:
                    tmp.append(abs(arr[row][col] - arr[a][b]))
                else:
                    tmp.append(Inf)
        Adjacent.append(list(tmp))


# 设置起始点和目标点，以及端点总数N。例子4行5列共20端点，从左上到右下即从0到19号。
start, target, N = 0, rows * cols - 1, rows * cols


def dijkstra(adj, src, dst, n):
    visited = [0] * n
    dist = adj[src]
    visited[src] = 1
    for _ in range(n - 1):
        u = src
        min_dist = Inf

        for v in range(n):
            if not visited[v] and dist[v] < min_dist:
                u = v
                min_dist = dist[v]

        visited[u] = 1
        for w in range(n):
            if not visited[w] and adj[u][w] < Inf:
                if dist[u] + adj[u][w] < dist[w]:
                    dist[w] = dist[u] + adj[u][w]
    return dist[dst]


def floyd(adj, src, dst, n):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                if adj[j][k] > adj[j][i] + adj[i][k]:
                    adj[j][k] = adj[j][i] + adj[i][k]
    return adj[src][dst]


print(dijkstra(Adjacent, start, target, N))
print(floyd(Adjacent, start, target, N))