请写出改进Dijkstra算法的奖励机制和非完全贪心策略的算法代码

改进Dijkstra算法的奖励机制和非完全贪心策略可以用A*算法实现。A*算法基于Dijkstra算法，在Dijkstra算法的基础上增加了启发式函数，通过启发式函数的预估值来进行优化搜索。具体实现如下：

def A_star(start, end, graph, heuristic):
    # 初始化起点和终点的信息，包括距离和路径
    distance = {node: float("inf") for node in graph}
    distance[start] = 0
    path = {start: []}
    current_node = start

    while current_node != end:
        # 遍历当前节点的所有邻接节点，计算距离和启发式函数值
        for neighbor in graph[current_node]:
            # 计算该节点前往邻居节点的距离
            tentative_distance = distance[current_node] + graph[current_node][neighbor]
            if tentative_distance < distance[neighbor]:
                # 更新当前路径和距离
                distance[neighbor] = tentative_distance
                path[neighbor] = path[current_node] + [current_node]
                # 计算启发式函数值
                f_score = tentative_distance + heuristic(neighbor, end)
                # 将邻居节点加入开放列表
                open_list.put((f_score, neighbor))
        # 从开放列表中选择下一个节点
        if not open_list.empty():
            current_node = open_list.get()[1]
        else:
            # 如果开放列表为空则说明无法到达终点，直接返回
            return "Path does not exist"
    # 返回最短路径和距离
    return path[end] + [end], distance[end]

其中，启发式函数可以根据具体情况进行设计。例如，对于地图搜索问题，可以将启发式函数设置为当前节点到终点的欧几里得距离。

在非完全贪心策略中，可以将每个节点的邻居节点按照一定的规则排序，先考虑距离较近的节点。具体实现如下：

def non_greedy_dijkstra(start, end, graph):
    # 初始化起点和终点的信息，包括距离和路径
    distance = {node: float("inf") for node in graph}
    distance[start] = 0
    path = {start: []}
    visited = []
    current_node = start

    while current_node != end:
        # 遍历当前节点的所有邻接节点，并按照距离排序
        sorted_neighbors = sorted(graph[current_node].items(), key=lambda x: x[1])
        for neighbor, weight in sorted_neighbors:
            # 计算该节点前往邻居节点的距离
            tentative_distance = distance[current_node] + weight
            if tentative_distance < distance[neighbor]:
                # 更新当前路径和距离
                distance[neighbor] = tentative_distance
                path[neighbor] = path[current_node] + [current_node]
        # 将当前节点加入已访问列表，并选择下一个节点
        visited.append(current_node)
        unvisited_neighbors = {node: distance[node] for node in graph if node not in visited}
        if not unvisited_neighbors:
            # 如果所有节点都已访问，则说明无法到达终点，直接返回
            return "Path does not exist"
        current_node = min(unvisited_neighbors, key=unvisited_neighbors.get)
    # 返回最短路径和距离
    return path[end] + [end], distance[end]