diff options
| author | Dan Schult <dschult@colgate.edu> | 2015-10-03 00:28:14 -0400 |
|---|---|---|
| committer | Dan Schult <dschult@colgate.edu> | 2015-10-03 00:28:14 -0400 |
| commit | 0da6261b850f740e728eb1e54a5cec3d815f7a6f (patch) | |
| tree | 08b8af1d2b95ddcb9ecb0295f9a00150020e7916 | |
| parent | 76d040056bd935a95874058ed97b7d73eabca64a (diff) | |
| download | networkx-0da6261b850f740e728eb1e54a5cec3d815f7a6f.tar.gz | |
Change comments about fringe tuples in dijkstra
| -rw-r--r-- | networkx/algorithms/shortest_paths/weighted.py | 4 |
1 files changed, 3 insertions, 1 deletions
diff --git a/networkx/algorithms/shortest_paths/weighted.py b/networkx/algorithms/shortest_paths/weighted.py index bdae796e..dceb816f 100644 --- a/networkx/algorithms/shortest_paths/weighted.py +++ b/networkx/algorithms/shortest_paths/weighted.py @@ -346,8 +346,10 @@ def _dijkstra(G, source, get_weight, pred=None, paths=None, cutoff=None, pop = heappop dist = {} # dictionary of final distances seen = {source: 0} + # fringe is heapq with 3-tuples (distance,c,node) + # use the count c to avoid comparing nodes (may not be able to) c = count() - fringe = [] # use heapq with (distance,label) tuples + fringe = [] push(fringe, (0, next(c), source)) while fringe: (d, _, v) = pop(fringe) |