基于限制路径的Dijkstra算法

基于限制路径的Dijkstra算法是对标准的Dijkstra算法的一种改进。该算法在为每个节点计算最短路径时，会对路径进行限制，只有满足限制条件的路径才会被考虑。这种限制可以用于许多场景，例如限制最大距离、限制通过某些节点等。

以下是一种基于限制路径的Dijkstra算法的简单实现，其中限制条件为不通过编号为2的节点：

from queue import PriorityQueue

def dijkstra(graph, start, end):
    queue = PriorityQueue()
    queue.put((0, start))
    visited = set()

    while not queue.empty():
        (cost, node) = queue.get()
        if node in visited:
            continue
        visited.add(node)

        if node == end:
            return cost

        for neighbor in graph[node]:
            if neighbor[0] != 2 and neighbor[1] not in visited:
                queue.put((cost + neighbor[0], neighbor[1]))

    return -1

graph = [
    [(1, 1), (2, 5)],     # 0 -> (1, 1), 0 -> (2, 5)
    [(1, 0), (1, 2)],     # 1 -> (0, 1), 1 -> (2, 2)
    [(5, 0), (1, 1)],     # 2 -> (0, 5), 2 -> (1, 1)
]

print(dijkstra(graph, 0, 2))    # output: 2

在上述代码示例中，使用了一个优先队列来存储待处理的节点，每次从队列中取出距离起点最短的节点进行处理。若该节点满足限制条件，则不会去考虑它能到达的节点。如果该节点是终点，则返回该路径的总代价；如果无法到达终点，则返回-1