Python中文网 - 问答频道, 解决您学习工作中的Python难题和Bug
Python常见问题
生成树的顶点大约为100万个。我想知道是否有一种有效的方法来找到一个给定顶点和许多其他顶点之间的最短路径。在
下面是一个顶点数较少的示例图（110）
nodes = [(0.0, {'label': 2}) ,
(1.0, {'label': 2}) ,
(2.0, {'label': 0}) ,
(3.0, {'label': 2}) ,
(4.0, {'label': 2}) ,
(5.0, {'label': 0}) ,
(6.0, {'label': 0}) ,
(7.0, {'label': 2}) ,
(8.0, {'label': 2}) ,
(9.0, {'label': 1}) ,
(10.0, {'label': 0}) ,
(11.0, {'label': 1}) ,
(12.0, {'label': 1}) ,
(13.0, {'label': 0}) ,
(14.0, {'label': 1}) ,
(15.0, {'label': 2}) ,
(16.0, {'label': 1}) ,
(17.0, {'label': 1}) ,
(18.0, {'label': 2}) ,
(19.0, {'label': 2}) ,
(20.0, {'label': 0}) ,
(21.0, {'label': 1}) ,
(22.0, {'label': 1}) ,
(23.0, {'label': 0}) ,
(24.0, {'label': 1}) ,
(25.0, {'label': 2}) ,
(26.0, {'label': 0}) ,
(27.0, {'label': 0}) ,
(28.0, {'label': 1}) ,
(29.0, {'label': 0}) ,
(30.0, {'label': 2}) ,
(31.0, {'label': 1}) ,
(32.0, {'label': 2}) ,
(33.0, {'label': 1}) ,
(34.0, {'label': 1}) ,
(35.0, {'label': 1}) ,
(36.0, {'label': 1}) ,
(37.0, {'label': 2}) ,
(38.0, {'label': 0}) ,
(39.0, {'label': 0}) ,
(40.0, {'label': 2}) ,
(41.0, {'label': 0}) ,
(42.0, {'label': 1}) ,
(43.0, {'label': 0}) ,
(44.0, {'label': 0}) ,
(45.0, {'label': 2}) ,
(46.0, {'label': 0}) ,
(47.0, {'label': 2}) ,
(48.0, {'label': 0}) ,
(49.0, {'label': 1}) ,
(50.0, {'label': 0}) ,
(51.0, {'label': 1}) ,
(52.0, {'label': 2}) ,
(53.0, {'label': 0}) ,
(54.0, {'label': 1}) ,
(55.0, {'label': 1}) ,
(56.0, {'label': 2}) ,
(57.0, {'label': 1}) ,
(58.0, {'label': 1}) ,
(59.0, {'label': 0}) ,
(60.0, {'label': 2}) ,
(61.0, {'label': 1}) ,
(62.0, {'label': 1}) ,
(63.0, {'label': 2}) ,
(64.0, {'label': 0}) ,
(65.0, {'label': 0}) ,
(66.0, {'label': 0}) ,
(67.0, {'label': 0}) ,
(68.0, {'label': 1}) ,
(69.0, {'label': 2}) ,
(70.0, {'label': 0}) ,
(71.0, {'label': 1}) ,
(72.0, {'label': 0}) ,
(73.0, {'label': 2}) ,
(74.0, {'label': 0}) ,
(75.0, {'label': 1}) ,
(76.0, {'label': 1}) ,
(77.0, {'label': 0}) ,
(78.0, {'label': 2}) ,
(79.0, {'label': 2}) ,
(80.0, {'label': 2}) ,
(81.0, {'label': 1}) ,
(82.0, {'label': 2}) ,
(83.0, {'label': 2}) ,
(84.0, {'label': 1}) ,
(85.0, {'label': 0}) ,
(86.0, {'label': 1}) ,
(87.0, {'label': 2}) ,
(88.0, {'label': 1}) ,
(89.0, {'label': 0}) ,
(90.0, {'label': 0}) ,
(91.0, {'label': 2}) ,
(92.0, {'label': 0}) ,
(93.0, {'label': 1}) ,
(94.0, {'label': 1}) ,
(95.0, {'label': 2}) ,
(96.0, {'label': 2}) ,
(97.0, {'label': 0}) ,
(98.0, {'label': 2}) ,
(99.0, {'label': 2}) ,
(100.0, {'label': -1}) ,
(101.0, {'label': -1}) ,
(102.0, {'label': 1}) ,
(103.0, {'label': -1}) ,
(104.0, {'label': -1}) ,
(105.0, {'label': -1}) ,
(106.0, {'label': -1}) ,
(107.0, {'label': 1}) ,
(108.0, {'label': 0}) ,
(109.0, {'label': -1})]
edges = [(0.0, 25.0, {'weight': 1.3788141613435239}) ,
(0.0, 15.0, {'weight': 1.1948288781935414}) ,
(1.0, 99.0, {'weight': 2.1024875417678257}) ,
(1.0, 52.0, {'weight': 1.5298566582843918}) ,
(2.0, 59.0, {'weight': 1.2222170767316791}) ,
(3.0, 96.0, {'weight': 0.77235026806254947}) ,
(3.0, 98.0, {'weight': 0.75540026318653475}) ,
(3.0, 83.0, {'weight': 0.63745598060956865}) ,
(4.0, 8.0, {'weight': 1.1460983565815646}) ,
(5.0, 39.0, {'weight': 0.57882005244148982}) ,
(6.0, 27.0, {'weight': 0.77903808587705414}) ,
(6.0, 38.0, {'weight': 0.87763345274858739}) ,
(7.0, 83.0, {'weight': 1.0592473391743824}) ,
(7.0, 52.0, {'weight': 1.1650063193499598}) ,
(8.0, 18.0, {'weight': 0.62985157194068553}) ,
(8.0, 63.0, {'weight': 0.66061808561292024}) ,
(9.0, 57.0, {'weight': 0.73138423240527128}) ,
(9.0, 14.0, {'weight': 0.68690071596776681}) ,
(10.0, 43.0, {'weight': 1.0938913337235003}) ,
(11.0, 76.0, {'weight': 1.8066534138474315}) ,
(11.0, 22.0, {'weight': 1.5814274601380762}) ,
(12.0, 68.0, {'weight': 0.82964162447510292}) ,
(12.0, 28.0, {'weight': 0.56687613489965616}) ,
(13.0, 41.0, {'weight': 0.67883257822079479}) ,
(13.0, 70.0, {'weight': 0.69594526555853065}) ,
(13.0, 39.0, {'weight': 0.62690609201673064}) ,
(14.0, 42.0, {'weight': 0.51384098628821639}) ,
(15.0, 91.0, {'weight': 0.80363040334950342}) ,
(15.0, 63.0, {'weight': 0.74055429404201112}) ,
(16.0, 75.0, {'weight': 0.89225782872169068}) ,
(16.0, 36.0, {'weight': 0.97796463842832249}) ,
(16.0, 61.0, {'weight': 1.2426060084547763}) ,
(17.0, 24.0, {'weight': 0.48569989925661516}) ,
(17.0, 88.0, {'weight': 0.58411688395739225}) ,
(17.0, 42.0, {'weight': 0.48569989925661516}) ,
(18.0, 19.0, {'weight': 0.73750301595928458}) ,
(18.0, 87.0, {'weight': 0.62985157194068553}) ,
(19.0, 80.0, {'weight': 0.77740196142918039}) ,
(20.0, 53.0, {'weight': 1.5817584651620507}) ,
(21.0, 33.0, {'weight': 1.558483049272277}) ,
(21.0, 35.0, {'weight': 1.022218339608882}) ,
(22.0, 93.0, {'weight': 1.4628634684132413}) ,
(22.0, 101.0, {'weight': 7.494583622053641}) ,
(23.0, 97.0, {'weight': 0.86085201141197409}) ,
(23.0, 90.0, {'weight': 1.4629842172999594}) ,
(23.0, 65.0, {'weight': 0.94746570241498318}) ,
(24.0, 34.0, {'weight': 0.55323853417352553}) ,
(25.0, 104.0, {'weight': 4.9839694794161371}) ,
(26.0, 85.0, {'weight': 1.5024751933287497}) ,
(26.0, 46.0, {'weight': 1.2053565344116006}) ,
(27.0, 72.0, {'weight': 0.72860577250944303}) ,
(27.0, 92.0, {'weight': 0.74002007166874428}) ,
(28.0, 54.0, {'weight': 0.55323853417352553}) ,
(29.0, 50.0, {'weight': 0.81426784351619774}) ,
(30.0, 98.0, {'weight': 0.77235026806254947}) ,
(30.0, 78.0, {'weight': 0.79413937142096647}) ,
(30.0, 95.0, {'weight': 0.78901093530213129}) ,
(31.0, 68.0, {'weight': 0.98851671776185412}) ,
(32.0, 95.0, {'weight': 0.8579399666494596}) ,
(34.0, 54.0, {'weight': 0.55323853417352553}) ,
(34.0, 55.0, {'weight': 0.60906522381767525}) ,
(35.0, 62.0, {'weight': 0.66697239833732958}) ,
(36.0, 93.0, {'weight': 1.2932994772208264}) ,
(37.0, 80.0, {'weight': 0.85527462610640648}) ,
(37.0, 96.0, {'weight': 0.85527462610640648}) ,
(38.0, 46.0, {'weight': 0.95334944284759993}) ,
(39.0, 50.0, {'weight': 0.52028039541706872}) ,
(40.0, 69.0, {'weight': 1.7931323073700682}) ,
(42.0, 62.0, {'weight': 0.51384098628821639}) ,
(42.0, 81.0, {'weight': 0.5466147583189902}) ,
(43.0, 65.0, {'weight': 1.0581157274507453}) ,
(44.0, 108.0, {'weight': 3.0598509599260266}) ,
(44.0, 70.0, {'weight': 1.0805691635112824}) ,
(45.0, 56.0, {'weight': 1.3420236519319457}) ,
(45.0, 79.0, {'weight': 1.6201017824952586}) ,
(46.0, 53.0, {'weight': 1.070516213146298}) ,
(47.0, 78.0, {'weight': 1.2822937333699174}) ,
(47.0, 103.0, {'weight': 3.9053251231648707}) ,
(48.0, 97.0, {'weight': 0.86085201141197409}) ,
(48.0, 67.0, {'weight': 0.75656062694199944}) ,
(49.0, 94.0, {'weight': 1.6216528905308547}) ,
(49.0, 86.0, {'weight': 0.80157999082131093}) ,
(49.0, 62.0, {'weight': 0.7081136236724922}) ,
(51.0, 102.0, {'weight': 1.4704389417937378}) ,
(51.0, 71.0, {'weight': 0.83506431983724716}) ,
(54.0, 75.0, {'weight': 0.70074754481170742}) ,
(55.0, 58.0, {'weight': 0.78571631647476448}) ,
(56.0, 82.0, {'weight': 1.3387438494166808}) ,
(57.0, 84.0, {'weight': 1.558483049272277}) ,
(59.0, 64.0, {'weight': 1.0416266944398496}) ,
(60.0, 98.0, {'weight': 1.2534403896544031}) ,
(63.0, 73.0, {'weight': 0.83646303763566465}) ,
(64.0, 72.0, {'weight': 0.8620326535711742}) ,
(66.0, 77.0, {'weight': 0.79981721989351606}) ,
(67.0, 72.0, {'weight': 0.74002007166874428}) ,
(69.0, 83.0, {'weight': 1.5000235782351021}) ,
(70.0, 77.0, {'weight': 0.75999034076724692}) ,
(71.0, 88.0, {'weight': 0.66450874893016454}) ,
(74.0, 97.0, {'weight': 0.8743417572549379}) ,
(76.0, 107.0, {'weight': 2.0300278349030831}) ,
(77.0, 89.0, {'weight': 0.75999034076724692}) ,
(79.0, 106.0, {'weight': 4.5661761296968333}) ,
(82.0, 95.0, {'weight': 1.083633962514291}) ,
(84.0, 99.0, {'weight': 2.1024875417678257}) ,
(89.0, 92.0, {'weight': 0.75419548272456249}) ,
(100.0, 107.0, {'weight': 2.9259491743365307}) ,
(101.0, 109.0, {'weight': 7.6747981730730297}) ,
(102.0, 108.0, {'weight': 4.3128725576385092}) ,
(104.0, 105.0, {'weight': 7.5515191839631273})]
G2 = nx.Graph()
G2.add_nodes_from(nodes)
G2.add_edges_from(edges)
我想要的是“哪个顶点的label>；=0最接近label=-1的每个顶点”。对于这样的小图，使用nx.all_pairs_dijkstra_path_length()之类的方法，然后检查标签的brute-force方法可以很好地工作，但是不能扩展到非常大的图。有没有更有效的算法，特别是如果内置到networkx中，我可以使用吗？在
更新：
我用理查德的好建议和下面的评论来写这篇文章。我真正想要的是一系列的标签，我认为这使得事情不像Richard在networkx中提到的那样混乱。在一个数据集上，整个重新标记花费了45秒，用了一个小时的暴力！在
^{pr2}$Tags： 方法from路径networkxadd示例标签label
热门问题
- 是什么导致导入库时出现这种延迟？
- 是什么导致导入时提交大内存
- 是什么导致导入错误：“没有名为modules的模块”？
- 是什么导致局部变量引用错误？
- 是什么导致循环中的属性错误以及如何解决此问题
- 是什么导致我使用kivy的代码内存泄漏？
- 是什么导致我在python2.7中的代码中出现这种无意的无限循环？
- 是什么导致我的ATLAS工具在尝试构建时失败？
- 是什么导致我的Brainfuck transpiler的输出C文件中出现中止陷阱？
- 是什么导致我的Django文件上载代码内存峰值？
- 是什么导致我的json文件在添加kivy小部件后重置？
- 是什么导致我的python 404检查脚本崩溃/冻结？
- 是什么导致我的Python脚本中出现这种无效语法错误？
- 是什么导致我的while循环持续时间延长到12分钟？
- 是什么导致我的代码膨胀文本文件的大小？
- 是什么导致我的函数中出现“ValueError:cannot convert float NaN to integer”
- 是什么导致我的安跑的时间大大减少了？
- 是什么导致我的延迟触发，除了添加回调、启动反应器和连接端点之外什么都没做？
- 是什么导致我的条件[Python]中出现缩进错误
- 是什么导致我的游戏有非常低的fps
热门文章
- Python覆盖写入文件
- 怎样创建一个 Python 列表？
- Python3 List append()方法使用
- 派森语言
- Python List pop()方法
- Python Django Web典型模块开发实战
- Python input() 函数
- Python3 列表(list) clear()方法
- Python游戏编程入门
- 如何创建一个空的set?
- python如何定义(创建)一个字符串
- Python标准库 [The Python Standard Library by Ex
- Python网络数据爬取及分析从入门到精通（分析篇）
- Python3 for 循环语句
- Python List insert() 方法
- Python 字典(Dictionary) update()方法
- Python编程无师自通 专业程序员的养成
- Python3 List count()方法
- Python 网络爬虫实战 [Web Crawler With Python]
- Python Cookbook（第2版）中文版
这个不完整的伪代码应该从所有-1节点开始，然后“扇出”，依次计算到所有非1节点的距离。在
我不认为networkx中有这样的算法，但似乎有一个算法可以扩展最小成本路径，直到达到某个条件。然而，即使networkx不包含这样的功能，构建一个算法来实现这一点还是相当容易的。在
label==-1调用节点作为源节点。在label>=0的节点称为其目标节点。我们的目标是找到目标节点。在如果源节点数为S，则该算法在O（S（| E |+| V |））时间内运行（假设最短路径算法为Dijkstra）。在
（可能是我误解了您是希望-1最接近>；=0，还是>；=0最接近-1。如果有，请颠倒源/目标标签。）
如果我理解你的问题，那么你就有了一个旅行推销员的问题，这意味着没有比（在最坏的情况下）测试任何单一可能性更快的精确解决方案。在
相关问题 更多 >
编程相关推荐