Untitled

 avatar
unknown
plain_text
6 months ago
1.3 kB
7
Indexable
import queue

def breadth_first_search_with_heuristics(graph, G1, G2):
    # Rečnici za čuvanje udaljenosti od G1 i G2 do svakog čvora
    distance_G1 = {node: float('inf') for node in graph}
    distance_G2 = {node: float('inf') for node in graph}

    # BFS za izračunavanje najkraćih udaljenosti od G1
    def bfs(start, distance):
        q = queue.Queue()
        q.put(start)
        distance[start] = 0

        while not q.empty():
            node = q.get()
            for neighbor, weight in graph[node]:
                if distance[neighbor] > distance[node] + weight:
                    distance[neighbor] = distance[node] + weight
                    q.put(neighbor)

    # Pokrećemo BFS za G1 i G2
    bfs(G1, distance_G1)
    bfs(G2, distance_G2)

    # Kreiramo heuristiku za svaki čvor kao minimalnu udaljenost do G1 ili G2
    heuristika = {}
    for node in graph:
        heuristika[node] = min(distance_G1[node], distance_G2[node])

    return heuristika

# Primer grafa za testiranje
graph = {
    1: [(2, 4), (5, 7)],
    2: [(1, 4), (3, 1), (5, 3)],
    3: [(2, 1), (4, 3)],
    4: [(3, 3), (5, 2)],
    5: [(1, 7), (2, 3), (4, 2)]
}

G1, G2 = 1, 5
heuristika = breadth_first_search_with_heuristics(graph, G1, G2)
print("Heuristika za svaki čvor:", heuristika)
Editor is loading...
Leave a Comment