Как справиться с ошибкой цикла отрицательной стоимости при вычислении кратчайшего пути с отрицательными весами с помощью networkx?

Я использую networkx для решения проблем кратчайшего пути. Я хотел бы иметь возможность использовать graph_negative weight

Когда я попытался запустить алгоритм кратчайшего пути с помощью метода Bellman-ford (см. Код ниже), я получил ошибку NetworkXUnbounded: Negative cost cycle detected.

import matplotlib.pyplot as plt
from itertools import combinations, groupby
import os
import numpy as np
import networkx as nx
import random


# 1. Define test network 
MG = nx.MultiDiGraph()
MG.add_edges_from([("B", "A", {"length": 0.8}), ("A", "B", {"length": 1.}), ("D", "G", {"length": 3.5}),
                   ("B", "D", {"length": 20.8}), ("A", "C", {"length": 9.7}), ("D", "C", {"length": 0.3}),
                   ("B", "E", {"length": 4.8}), ("D", "E", {"length": 0.05}), ("C", "E", {"length": 0.1}),          
                   ("E", "C", {"length": 0.7}), ("E", "F", {"length": 0.4}), ("E", "G", {"length": 15.}),           
                   ("F", "C", {"length": 0.9}), ("F", "D", {"length": 4.}),                       
                  ])
attrs = {'B': {"x": -20., "y": 60.}, 'A': {"x": 28., "y":55.},
         'C': {"x": -12., "y": 40.}, 'D': {"x": 40., "y":45.},
         'E': {"x": 8., "y": 35.}, 'F': {"x": -8., "y":15.},    
         'G': {"x": 21., "y":5.},    
        }

for num, (k,v) in enumerate(attrs.items()):
    attrs[k]={**v,
             }  
nx.set_node_attributes(MG, attrs)

rng = np.random.default_rng(seed=42)
random_height = list(rng.uniform(low=-100, high=100, size=len(MG.edges)).round(0))
attrs={}
for num, edge in enumerate(MG.edges):
    attrs[edge]={'height': random_height[num]}
nx.set_edge_attributes(MG, attrs)


# 2. Calculate shortest route
best_route_by_length = nx.shortest_path(MG, "A", "G",weight="length")
print(f"Best route by length: {best_route_by_length}")

best_route_by_height = nx.shortest_path(MG, "A", "G",weight="height",method='bellman-ford')
print(f"Best route by height: {best_route_by_height}")

Есть ли способ решить эту проблему (например, удалить цикл)?

Изменить: ищу оптимальное решение без циклов


python shortest-path networkx graph-theory
person lhoupert    schedule 25.05.2021    source источник
comment
Не могли бы вы пояснить, что вы считаете хорошим решением? Если есть цикл, которому может следовать алгоритм, вы можете обойти этот цикл несколько раз, продолжая снижать вес пути. Итак, как бы вы определили минимальный путь в вашем случае, чтобы этого избежать? Итак, в вашем 2-м примере я мог бы выбрать путь, который несколько раз повторял C- ›E-› F, и он был бы меньше вашего.   -  person Joel    schedule 25.05.2021
comment
Привет, @Joel, спасибо за ваш комментарий. Я должен был упомянуть, что ищу решение без циклов. Отредактирую свой вопрос.   -  person lhoupert    schedule 25.05.2021

Ответы (1)


arrow_upward
0
arrow_downward

Одно из решений этой проблемы:

  1. создать копию моего графика, где все атрибуты ребер height сдвинуты на наименьшее отрицательное значение (таким образом, весь мой вес положителен)
  2. вычислил кратчайший путь на этом новом графике

Но на самом деле это не так просто, поскольку требуется работать с двумя графами или вычислять дополнительные преобразования.

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

import copy 

MH=copy.deepcopy(MG)

attrs={}
for num, edge in enumerate(MH.edges):
    attrs[edge] = MH.edges[edge]
    attrs[edge]['height'] += - np.min(random_height)
nx.set_node_attributes(MH, attrs)

best_route_by_height_shifted_negative = nx.shortest_path(MH, "A", "G",weight="height")
print(f"Best route by height (weight shifted by minimum negative weight): {best_route_by_height_zero_negative}")

# 3. Get stats for each route

def get_route_edge_attributes(
    G, route, attribute=None, minimize_key="length", retrieve_default=None
):
    """
    """
    attribute_values = []
    for u, v in zip(route[:-1], route[1:]):
        # if there are parallel edges between two nodes, select the one with the
        # lowest value of minimize_key
        data = min(G.get_edge_data(u, v).values(), key=lambda x: x[minimize_key])
        if attribute is None:
            attribute_value = data
        elif retrieve_default is not None:
            attribute_value = data.get(attribute, retrieve_default(u, v))
        else:
            attribute_value = data[attribute]
        attribute_values.append(attribute_value)
    return attribute_values


stats_best_route={}
stats_best_route['by_length']={'length': sum(get_route_edge_attributes(MG,
                                                                   best_route_by_length,
                                                                  'length')),
                              'height': sum(get_route_edge_attributes(MG,
                                                                   best_route_by_length,
                                                                  'height'))}
stats_best_route['by_height_with_negative']={'length': sum(get_route_edge_attributes(MG,
                                                                   best_route_by_height_shifted_negative,
                                                                  'length')),
                              'height': sum(get_route_edge_attributes(MG,
                                                                   best_route_by_height_shifted_negative,
                                                                  'height'))}

print(f"Stats best routes: {stats_best_route}")


Best route by height (weight shifted by minimum negative weight): ['A', 'C', 'E', 'G']
Stats best routes: {'by_length': {'length': 13.7, 'height': 245.0}, 'by_height_with_negative': {'length': 24.8, 'height': -70.0}}
person lhoupert    schedule 25.05.2021
comment
Это может потерпеть неудачу - рассмотрим ребро A-B с весом 1, а затем альтернативный путь A-C-D-B, с первым ребром с весом -1/2, вторым весом 0 и третьим с весом 3/4. Тогда общий вес пути ACDB равен 1/4, что меньше, чем у ребра A-B. Но если мы сдвинем все на 1/2, тогда путь ACDB будет иметь вес 1,75, а ребро A-B - 1,5. Таким образом, порядок меняется, потому что количество ребер влияет на то, насколько смещается вес пути. - person Joel; 30.05.2021