擅长:python、mysql、java
<p>这是因为<a href="https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm" rel="nofollow noreferrer">Bellman-Ford</a>算法从单个源返回所有节点的最短路径。但是,如果存在任何负循环,则没有从源顶点到所有节点的最短路径(例如,该循环中的每个节点都没有到的最短路径,因为您可以再次迭代循环并获得较低权重的路径)。在</p>
<p>您可以使用<a href="https://networkx.github.io/documentation/networkx-1.9/reference/generated/networkx.algorithms.cycles.simple_cycles.html" rel="nofollow noreferrer">nx.simple_cycles</a>。它所做的是返回一个简单循环的生成器,即图中没有重复节点的不同循环(当然除了第一个和最后一个)。
然后,您可以迭代生成的输出并检查负循环。在</p>
<p>我想应该是这样的:</p>
<pre><code>#import networx as nx
import networkx as nx
def find_path(digraph, start="USD"):
try:
path = nx.bellman_ford(digraph, start)
return path
except NetworkXUnbounded:
cycles = nx.simple_cycles(digraph)
for cycle in cycles:
print cycle # do whatever you prefer here of course
</code></pre>
<p>我还没试过。在</p>