Найти минимальное значение в словаре объектов - PullRequest
Новая
       5

Найти минимальное значение в словаре объектов

0 голосов
/ 18 октября 2018

Я работаю над реализацией алгоритма Джикстры, и у меня есть проблема в цикле for.В этом цикле я обновляю каждый узел от «бесконечности» до «расстояния».Важно то, что я не знаю, как заставить следующий узел следовать по пути в поисках минимального «расстояния».Я работаю с Networkx на Python, и я не могу использовать реализованный алгоритм Джикстра.Это мой закомментированный код: 

def dijkstra(G, origen, destino, infinity=float(9999999999999999999.9)):
    [G.add_node(i, distance = infinity, prev = None) for i in G.nodes() if 
    G.node[i]!= origen] #set all 'distance' to infinity except soure node(origen)

    G.add_node(origen,distance= 0, prev = None)
    pathFound = False #I will stop when found my destiny node in the loop
    exploredNode = origen #SourceNode for the loop start
    fastPath=[] #Fast path between source node and destiny node.
    fastPath.append(exploredNode)
    nodeNeighbours = list(G.neighbors(origen)) #Neighbors of source node
    while not pathFound:
        for nodes in nodeNeighbours :
            G.node[nodes]['distance'] = (G.get_edge_data(exploredNode,nodes)['distance'])+(G.node[exploredNode]['distance'])
        #main loop, only implemented the update of the distance, looking for implement the min 'distance with nodes

Примечания. Все узлы спроектированы по номеру, и я обращаюсь к ним с помощью G.node [число].Это вернет словарь со всеми атрибутами.У каждого узла есть словарь со своими значениями: {'line': 4, 'distance': 0.321831}

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

1 Ответ

0 голосов
/ 18 октября 2018

Несколько идей:

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

  2. Первая строка также вызывает метод add_node ().Хотите добавить новые узлы или просто обновить существующие?Точка установки расстояния до бесконечности узла и до None заключается в том, что они еще не были замечены.Это стандартный первый шаг в алгоритме поиска по графику.

  3. Я не знаю NetworkX, но в целом будьте осторожны при обновлении структуры данных и выполнении поиска в ней втот же цикл.

  4. Когда pathFound будет когда-либо установлен в True?(Я знаю, что вы не написали полный алгоритм, но уточните!) Я думаю, что этот цикл должен сказать вместо этого:

    while fastPath: # While the queue is not empty v = fastPath.pop() # The node with minimum distance (use a priority queue)

    , а затем перебрать смежность v. Смотрите. python docs на "Использование списков как очередей" (вы, вероятно, захотите, чтобы это сортировалось по расстоянию).

    Dijkstra - это особый случай поиска в ширину (или наоборот), поэтому он поддерживает очередь посещаемых узлов.Ваш источник является изученным (исследуемый может означать больше, чем просто посещенный, но это правда, что источник посещен), но код не появляется из очереди узлов для посещения в цикле while.Какой узел поп?Передняя часть очереди должна иметь узел с минимальным расстоянием, которое в первой итерации будет источником, его расстояние устанавливается равным нулю, а все остальные узлы равны бесконечности.Вот как алгоритм начинает поиск с начала координат.fastPath выглядит как попытка этой очереди, но не завершена.(Поместите туда каждый узел!) Я бы порекомендовал изучить, как работает BFS (ссылка), что сделает Дейкстру более понятным.Не торопитесь!

...