CODEWITHSUNDEEP
pythonnetworkxdijkstra
Dark_fish
Dark_fish

Reputation: 11

Networkx is_negatively_weighted Is False, But Use Dijkstra Return ('Contradictory paths found:', 'negative weights?')

I wanted to use a gragh to get a shortest path,but networkx tiped me 'ValueError: ('Contradictory paths found:', 'negative weights?')'.After that,i checked all the gragh edges,they were all bigger the zero. In the end, I uesd the nx.is_negatively_weighted(G, weight='weight'), which return False.however,Dijkstra also return ('Contradictory paths found:', 'negative weights?') when I tried to find shortest path. the following is my code:

def Get_Shortest_Car_To_Cus_Path(  # 获得车辆到乘客的最短路径
        car_names,  # 符合条件的车辆编号们 (就算单个pd.data对象也没事)
        cus_name,  # 目标乘客
        car_updata: bool = False,  # 是否更新节点的车辆信息
        cus_updata: bool = False,  # 是否更新节点的乘客信息
        weight: str = 'weight',  # 计算最短路径的权重名称，有三类（weight， shape_len， wgs84_length）
        **kwargs
):
    G = kwargs['G']
    # G = G.copy()  # 创建副本，从副本导出
    if car_updata:  # 更新节点的车辆信息
        G = Updata_G_Map_Car(
            car_names=car_names,
            **kwargs)
    # 添加乘客的O点
    if cus_updata:
        G = Updata_G_Map_cus(
            cus_names=[cus_name],
            **kwargs
        )
    print(nx.is_negatively_weighted(G, weight='weight'))
    if len(car_names) != 1:
        length, path = nx.multi_source_dijkstra(G=G, sources=set(car_names), target=cus_name + '_出发地',
                                                weight=weight)
    else:
        path = nx.dijkstra_path(G=G, source=str(car_names), target=cus_name + '_出发地', weight=weight)
        length = path_lenght(G=G, path=path, weight=weight)
    path = get_pure_path(old_path=path)
    return length, path

Every time I try to find shortest path,nx.is_negatively_weighted(G, weight='weight') tell me the gragh is not negative,but the nx.multi_source_dijkstra() tell me the graph has negative weights. Why that happen?

Upvotes: 1

Views: 1203

Answers (2)

Lea
Lea

Reputation: 1

can't agree any more! Check the weights of edges

Upvotes: 0

Junze Yang
Junze Yang

Reputation: 31

I have met the same problem that there are actually no negatively weighted edges in the network，but it gave me this error when conducting traffic assignment. I finally found that it was not the problem of negatively weighted edges but those with infinite weights (inf or np.nan) that concern. Suggest checking it and the error will disappear.

Upvotes: 1

Related Questions