Zephyr's Notes on ISCS & CBMS, UTokyo

寻路算法

Nov 16, 202417 min read

寻路算法 | Pathfinding Algorithms

定义 | Definition

寻路算法是用于在图或网格中找到从一个点到另一个点的路径的算法。寻路算法在导航、机器人、游戏开发和网络路由等领域有广泛应用。

Pathfinding algorithms are used to find a path from one point to another in a graph or grid. These algorithms are widely used in navigation, robotics, game development, and network routing.

常见算法 | Common Algorithms

深度优先搜索 (DFS) | Depth-First Search (DFS)

DFS 是一种递归的图遍历算法，从起始节点开始，沿着一条路径一直走到底，再回溯寻找其他路径，直到找到目标节点或遍历完所有节点。

DFS is a recursive graph traversal algorithm that starts at the root node and explores as far as possible along each branch before backtracking to find other paths, until the target node is found or all nodes are visited.

def dfs(graph, start, goal, path=None):
    if path is None:
        path = []
    path.append(start)
    if start == goal:
        return path
    for neighbor in graph[start]:
        if neighbor not in path:
            result = dfs(graph, neighbor, goal, path)
            if result:
                return result
    path.pop()
    return None
 
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}
 
path = dfs(graph, 'A', 'F')
print(path)  # Output: ['A', 'B', 'E', 'F']

广度优先搜索 (BFS) | Breadth-First Search (BFS)

BFS 是一种遍历算法，从起始节点开始，按层次依次访问每一层的节点，直到找到目标节点或遍历完所有节点。BFS 保证找到的是最短路径。

BFS is a traversal algorithm that starts at the root node and visits all nodes at the present depth level before moving on to nodes at the next depth level, until the target node is found or all nodes are visited. BFS guarantees finding the shortest path.

from collections import deque
 
def bfs(graph, start, goal):
    queue = deque([(start, [start])])
    while queue:
        (vertex, path) = queue.popleft()
        for next in set(graph[vertex]) - set(path):
            if next == goal:
                return path + [next]
            else:
                queue.append((next, path + [next]))
    return None
 
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}
 
path = bfs(graph, 'A', 'F')
print(path)  # Output: ['A', 'C', 'F']

Dijkstra 算法 | Dijkstra’s Algorithm

Dijkstra 算法是一种经典的单源最短路径算法，适用于边权非负的图。其基本思想是逐步扩展已知最短路径的顶点集，保证每次选择的是当前最短的路径。该算法广泛应用于路由、地图导航等领域。

Dijkstra’s algorithm is a classic single-source shortest path algorithm suitable for graphs with non-negative edge weights. The basic idea is to incrementally expand the set of vertices with known shortest paths, ensuring that the shortest path is always chosen. This algorithm is widely used in routing, map navigation, and similar applications.

算法步骤 | Algorithm Steps

  1. 初始化距离数组，将起点的距离设为 0，其他顶点的距离设为无穷大。

  2. 将所有顶点添加到优先队列中，起点的优先级最高。

  3. 重复以下步骤，直到优先队列为空：

    • 取出优先级最高的顶点 。
    • 更新与顶点 相邻的顶点的距离，如果通过 到达这些顶点的距离更短，则更新它们的优先级。

  4. 所有顶点的距离即为从起点到这些顶点的最短路径长度。

  5. Initialize the distance array, setting the source distance to 0 and all other vertices’ distances to infinity.

  6. Add all vertices to a priority queue, with the source having the highest priority.

  7. Repeat the following steps until the priority queue is empty:

    • Extract the vertex with the highest priority.
    • Update the distances of the vertices adjacent to . If a shorter path is found through , update their priorities.

  8. The distances to all vertices represent the shortest path lengths from the source to these vertices.

算法巧妙之处 | Algorithm Ingenuity

  • 贪心策略 | Greedy Strategy: Dijkstra 算法采用贪心策略，每次选择当前已知的最短路径，逐步构建最终的最短路径树。这种局部最优选择的策略保证了全局最优解。 Greedy Strategy: Dijkstra’s algorithm uses a greedy strategy, choosing the currently known shortest path to progressively build the final shortest path tree. This strategy of local optimal choice ensures a globally optimal solution.
  • 优先队列 | Priority Queue: 使用优先队列（通常是最小堆）来高效地选择和更新最短路径顶点，使得每次提取和更新操作的时间复杂度为 。优先队列显著提高了算法的效率，尤其在稀疏图中表现尤为突出。 Priority Queue: Utilizing a priority queue (typically a min-heap) to efficiently select and update the shortest path vertices, making each extraction and update operation . The priority queue significantly enhances the algorithm’s efficiency, especially in sparse graphs.
  • 松弛操作 | Relaxation: 松弛操作是 Dijkstra 算法的核心，通过比较和更新顶点的最短距离，确保每个顶点都能通过最短路径到达。 Relaxation: Relaxation is the core of Dijkstra’s algorithm. By comparing and updating the shortest distances of vertices, it ensures that every vertex is reachable via the shortest path.
import heapq
 
def dijkstra(graph, start):
    queue = [(0, start)]
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0
    while queue:
        current_distance, current_vertex = heapq.heappop(queue)
        if current_distance > distances[current_vertex]:
            continue
        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(queue, (distance, neighbor))
    return distances
 
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'D': 2, 'E': 5},
    'C': {'A': 4, 'F': 3},
    'D': {'B': 2},
    'E': {'B': 5, 'F': 1},
    'F': {'C': 3, 'E': 1}
}
 
distances = dijkstra(graph, 'A')
print(distances)  # Output: {'A': 0, 'B': 1, 'C': 4, 'D': 3, 'E': 6, 'F': 5}

堆在 Dijkstra 算法中的作用 | Role of Heaps in Dijkstra’s Algorithm

  • 高效优先级操作 | Efficient Priority Operations: 使用最小堆可以高效地进行优先级操作，每次提取最小值和插入新元素的时间复杂度为 。

  • 动态更新顶点距离 | Dynamic Distance Updates: 堆允许动态更新顶点的优先级（即距离），在每次松弛操作后，可以快速调整顶点在堆中的位置。

  • 减少重复计算 | Reduce Redundant Calculations: 堆确保每次总是选择当前最短路径的顶点进行扩展，避免了不必要的计算和重复遍历，提高了算法的整体效率。

  • Efficient Priority Operations: Using a min-heap allows for efficient priority operations, with each extraction of the minimum value and insertion of new elements having a time complexity of .

  • Dynamic Distance Updates: The heap allows dynamic updates to the priority (distance) of vertices. After each relaxation operation, the position of the vertices in the heap can be quickly adjusted.

  • Reduce Redundant Calculations: The heap ensures that the vertex with the current shortest path is always chosen for expansion, avoiding unnecessary calculations and redundant traversals, thereby improving the overall efficiency of the algorithm.

Dijkstra 算法是一种单源最短路径算法，适用于非负权重图。它通过逐步扩展路径，确保每次选择的是当前已知最短路径，最终找到从起始点到所有其他点的最短路径。

Dijkstra’s algorithm is a single-source shortest path algorithm suitable for graphs with non-negative weights. It incrementally expands the shortest known path, ensuring that the shortest path is found from the start point to all other points.

import heapq
 
def dijkstra(graph, start):
    queue = [(0, start)]
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0
    while queue:
        current_distance, current_vertex = heapq.heappop(queue)
        if current_distance > distances[current_vertex]:
            continue
        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(queue, (distance, neighbor))
    return distances
 
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'D': 2, 'E': 5},
    'C': {'A': 4, 'F': 3},
    'D': {'B': 2},
    'E': {'B': 5, 'F': 1},
    'F': {'C': 3, 'E': 1}
}
 
distances = dijkstra(graph, 'A')
print(distances)  # Output: {'A': 0, 'B': 1, 'C': 4, 'D': 3, 'E': 6, 'F': 5}

A* 算法 | A* Algorithm

A* 算法结合了 Dijkstra 算法的最短路径搜索和启发式搜索的优点，使用启发式函数估计当前点到目标点的距离，优先扩展估计成本最低的路径。

A* algorithm combines the advantages of Dijkstra’s algorithm and heuristic search. It uses a heuristic function to estimate the distance from the current point to the goal, prioritizing the path with the lowest estimated cost.

import heapq
 
def heuristic(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])
 
def a_star(graph, start, goal):
    queue = [(0, start)]
    came_from = {}
    g_score = {vertex: float('infinity') for vertex in graph}
    g_score[start] = 0
    f_score = {vertex: float('infinity') for vertex in graph}
    f_score[start] = heuristic(start, goal)
    
    while queue:
        _, current = heapq.heappop(queue)
        if current == goal:
            path = []
            while current in came_from:
                path.append(current)
                current = came_from[current]
            path.append(start)
            return path[::-1]
        
        for neighbor, cost in graph[current].items():
            tentative_g_score = g_score[current] + cost
            if tentative_g_score < g_score[neighbor]:
                came_from[neighbor] = current
                g_score[neighbor] = tentative_g_score
                f_score[neighbor] = g_score[neighbor] + heuristic(neighbor, goal)
                heapq.heappush(queue, (f_score[neighbor], neighbor))
    return None
 
graph = {
    (0, 0): {(1, 0): 1, (0, 1): 1},
    (1, 0): {(0, 0): 1, (1, 1): 1},
    (0, 1): {(0, 0): 1, (1, 1): 1},
    (1, 1): {(1, 0): 1, (0, 1): 1, (2, 2): 1},
    (2, 2): {(1, 1): 1}
}
 
path = a_star(graph, (0, 0), (2, 2))
print(path)  # Output: [(0, 0), (0, 1), (1, 1), (2, 2)]

进阶知识 | Advanced Knowledge

负权重环 | Negative Weight Cycle

定义 | Definition

负权重环是指在一个有向图中，一个环（即一条从某顶点出发，经过若干条边，又回到该顶点的路径）的所有边的权重和为负数。负权重环在图算法中特别重要，因为它会导致无穷小的路径权重，影响最短路径的计算。

A negative weight cycle is a cycle in a directed graph where the sum of the edge weights is negative. Negative weight cycles are significant in graph algorithms because they lead to paths with infinitely decreasing weights, affecting the calculation of the shortest paths.

影响 | Impact

  • 路径权重无穷小 | Infinitely Small Path Weights: 由于负权重环的存在，可以通过多次循环该环，使得路径的总权重无限减小，导致没有真正的最短路径。

  • 算法失效 | Algorithm Failure: 负权重环会使得某些算法（如 Dijkstra 算法）无法正确工作，因为这些算法假设路径权重总是增加的。

  • 无解情况 | No Solution: 在包含负权重环的图中，尝试找到从某个顶点到另一个顶点的最短路径可能没有解，因为路径权重可以无限减小。

  • Infinitely Small Path Weights: Due to the presence of a negative weight cycle, repeatedly traversing the cycle can make the total path weight infinitely small, resulting in no true shortest path.

  • Algorithm Failure: Negative weight cycles cause certain algorithms (like Dijkstra’s algorithm) to fail, as these algorithms assume path weights always increase.

  • No Solution: In graphs with negative weight cycles, finding the shortest path from one vertex to another may be impossible because the path weight can decrease indefinitely.

检测负权重环 | Detecting Negative Weight Cycle

Bellman-Ford 算法不仅可以计算单源最短路径，还可以检测图中是否存在负权重环。具体步骤如下：

  1. 初始化距离数组，将起点的距离设为 0，其他顶点的距离设为无穷大。
  2. 对所有边进行 次松弛操作，更新距离数组。
  3. 进行第 次松弛操作，如果某个边还能被松弛，则图中存在负权重环。

The Bellman-Ford algorithm not only computes the shortest paths from a single source but also detects the presence of negative weight cycles in a graph. The steps are:

  1. Initialize the distance array, setting the source distance to 0 and all other vertices’ distances to infinity.
  2. Perform relaxation for all edges times to update the distance array.
  3. Perform the -th relaxation. If any edge can still be relaxed, a negative weight cycle exists in the graph.
def bellman_ford(graph, start):
    distance = {vertex: float('infinity') for vertex in graph}
    distance[start] = 0
    for _ in range(len(graph) - 1):
        for u in graph:
            for v, weight in graph[u].items():
                if distance[u] + weight < distance[v]:
                    distance[v] = distance[u] + weight
    for u in graph:
        for v, weight in graph[u].items():
            if distance[u] + weight < distance[v]:
                return True  # 存在负权重环 | Negative weight cycle exists
    return False  # 不存在负权重环 | No negative weight cycle
 
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'C': -3, 'D': 2, 'E': 2},
    'C': {},
    'D': {'B': 1, 'C': 5},
    'E': {'D': -3}
}
 
has_negative_cycle = bellman_ford(graph, 'A')
print(has_negative_cycle)  # Output: True

处理负权重环 | Handling Negative Weight Cycle

  • 修改图结构 | Modify Graph Structure: 如果可以，修改图中的权重，使其不包含负权重环。

  • 使用适当算法 | Use Appropriate Algorithms: 使用 Bellman-Ford 或 Floyd-Warshall 算法，这些算法能够处理负权重边并检测负权重环。

  • 报告无解情况 | Report No Solution: 在应用中，检测到负权重环时应及时报告，提示路径计算无解或需特殊处理。

  • Modify Graph Structure: If possible, modify the weights in the graph to eliminate negative weight cycles.

  • Use Appropriate Algorithms: Use Bellman-Ford or Floyd-Warshall algorithms, which can handle negative weight edges and detect negative weight cycles.

  • Report No Solution: In applications, if a negative weight cycle is detected, report it promptly, indicating that path computation is unsolvable or needs special handling.

Bellman-Ford 算法 | Bellman-Ford Algorithm

Bellman-Ford 算法适用于含有负权重边的图，可以找到单源最短路径，并且能够检测负权重环的存在。

The Bellman-Ford algorithm is suitable for graphs with negative weight edges. It can find the shortest path from a single source and detect the presence of negative weight cycles.

def bellman_ford(graph, start):
    distance = {vertex: float('infinity') for vertex in graph}
    distance[start] = 0
    for _ in range(len(graph) - 1):
        for u in graph:
            for v, weight in graph[u].items():
                if distance[u] + weight < distance[v]:
                    distance[v] = distance[u] + weight
    for u in graph:
        for v, weight in graph[u].items():
            if distance[u] + weight < distance[v]:
                raise ValueError("Graph contains a negative weight cycle")
    return distance
 
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'C': -3, 'D': 2, 'E': 2},
    'C': {},
    'D': {'B': 1, 'C': 5},
    'E': {'D': -3}
}
 
distances = bellman_ford(graph, 'A')
print(distances)  # Output: {'A': 0, 'B': 1, 'C': -2, 'D': -2, 'E': 3}

Floyd-Warshall 算法 | Floyd-Warshall Algorithm

Floyd-Warshall 算法是一种动态规划算法，用于找到所有顶点对之间的最短路径。它适用于含有负权重边但不含负权重环的图。

The Floyd-Warshall algorithm is a dynamic programming algorithm used to find the shortest paths between all pairs of vertices. It is suitable for graphs with negative weight edges but without negative weight cycles.

def floyd_warshall(graph):
    distance = {u: {v: float('infinity') for v in graph} for u in graph}
    for u in graph:
        distance[u][u] = 0
        for v, weight in graph[u].items():
            distance[u][v] = weight
    for k in graph:
        for i in graph:
            for j in graph:
                distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])
    return distance
 
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'C': -3, 'D': 2, 'E': 2},
    'C': {},
    'D': {'B': 1, 'C': 5},
    'E': {'D': -3}
}
 
distances = floyd_warshall(graph)
print(distances)
# Output: {'A': {'A': 0, 'B': 1, 'C': -2, 'D': 0, 'E': 3}, ...}

常见问题 | Common Issues

  • 负权重边处理 | Handling Negative Weight Edges: 在处理含有负权重边的图时，Dijkstra 算法不能使用，应使用 Bellman-Ford 或 Floyd-Warshall 算法。

  • 循环依赖 | Cyclic Dependencies: 寻路过程中可能会遇到循环依赖，应确保算法能够正确处理，避免无限循环。

  • Handling Negative Weight Edges: When dealing with graphs that have negative weight edges, Dijkstra’s algorithm should not be used. Instead, use Bellman-Ford or Floyd-Warshall algorithms.

  • Cyclic Dependencies: During pathfinding, cyclic dependencies might be encountered. Ensure that the algorithm can correctly handle them to avoid infinite loops.

Graph View

Backlinks