将BFS转换为Djikstra求最短路径

2024-03-28 14:14:35 发布

您现在位置:Python中文网/ 问答频道 /正文

如何使用Djikstra将以下BFS算法转换为最短路径?我知道我需要更新邻居的距离,但是我不知道如何用它来扩展下面的BFS。限制条件是我们只能沿着两个节点之间的L形路径移动。你知道吗

from collections import deque

N = 8
board_p = [[(-1,-1) for f in range(0,N)] for i in range(0,N)]

def Adjacents(u):    
    adj = []
    for e in [(-2,-1),(-2,1),(2,1),(2,-1),(-1,-2),(1,-2),(-1,2),(1,2)]:        
        v = (u[0] + e[0], u[1] + e[1])
        if v[0] >= 0 and v[0] < N and v[1] >= 0 and v[1] < N: adj.append(v)
    return adj;

def Moves(s,t):
    q = deque()
    q.append(s)
    board_p[s[0]][s[1]] = s # "root" of BFS-traversal points to it self (avoid loop over "back-edge" to s)
    while q:
        u = q.popleft()
        if u == t: break
        for v in Adjacents(u):
            if board_p[v[0]][v[1]] == (-1,-1):
                board_p[v[0]][v[1]] = u
                q.append(v)

    # walk the path back (using parent "pointers")
    path = [(t)]    
    while t != s:
        t = board_p[t[0]][t[1]]
        path.append(t)

    path.reverse()
    return path


print(Moves((1,1),(5,5)))

Tags: andpathin路径boardforreturnif