stp旅行社算法python

STP（Shortest Path First，最短路径优先）算法通常用于图论中的寻找两个节点之间的最短路径问题，比如Dijkstra算法或A*搜索算法就是STP的具体实现。在Python中，我们可以使用内置的数据结构和相关的库来实现这个算法。

**1. Dijkstra算法（适用于非负权重图）：**

import heapq

def dijkstra(graph, start):
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0
    queue = [(0, start)]
    while queue:
        current_distance, current_node = heapq.heappop(queue)
        if current_distance > distances[current_node]:
            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

**2. A*搜索算法（适用于带启发式的图）：**

import heapq

def a_star_search(graph, start, goal, heuristic):
    frontier = [(heuristic(start, goal), start)]
    came_from = {}
    cost_so_far = {start: 0}

    while frontier:
        _, current = heapq.heappop(frontier)

        if current == goal:
            break

        for next_node, cost in graph.get(current, {}).items():
            new_cost = cost_so_far[current] + cost
            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(next_node, goal)
                heapq.heappush(frontier, (priority, next_node))
                came_from[next_node] = current

    return came_from, cost_so_far

# 使用时提供合适的启发式函数（如曼哈顿距离或欧几里得距离）

**相关问题--:**
1. 在Python中如何用Dijkstra算法找出图中两点的最短路径？
2. A*搜索算法相比Dijkstra算法有什么优势？
3. 在实现A*算法时，启发式函数的作用是什么？