Python：最短加权路径和最少边数

我正在使用networkx加权图来建模交通网络。我试图根据加权边的总和来找到最短路径。我用Dijkstra路径来找到这条路。我的问题发生在加权边缘方面。当发生这种情况时，我总是希望从绑定的路径集合中选择具有最少边数的路径。 Dijkstra路径似乎没有这样做。Python：最短加权路径和最少边数

有没有一种方法可以确保我可以从一组路径中选择具有最少边数的路径，这些路径根据加权边的总和进行关联？

来源

2017-02-03 thecornman

我应该加入：我也尝试过使用all_shortest_paths;返回所有具有最少边数的路径....我想我可以返回这组路径并选择具有最小加权边的总和的路径。但是，我无法弄清楚如何获得这些路径的加权边的总和以伴随它们。我得到最短路径的生成器对象（根据边的数量）....是否有一种简单的方法来显示加权边和路径的总和？ – thecornman

而不是使用浮点的权重，使用元组(weight, number_of_edges)成对添加。使用这些新权重的最低权重路径将具有最低权重，并且在配合情况下是最短路径。

要定义这些权重，我将使它们成为tuple的子类，并重新定义__add__。那么你应该可以使用你现有的代码。

来源

2017-02-03 17:14:44 btilly

如何将权重设为元组我有点困惑.......如果我将权重参数设置为元组，networkx似乎不支持添加数据类型以获取最短路径距离 – thecornman

@thecornman使用在http://stackoverflow.com/a/15919466/585411解决方案来定义添加正确的元组。您将需要'从itertools import izip'，并且通过使用'mytup（（weight，length））'传递一个元组来构造权重。那些特殊的元组应该流经普通的python和Do The Right Thing。 – btilly

Python：最短加权路径和最少边数

回答

相关问题