Найдите локальный кратчайший путь с помощью жадного алгоритма наилучшего первого поиска

Question

Недавно я сдавал тест по теории алгоритмов. У меня был нормальный лучший первый алгоритм поиска (код ниже).

      from queue import PriorityQueue

# Filling adjacency matrix with empty arrays
vertices = 14
graph = [[] for i in range(vertices)]


# Function for adding edges to graph
def add_edge(x, y, cost):
    graph[x].append((y, cost))
    graph[y].append((x, cost))


# Function For Implementing Best First Search
# Gives output path having the lowest cost
def best_first_search(source, target, vertices):
    visited = [0] * vertices
    pq = PriorityQueue()
    pq.put((0, source))
    print("Path: ")
    while not pq.empty():
        u = pq.get()[1]
        # Displaying the path having the lowest cost
        print(u, end=" ")
        if u == target:
            break

        for v, c in graph[u]:
            if not visited[v]:
                visited[v] = True
                pq.put((c, v))
    print()


if __name__ == '__main__':
    # The nodes shown in above example(by alphabets) are
    # implemented using integers add_edge(x,y,cost);
    add_edge(0, 1, 1)
    add_edge(0, 2, 8)
    add_edge(1, 2, 12)
    add_edge(1, 4, 13)
    add_edge(2, 3, 6)
    add_edge(4, 3, 3)

    source = 0
    target = 2
    best_first_search(source, target, vertices)

Он выводит Path: 0 1 0 2 (сумма пути — 8), это правильно.

Мой учитель предложил мне переделать код так, чтобы он искал локальный минимальный путь, т.е. Path: 0 1 2 (сумма путей — 13).

Мне нужно жадно взять кратчайшее ребро от текущего узла к непосещенному узлу, и я не очень понимаю, как это сделать правильно.

Answer 1

Поскольку это домашнее задание, я не буду расшифровывать вам весь код.

Для поиска по первому наилучшему вам не нужна очередь с приоритетом. Вам просто нужно отслеживать, какие узлы вы посетили и на каком узле находитесь в данный момент. Пока ваш текущий узел не является целевым узлом, найдите кратчайшее ребро, ведущее к непосещенному узлу, и установите текущий узел на узел на другом конце этого ребра.