How to write shortest path algorithm in Python?

How to write the shortest path algorithm in Python?

The shortest path algorithm is an algorithm used to find the shortest path from the start node to the target node in a graph with weighted edges. Among them, the two most famous and classic algorithms are Dijkstra's algorithm and A* algorithm. This article will describe how to write these two algorithms using Python and provide code examples.

1. Dijkstra's algorithm

Dijkstra's algorithm is a greedy algorithm for finding the shortest path in a graph with non-negative edge weights. It starts with a starting node and gradually expands to other nodes until the target node is found or all possible nodes are expanded. The specific steps are as follows:

1) Create a set S to save the nodes of the determined shortest path.
2) Initialize the starting node as the current node, set its shortest path length to 0, and set the shortest path lengths of other nodes to infinity.
3) Traverse the nodes adjacent to the current node and update their shortest path length to the path length of the current node plus the weight of the edge.
4) Select the nearest node from the nodes with undetermined shortest path as the new current node and add it to the set S.
5) Repeat steps 3 and 4 until the target node is determined to be the shortest path, and the algorithm ends.

The following is a code example for implementing Dijkstra's algorithm in Python:

def dijkstra(graph, start, end):
    # 节点集合
    nodes = set(graph.keys())
    # 起始节点到各个节点的最短路径长度字典
    distance = {node: float('inf') for node in nodes}
    # 起始节点到各个节点的最短路径字典
    path = {node: [] for node in nodes}
    # 起始节点到自身的最短路径长度为0
    distance[start] = 0

    while nodes:
        # 找到当前节点中最小距离的节点
        min_node = min(nodes, key=lambda node: distance[node])
        nodes.remove(min_node)

        for neighbor, weight in graph[min_node].items():
            # 计算经过当前节点到相邻节点的路径长度
            new_distance = distance[min_node] + weight
            if new_distance < distance[neighbor]:
                # 更新最短路径
                distance[neighbor] = new_distance
                path[neighbor] = path[min_node] + [min_node]

    return distance[end], path[end] + [end]

2. A* algorithm

The A* algorithm is a valuation search algorithm. For solving shortest paths in weighted graphs with heuristic functions. It estimates the path length from the current node to the target node through a heuristic function, and selects the node with the smallest estimate for search. The specific steps are as follows:

1) Create a priority queue to store nodes and their valuations.
2) Initialize the starting node as the current node and add it to the priority queue.
3) Take the node with the smallest valuation from the priority queue as the current node.
4) If the current node is the target node, the algorithm ends and the shortest path is returned.
5) Traverse the nodes adjacent to the current node, calculate their valuation and add them to the priority queue.
6) Repeat steps 3 to 5 until the target node is found or the priority queue is empty, then the algorithm ends.

The following is a code example to implement the A* algorithm in Python:

from queue import PriorityQueue

def heuristic(node, end):
    # 启发式函数，估计从当前节点到目标节点的路径长度
    return abs(node[0] - end[0]) + abs(node[1] - end[1])

def a_star(graph, start, end):
    # 起始节点到各个节点的最短路径字典
    path = {start: []}
    # 起始节点到各个节点的路径估值字典
    f_value = {start: heuristic(start, end)}
    # 创建一个优先队列，用于存储节点及其估值
    queue = PriorityQueue()
    queue.put((f_value[start], start))

    while not queue.empty():
        _, current = queue.get()

        if current == end:
            return path[current] + [end]

        for neighbor in graph[current]:
            next_node = path[current] + [current]
            if neighbor not in path or len(next_node) < len(path[neighbor]):
                # 更新最短路径
                path[neighbor] = next_node
                # 更新路径估值
                f_value[neighbor] = len(next_node) + heuristic(neighbor, end)
                queue.put((f_value[neighbor], neighbor))

    return None

Summary

Through the above code example, we can see how to use Python to write the shortest path algorithm, including Dijkstra's algorithm and A* algorithm. These two algorithms are very effective for solving the shortest path problem on weighted graphs. In practical applications, suitable algorithms can be selected according to specific needs to improve the efficiency and accuracy of the algorithm.

The above is the detailed content of How to write shortest path algorithm in Python?. For more information, please follow other related articles on the PHP Chinese website!