Создайте взвешенный граф networkx и найдите путь между двумя узлами с наименьшим весом - PullRequest
Новая
       14

Создайте взвешенный граф networkx и найдите путь между двумя узлами с наименьшим весом

0 голосов
/ 28 марта 2019

У меня проблема с теорией графов. Чтобы решить эту проблему, я хотел бы создать взвешенный график с использованием networkx. На данный момент у меня есть словарь, в котором каждый ключ является узлом, а каждое значение - это связанный вес (от 10 до 200 000 или около того). 

weights = {node: weight}

Полагаю, мне не нужно нормализовать вес в сетях. На данный момент я создаю невзвешенный граф, добавляя ребра: 

def create_graph(data):
    edges = create_edges(data)

    # Create the graph
    G = nx.Graph()

    # Add edges
    G.add_edges_from(edges)

    return G

Из того, что я прочитал, я могу добавить вес к краю. Однако я бы предпочел, чтобы вес применялся к конкретному узлу, а не к ребру. Как я могу это сделать?

Идея: Я создаю график, добавляя взвешенные узлы, а затем добавляю ребра между узлами. 

def create_graph(data, weights):
    nodes = create_nodes(data)
    edges = create_edges(data) # list of tuples

    # Create the graph
    G = nx.Graph()

    # Add edges
    for node in nodes:
        G.add_node(node, weight=weights[node])

    # Add edges
    G.add_edges_from(edges)

    return G

Является ли этот подход правильным?

Следующий шаг - найти путь между 2 узлами с наименьшим весом. Я нашел эту функцию: networkx.algorithms.shortest_paths.generic.shortest_path, которая, я думаю, делает правильные вещи. Однако он использует веса на ребре, а не веса на узлах. Может ли кто-нибудь объяснить мне, что делает эта функция, в чем разница между весами на узлах и весами на краях для networkx, и как мне достичь того, что я ищу? Спасибо:)

1 Ответ

1 голос
/ 29 марта 2019

Обычно это выглядит правильно.

Вы можете использовать bidirectional_dijkstra .Это может быть значительно быстрее, если вы знаете исходные и целевые узлы вашего пути (см. Мои комментарии внизу).

Чтобы решить проблему веса ребра и узла, есть два варианта.Сначала обратите внимание, что вы после суммы узлов по пути.Если я присваиваю каждому ребру вес w(u,v) = w(u) + w(v), то сумма весов по нему равна w(source) + w(target) + 2 sum(w(v)), где узлы v - это все узлы, найденные на этом пути.Все, что имеет минимальный вес с этими весами ребер, будет иметь минимальный вес с весами узлов.

Таким образом, вы можете пойти и назначить каждому ребру вес, который будет суммой двух узлов.

for edge in G.edges():
    G.edges[edge]['weight'] = G.nodes[edge[0]]['weight'] + G.nodes[edge[1]]['weight']

Но альтернатива состоит в том, чтобы отметить, что вес, введенный в bidirectional_dijkstra, может быть функцией, которая принимает ребро в качестве ввода.Определите свою собственную функцию, чтобы получить сумму весов двух узлов: 

def f(edge):
    u,v = edge
    return G.nodes[u]['weight'] + G.nodes[v]['weight']

, а затем в своем вызове выполните bidirectional_dijkstra(G, source, target, weight=f)

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

Некоторые комментарии к двунаправленной дижкрахте: представьте, что у вас есть две точки в пространстве на расстоянии R друг от друга, и вы хотитенайти кратчайшее расстояние между ними.Алгоритм dijkstra (который является значением по умолчанию для shorttest_path) исследует каждую точку на расстоянии D от исходной точки.По сути это похоже на расширение воздушного шара с центром в первой точке, пока он не достигнет другой.Это имеет объем (4/3) пи R ^ 3.С bidirectional_dijkstra мы раздуваем воздушные шары по центру каждого, пока они не коснутся.Каждый из них будет иметь радиус R / 2.Таким образом, объем равен (4/3) пи (R / 2) ^ 3 + (4/3) пи (R / 2) ^ 3, что составляет четверть объема исходного шара, поэтому алгоритм исследовал четвертьпространства.Поскольку сети могут иметь очень высокое эффективное измерение, экономия часто намного больше.

...