I’m trying to implement A* search algorithm to solve TSP problem.
Here’s the code I’ve written so far:

import heapq


#def kruskal_mst(graph):...


def mst_heuristic(graph, current_city, unvisited_cities):
    nearest_unvisited_distance = float('inf')
    for city in unvisited_cities:
        if city in graph[current_city]:  # Check if there is a direct connection between current_city and city
            distance = graph[current_city][city]
            if distance < nearest_unvisited_distance:
                nearest_unvisited_distance = distance
    nearest_to_start_distance = graph[current_city]['A'] if current_city != 'A' else 0
    #mst_weight = kruskal_mst(graph)
    return nearest_to_start_distance


def a_star_tsp(graph, start_city):
    visited = set()
    unvisited = set(graph.keys())
    unvisited.remove(start_city)
    num_nodes = len(graph)
    priority_queue = [(0, start_city, [start_city], {start_city})]

    while priority_queue:
        print("Priority Queue:", priority_queue)
        cost, current_city, path, path_set = heapq.heappop(priority_queue)
        print("Current City:", current_city)
        visited.add(current_city)

        # Calculate nearest_to_start_distance only once for each city
        nearest_to_start_distance = mst_heuristic(graph, current_city, {start_city})

        for next_city, edge_cost in graph[current_city].items():
            if next_city not in path_set:
                new_path = path + [next_city]
                new_path_set = path_set.copy()
                new_path_set.add(next_city)
                g_n = cost + edge_cost
                # Calculate nearest_unvisited_distance only once for each city
                nearest_unvisited_distance = mst_heuristic(graph, next_city, unvisited)
                f_n = g_n + nearest_unvisited_distance
                heapq.heappush(priority_queue, (f_n, next_city, new_path, new_path_set))

        # Check if all paths in priority queue have the same length as the number of nodes
        if all(len(p) == num_nodes for _, _, p, _ in priority_queue):
            min_cost_path = min(priority_queue, key=lambda x: x[0])[2]
            min_cost = sum(graph[min_cost_path[i]][min_cost_path[i + 1]] for i in range(len(min_cost_path) - 1))
            min_cost += graph[min_cost_path[-1]][start_city]
            min_cost_path.append(start_city)
            print(f"Priority Queue:{priority_queue}n")
            print("Optimal TSP path:", min_cost_path)
            return min_cost_path

    # If priority queue is empty and all nodes are expanded, return the lowest cost path found so far
    if not priority_queue:
        return path

    # If priority queue is empty and all nodes are expanded, return the lowest cost path found so far
    if not priority_queue:
        return path


# Example usage:
cities = {
    'A': {'B': 10, 'C': 15, 'D': 20},
    'B': {'A': 10, 'C': 20, 'D': 25},
    'C': {'A': 15, 'B': 20, 'D': 30},
    'D': {'A': 20, 'B': 25, 'C': 30}
}

start_city = 'A'
queue = a_star_tsp(cities, start_city)

The nearest_to_start_distance must simply show the distance between each node to the starting (A in this example) point. Now if we take node B as an example, the distance between it and A is 10, while the program returns another value and keeps increasing it. Let’s explain what I mean with an example.

I’m only considering f(n) based on the nearest_to_start_distance for explaining popuse.
If I run the program now, here’s a part of the result I get:

Priority Queue: [(0, 'A', ['A'], {'A'})]
Current City: A
Priority Queue: [(20, 'B', ['A', 'B'], {'A', 'B'}), (30, 'C', ['A', 'C'], {'A', 'C'}), (40, 'D', ['A', 'D'], {'A', 'D'})]
Current City: B
Priority Queue: [(30, 'C', ['A', 'C'], {'A', 'C'}), (40, 'D', ['A', 'D'], {'A', 'D'}), (55, 'C', ['A', 'B', 'C'], {'A', 'B', 'C'}), (65, 'D', ['A', 'B', 'D'], {'A', 'B', 'D'})]
Current City: C
Priority Queue: [(40, 'D', ['A', 'D'], {'A', 'D'}), (60, 'B', ['A', 'C', 'B'], {'A', 'C', 'B'}), (55, 'C', ['A', 'B', 'C'], {'A', 'B', 'C'}), (65, 'D', ['A', 'B', 'D'], {'A', 'B', 'D'}), (80, 'D', ['A', 'C', 'D'], {'A', 'C', 'D'})]
Current City: D

For the first Priority Queue, the cost (f_n) is correctly set to zero. But in the next step, when Current City is B (In this priority queue i mean: (20, 'B', ['A', 'B'], {'A', 'B'})) the cost is 20, while it had to be 10 according to the graph!!
More overwhelmingly, in another case where the Current City is B again (here for example: (60, 'B', ['A', 'C', 'B'], {'A', 'C', 'B'})), the cost has increased and I’ve been thinking on it for hours but been unable to find out the reason for why this is happening. It had to be 10 in all cases where Current City is B as the distance between B to A is 10 in the graph.
Can anyone figure the reason out.