Время выполнения для кратчайшего P alg в невзвешенном неориентированном графе в python3

Question

Для такой проблемы я подумал, что было бы лучше сделать какую-то BFS-подобную реализациюЯ не знаю, почему после некоторого тестирования во время выполнения вышел сюжет, напоминающий экспоненциальную функцию.

Итак, я начал думать о правильности моего кода: действительно ли он эффективен?Можете ли вы помочь мне сделать анализ времени выполнения для хорошего алгоритма?

Я составил график базы 1.5 для оси X (так как в коде я использую список первых 30 степеней1.5 как число вершин, введенных в случайный граф ()По-прежнему выглядит экспоненциально ...

def bfs_short(graph, source, target):
    visited = set()
    queue = collections.deque([source])

    d={}
    d[source]=0

    while queue:
        u = queue.pop()
        if u==target:
            return d[target]
        if u not in visited:
            visited.add(u)
            for w in graph[u]:
                if w not in visited:
                    queue.appendleft(w)
                    d[w]=d[u]+1

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

Answer 1

Проблема в вашем коде состоит в том, что ваша очередь не учитывает расстояние до начала координат, чтобы расставить приоритеты для следующей вершины, в которой она появится.
Кроме того, collections.deque не является приоритетной очередью, и, следовательно, не даст вам ближайшую невидимую вершину, которую вы видели до сих пор, когда извлекаете из нее элемент.
Это следует сделать, используя heapq, встроенную реализацию кучи:

import heapq

def bfs_short(graph, source, target):
    visited = set()
    queue = [(0, source)]
    heapq.heapify(queue)
    while not queue:
        dist, vertex = heapq.heappop(queue)
        if vertex == target:
            return dist
        if vertex not in visited:
            visited.add(vertex)
            for neighbor in graph[vertex]:
                if neighbor not in visited:
                    heapq.heappush(queue, (dist + 1, neighbor))

В этой версии пары помещаются в очередь. Чтобы оценить и сравнить кортежи, Python пытается сравнить их первый элемент, затем второй в случае равенства и так далее.
Таким образом, нажав dist(vertex, origin) в качестве первого члена кортежа, наименьшая пара (dist, vertex) в куче также будет ближайшей к исходной вершине.