最短路徑演算法python

最短路徑算法有許多種，其中最常用的包括Dijkstra算法和A*搜尋算法。以下是使用Python實現Dijkstra算法的示例代碼：

import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    queue = [(0, start)]
    while queue:
        current_distance, current_node = heapq.heappop(queue)
        if distances[current_node] < current_distance:
            continue
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(queue, (distance, neighbor))
    return distances

這個算法接受一個圖和一個起始節點作為輸入，並返回一個字典，其中包含從起始節點到每個節點的最短距離。該算法使用一個優先佇列來保持待處理的節點列表，以便優先處理距離較短的節點。在每次疊代中，算法會遍歷當前節點的所有鄰居，並更新它們的最短距離。

使用A*搜尋算法實現最短路徑算法的示例代碼如下：

import heapq

def astar(graph, start, goal):
    frontier = [(0, start)]
    came_from = {}
    cost_so_far = {}
    came_from[start] = None
    cost_so_far[start] = 0
    while frontier:
        current = heapq.heappop(frontier)[1]
        if current == goal:
            break
        for next_node, cost in graph[current].items():
            new_cost = cost + cost_so_far[current]
            if next_node not in cost_so_far or new_cost < cost_so_far[next_node]:
                cost_so_far[next_node] = new_cost
                priority = new_cost + heuristic(goal, next_node)
                heapq.heappush(frontier, (priority, next_node))
                came_from[next_node] = current
    return came_from, cost_so_far

這個算法使用一個優先佇列來保持待處理的節點列表，並使用啟發式函式來估計每個節點的目標距離。在這個實現中，啟發式函式使用了曼哈頓距離作為啟發式函式的權重。這個算法通過將路徑中的所有節點及其父節點存儲在字典中來返回最短路徑。