如何使用Python NetworkX找到最长的路径? [英] How to find the longest path with Python NetworkX?
本文介绍了如何使用Python NetworkX找到最长的路径?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我有一个从S到T的有向图.
I have a directed graph from S to T.
我想找到路线(S,A,C,E,T)及其容量的总和(1 + 2 + 3 + 1 = 7),所以总和最大.
And I would like to find the route (S, A, C, E, T) and the sum of its capacities (1 + 2 + 3 + 1 = 7) so the sum is the largest.
我尝试使用networkx.algorithms.flow.ford_fulkerson,但我不知道如何获得从S到T的单向方向.
I tried networkx.algorithms.flow.ford_fulkerson, but I don't know how to get the one-way direction from S to T.
我的环境:
- Ubuntu 12.04
- Python 2.7.8
- NetworkX 1.9
- Matplotlib 1.4.0
example.py
example.py
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import matplotlib.pylab as p
import networkx as nx
if __name__ == '__main__':
DG = nx.DiGraph()
DG.add_edge('S', 'a', capacity=1)
DG.add_edge('a', 'b', capacity=1)
DG.add_edge('a', 'c', capacity=2)
DG.add_edge('b', 'd', capacity=1)
DG.add_edge('b', 'e', capacity=2)
DG.add_edge('c', 'e', capacity=3)
DG.add_edge('c', 'f', capacity=2)
DG.add_edge('d', 'T', capacity=1)
DG.add_edge('e', 'T', capacity=1)
DG.add_edge('f', 'T', capacity=1)
result = nx.algorithms.flow.ford_fulkerson(DG, 'S', 'T')
print(result.size(weight='capacity')) # 15.0, but I want 7.
pos = nx.spectral_layout(DG)
nx.draw(DG, pos)
nx.draw_networkx_labels(DG, pos)
nx.draw_networkx_edge_labels(DG, pos)
p.show()
# This shows a partly bidirectional graph, which is not what I want.
pos = nx.spectral_layout(result)
nx.draw(result, pos)
nx.draw_networkx_labels(result, pos)
nx.draw_networkx_edge_labels(result, pos)
p.show()
推荐答案
负权重适用于约翰逊.您的情况下,修改为:
The negative weights works for johnson. In your case, modified as:
DG = nx.DiGraph()
DG.add_edge('S', 'a', weight=-1)
DG.add_edge('a', 'b', weight=-1)
DG.add_edge('a', 'c', weight=-2)
DG.add_edge('b', 'd', weight=-1)
DG.add_edge('b', 'e', weight=-2)
DG.add_edge('c', 'e', weight=-3)
DG.add_edge('c', 'f', weight=-2)
DG.add_edge('d', 'T', weight=-1)
DG.add_edge('e', 'T', weight=-1)
DG.add_edge('f', 'T', weight=-1)
要找到最长的路径,请使用来获取从S到T的单向方向
To find longest path, get the one-way direction from S to T with
p2 = nx.johnson (DG, weight='weight')
print('johnson: {0}'.format(p2['S']['T']))
结果为:johnson: ['S', 'a', 'c', 'e', 'T']
我的环境:
- 软件版本
- Python 3.4.5 64位[MSC v.1600 64位(AMD64)]
- IPython 5.1.0操作系统Windows 10 10.0.14393
- networkx 1.11
这篇关于如何使用Python NetworkX找到最长的路径?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文