diff options
Diffstat (limited to '_modules/networkx/algorithms/shortest_paths/weighted.html')
| -rw-r--r-- | _modules/networkx/algorithms/shortest_paths/weighted.html | 66 |
1 files changed, 33 insertions, 33 deletions
diff --git a/_modules/networkx/algorithms/shortest_paths/weighted.html b/_modules/networkx/algorithms/shortest_paths/weighted.html index a2e23f33..61c9e9e5 100644 --- a/_modules/networkx/algorithms/shortest_paths/weighted.html +++ b/_modules/networkx/algorithms/shortest_paths/weighted.html @@ -502,7 +502,7 @@ <span class="k">def</span> <span class="nf">_weight_function</span><span class="p">(</span><span class="n">G</span><span class="p">,</span> <span class="n">weight</span><span class="p">):</span> - <span class="sd">"""Returns a function that returns the weight of an edge.</span> +<span class="w"> </span><span class="sd">"""Returns a function that returns the weight of an edge.</span> <span class="sd"> The returned function is specifically suitable for input to</span> <span class="sd"> functions :func:`_dijkstra` and :func:`_bellman_ford_relaxation`.</span> @@ -542,7 +542,7 @@ <div class="viewcode-block" id="dijkstra_path"><a class="viewcode-back" href="../../../../reference/algorithms/generated/networkx.algorithms.shortest_paths.weighted.dijkstra_path.html#networkx.algorithms.shortest_paths.weighted.dijkstra_path">[docs]</a><span class="k">def</span> <span class="nf">dijkstra_path</span><span class="p">(</span><span class="n">G</span><span class="p">,</span> <span class="n">source</span><span class="p">,</span> <span class="n">target</span><span class="p">,</span> <span class="n">weight</span><span class="o">=</span><span class="s2">"weight"</span><span class="p">):</span> - <span class="sd">"""Returns the shortest weighted path from source to target in G.</span> +<span class="w"> </span><span class="sd">"""Returns the shortest weighted path from source to target in G.</span> <span class="sd"> Uses Dijkstra's Method to compute the shortest weighted path</span> <span class="sd"> between two nodes in a graph.</span> @@ -623,7 +623,7 @@ <div class="viewcode-block" id="dijkstra_path_length"><a class="viewcode-back" href="../../../../reference/algorithms/generated/networkx.algorithms.shortest_paths.weighted.dijkstra_path_length.html#networkx.algorithms.shortest_paths.weighted.dijkstra_path_length">[docs]</a><span class="k">def</span> <span class="nf">dijkstra_path_length</span><span class="p">(</span><span class="n">G</span><span class="p">,</span> <span class="n">source</span><span class="p">,</span> <span class="n">target</span><span class="p">,</span> <span class="n">weight</span><span class="o">=</span><span class="s2">"weight"</span><span class="p">):</span> - <span class="sd">"""Returns the shortest weighted path length in G from source to target.</span> +<span class="w"> </span><span class="sd">"""Returns the shortest weighted path length in G from source to target.</span> <span class="sd"> Uses Dijkstra's Method to compute the shortest weighted path length</span> <span class="sd"> between two nodes in a graph.</span> @@ -702,7 +702,7 @@ <div class="viewcode-block" id="single_source_dijkstra_path"><a class="viewcode-back" href="../../../../reference/algorithms/generated/networkx.algorithms.shortest_paths.weighted.single_source_dijkstra_path.html#networkx.algorithms.shortest_paths.weighted.single_source_dijkstra_path">[docs]</a><span class="k">def</span> <span class="nf">single_source_dijkstra_path</span><span class="p">(</span><span class="n">G</span><span class="p">,</span> <span class="n">source</span><span class="p">,</span> <span class="n">cutoff</span><span class="o">=</span><span class="kc">None</span><span class="p">,</span> <span class="n">weight</span><span class="o">=</span><span class="s2">"weight"</span><span class="p">):</span> - <span class="sd">"""Find shortest weighted paths in G from a source node.</span> +<span class="w"> </span><span class="sd">"""Find shortest weighted paths in G from a source node.</span> <span class="sd"> Compute shortest path between source and all other reachable</span> <span class="sd"> nodes for a weighted graph.</span> @@ -766,7 +766,7 @@ <div class="viewcode-block" id="single_source_dijkstra_path_length"><a class="viewcode-back" href="../../../../reference/algorithms/generated/networkx.algorithms.shortest_paths.weighted.single_source_dijkstra_path_length.html#networkx.algorithms.shortest_paths.weighted.single_source_dijkstra_path_length">[docs]</a><span class="k">def</span> <span class="nf">single_source_dijkstra_path_length</span><span class="p">(</span><span class="n">G</span><span class="p">,</span> <span class="n">source</span><span class="p">,</span> <span class="n">cutoff</span><span class="o">=</span><span class="kc">None</span><span class="p">,</span> <span class="n">weight</span><span class="o">=</span><span class="s2">"weight"</span><span class="p">):</span> - <span class="sd">"""Find shortest weighted path lengths in G from a source node.</span> +<span class="w"> </span><span class="sd">"""Find shortest weighted path lengths in G from a source node.</span> <span class="sd"> Compute the shortest path length between source and all other</span> <span class="sd"> reachable nodes for a weighted graph.</span> @@ -837,7 +837,7 @@ <div class="viewcode-block" id="single_source_dijkstra"><a class="viewcode-back" href="../../../../reference/algorithms/generated/networkx.algorithms.shortest_paths.weighted.single_source_dijkstra.html#networkx.algorithms.shortest_paths.weighted.single_source_dijkstra">[docs]</a><span class="k">def</span> <span class="nf">single_source_dijkstra</span><span class="p">(</span><span class="n">G</span><span class="p">,</span> <span class="n">source</span><span class="p">,</span> <span class="n">target</span><span class="o">=</span><span class="kc">None</span><span class="p">,</span> <span class="n">cutoff</span><span class="o">=</span><span class="kc">None</span><span class="p">,</span> <span class="n">weight</span><span class="o">=</span><span class="s2">"weight"</span><span class="p">):</span> - <span class="sd">"""Find shortest weighted paths and lengths from a source node.</span> +<span class="w"> </span><span class="sd">"""Find shortest weighted paths and lengths from a source node.</span> <span class="sd"> Compute the shortest path length between source and all other</span> <span class="sd"> reachable nodes for a weighted graph.</span> @@ -938,7 +938,7 @@ <div class="viewcode-block" id="multi_source_dijkstra_path"><a class="viewcode-back" href="../../../../reference/algorithms/generated/networkx.algorithms.shortest_paths.weighted.multi_source_dijkstra_path.html#networkx.algorithms.shortest_paths.weighted.multi_source_dijkstra_path">[docs]</a><span class="k">def</span> <span class="nf">multi_source_dijkstra_path</span><span class="p">(</span><span class="n">G</span><span class="p">,</span> <span class="n">sources</span><span class="p">,</span> <span class="n">cutoff</span><span class="o">=</span><span class="kc">None</span><span class="p">,</span> <span class="n">weight</span><span class="o">=</span><span class="s2">"weight"</span><span class="p">):</span> - <span class="sd">"""Find shortest weighted paths in G from a given set of source</span> +<span class="w"> </span><span class="sd">"""Find shortest weighted paths in G from a given set of source</span> <span class="sd"> nodes.</span> <span class="sd"> Compute shortest path between any of the source nodes and all other</span> @@ -1011,7 +1011,7 @@ <div class="viewcode-block" id="multi_source_dijkstra_path_length"><a class="viewcode-back" href="../../../../reference/algorithms/generated/networkx.algorithms.shortest_paths.weighted.multi_source_dijkstra_path_length.html#networkx.algorithms.shortest_paths.weighted.multi_source_dijkstra_path_length">[docs]</a><span class="k">def</span> <span class="nf">multi_source_dijkstra_path_length</span><span class="p">(</span><span class="n">G</span><span class="p">,</span> <span class="n">sources</span><span class="p">,</span> <span class="n">cutoff</span><span class="o">=</span><span class="kc">None</span><span class="p">,</span> <span class="n">weight</span><span class="o">=</span><span class="s2">"weight"</span><span class="p">):</span> - <span class="sd">"""Find shortest weighted path lengths in G from a given set of</span> +<span class="w"> </span><span class="sd">"""Find shortest weighted path lengths in G from a given set of</span> <span class="sd"> source nodes.</span> <span class="sd"> Compute the shortest path length between any of the source nodes and</span> @@ -1092,7 +1092,7 @@ <div class="viewcode-block" id="multi_source_dijkstra"><a class="viewcode-back" href="../../../../reference/algorithms/generated/networkx.algorithms.shortest_paths.weighted.multi_source_dijkstra.html#networkx.algorithms.shortest_paths.weighted.multi_source_dijkstra">[docs]</a><span class="k">def</span> <span class="nf">multi_source_dijkstra</span><span class="p">(</span><span class="n">G</span><span class="p">,</span> <span class="n">sources</span><span class="p">,</span> <span class="n">target</span><span class="o">=</span><span class="kc">None</span><span class="p">,</span> <span class="n">cutoff</span><span class="o">=</span><span class="kc">None</span><span class="p">,</span> <span class="n">weight</span><span class="o">=</span><span class="s2">"weight"</span><span class="p">):</span> - <span class="sd">"""Find shortest weighted paths and lengths from a given set of</span> +<span class="w"> </span><span class="sd">"""Find shortest weighted paths and lengths from a given set of</span> <span class="sd"> source nodes.</span> <span class="sd"> Uses Dijkstra's algorithm to compute the shortest paths and lengths</span> @@ -1211,7 +1211,7 @@ <span class="k">def</span> <span class="nf">_dijkstra</span><span class="p">(</span><span class="n">G</span><span class="p">,</span> <span class="n">source</span><span class="p">,</span> <span class="n">weight</span><span class="p">,</span> <span class="n">pred</span><span class="o">=</span><span class="kc">None</span><span class="p">,</span> <span class="n">paths</span><span class="o">=</span><span class="kc">None</span><span class="p">,</span> <span class="n">cutoff</span><span class="o">=</span><span class="kc">None</span><span class="p">,</span> <span class="n">target</span><span class="o">=</span><span class="kc">None</span><span class="p">):</span> - <span class="sd">"""Uses Dijkstra's algorithm to find shortest weighted paths from a</span> +<span class="w"> </span><span class="sd">"""Uses Dijkstra's algorithm to find shortest weighted paths from a</span> <span class="sd"> single source.</span> <span class="sd"> This is a convenience function for :func:`_dijkstra_multisource`</span> @@ -1227,7 +1227,7 @@ <span class="k">def</span> <span class="nf">_dijkstra_multisource</span><span class="p">(</span> <span class="n">G</span><span class="p">,</span> <span class="n">sources</span><span class="p">,</span> <span class="n">weight</span><span class="p">,</span> <span class="n">pred</span><span class="o">=</span><span class="kc">None</span><span class="p">,</span> <span class="n">paths</span><span class="o">=</span><span class="kc">None</span><span class="p">,</span> <span class="n">cutoff</span><span class="o">=</span><span class="kc">None</span><span class="p">,</span> <span class="n">target</span><span class="o">=</span><span class="kc">None</span> <span class="p">):</span> - <span class="sd">"""Uses Dijkstra's algorithm to find shortest weighted paths</span> +<span class="w"> </span><span class="sd">"""Uses Dijkstra's algorithm to find shortest weighted paths</span> <span class="sd"> Parameters</span> <span class="sd"> ----------</span> @@ -1328,7 +1328,7 @@ <div class="viewcode-block" id="dijkstra_predecessor_and_distance"><a class="viewcode-back" href="../../../../reference/algorithms/generated/networkx.algorithms.shortest_paths.weighted.dijkstra_predecessor_and_distance.html#networkx.algorithms.shortest_paths.weighted.dijkstra_predecessor_and_distance">[docs]</a><span class="k">def</span> <span class="nf">dijkstra_predecessor_and_distance</span><span class="p">(</span><span class="n">G</span><span class="p">,</span> <span class="n">source</span><span class="p">,</span> <span class="n">cutoff</span><span class="o">=</span><span class="kc">None</span><span class="p">,</span> <span class="n">weight</span><span class="o">=</span><span class="s2">"weight"</span><span class="p">):</span> - <span class="sd">"""Compute weighted shortest path length and predecessors.</span> +<span class="w"> </span><span class="sd">"""Compute weighted shortest path length and predecessors.</span> <span class="sd"> Uses Dijkstra's Method to obtain the shortest weighted paths</span> <span class="sd"> and return dictionaries of predecessors for each node and</span> @@ -1400,7 +1400,7 @@ <div class="viewcode-block" id="all_pairs_dijkstra"><a class="viewcode-back" href="../../../../reference/algorithms/generated/networkx.algorithms.shortest_paths.weighted.all_pairs_dijkstra.html#networkx.algorithms.shortest_paths.weighted.all_pairs_dijkstra">[docs]</a><span class="k">def</span> <span class="nf">all_pairs_dijkstra</span><span class="p">(</span><span class="n">G</span><span class="p">,</span> <span class="n">cutoff</span><span class="o">=</span><span class="kc">None</span><span class="p">,</span> <span class="n">weight</span><span class="o">=</span><span class="s2">"weight"</span><span class="p">):</span> - <span class="sd">"""Find shortest weighted paths and lengths between all nodes.</span> +<span class="w"> </span><span class="sd">"""Find shortest weighted paths and lengths between all nodes.</span> <span class="sd"> Parameters</span> <span class="sd"> ----------</span> @@ -1468,7 +1468,7 @@ <div class="viewcode-block" id="all_pairs_dijkstra_path_length"><a class="viewcode-back" href="../../../../reference/algorithms/generated/networkx.algorithms.shortest_paths.weighted.all_pairs_dijkstra_path_length.html#networkx.algorithms.shortest_paths.weighted.all_pairs_dijkstra_path_length">[docs]</a><span class="k">def</span> <span class="nf">all_pairs_dijkstra_path_length</span><span class="p">(</span><span class="n">G</span><span class="p">,</span> <span class="n">cutoff</span><span class="o">=</span><span class="kc">None</span><span class="p">,</span> <span class="n">weight</span><span class="o">=</span><span class="s2">"weight"</span><span class="p">):</span> - <span class="sd">"""Compute shortest path lengths between all nodes in a weighted graph.</span> +<span class="w"> </span><span class="sd">"""Compute shortest path lengths between all nodes in a weighted graph.</span> <span class="sd"> Parameters</span> <span class="sd"> ----------</span> @@ -1526,7 +1526,7 @@ <div class="viewcode-block" id="all_pairs_dijkstra_path"><a class="viewcode-back" href="../../../../reference/algorithms/generated/networkx.algorithms.shortest_paths.weighted.all_pairs_dijkstra_path.html#networkx.algorithms.shortest_paths.weighted.all_pairs_dijkstra_path">[docs]</a><span class="k">def</span> <span class="nf">all_pairs_dijkstra_path</span><span class="p">(</span><span class="n">G</span><span class="p">,</span> <span class="n">cutoff</span><span class="o">=</span><span class="kc">None</span><span class="p">,</span> <span class="n">weight</span><span class="o">=</span><span class="s2">"weight"</span><span class="p">):</span> - <span class="sd">"""Compute shortest paths between all nodes in a weighted graph.</span> +<span class="w"> </span><span class="sd">"""Compute shortest paths between all nodes in a weighted graph.</span> <span class="sd"> Parameters</span> <span class="sd"> ----------</span> @@ -1580,7 +1580,7 @@ <div class="viewcode-block" id="bellman_ford_predecessor_and_distance"><a class="viewcode-back" href="../../../../reference/algorithms/generated/networkx.algorithms.shortest_paths.weighted.bellman_ford_predecessor_and_distance.html#networkx.algorithms.shortest_paths.weighted.bellman_ford_predecessor_and_distance">[docs]</a><span class="k">def</span> <span class="nf">bellman_ford_predecessor_and_distance</span><span class="p">(</span> <span class="n">G</span><span class="p">,</span> <span class="n">source</span><span class="p">,</span> <span class="n">target</span><span class="o">=</span><span class="kc">None</span><span class="p">,</span> <span class="n">weight</span><span class="o">=</span><span class="s2">"weight"</span><span class="p">,</span> <span class="n">heuristic</span><span class="o">=</span><span class="kc">False</span> <span class="p">):</span> - <span class="sd">"""Compute shortest path lengths and predecessors on shortest paths</span> +<span class="w"> </span><span class="sd">"""Compute shortest path lengths and predecessors on shortest paths</span> <span class="sd"> in weighted graphs.</span> <span class="sd"> The algorithm has a running time of $O(mn)$ where $n$ is the number of</span> @@ -1709,7 +1709,7 @@ <span class="n">target</span><span class="o">=</span><span class="kc">None</span><span class="p">,</span> <span class="n">heuristic</span><span class="o">=</span><span class="kc">True</span><span class="p">,</span> <span class="p">):</span> - <span class="sd">"""Calls relaxation loop for Bellman–Ford algorithm and builds paths</span> +<span class="w"> </span><span class="sd">"""Calls relaxation loop for Bellman–Ford algorithm and builds paths</span> <span class="sd"> This is an implementation of the SPFA variant.</span> <span class="sd"> See https://en.wikipedia.org/wiki/Shortest_Path_Faster_Algorithm</span> @@ -1801,7 +1801,7 @@ <span class="n">dist</span><span class="o">=</span><span class="kc">None</span><span class="p">,</span> <span class="n">heuristic</span><span class="o">=</span><span class="kc">True</span><span class="p">,</span> <span class="p">):</span> - <span class="sd">"""Inner Relaxation loop for Bellman–Ford algorithm.</span> +<span class="w"> </span><span class="sd">"""Inner Relaxation loop for Bellman–Ford algorithm.</span> <span class="sd"> This is an implementation of the SPFA variant.</span> <span class="sd"> See https://en.wikipedia.org/wiki/Shortest_Path_Faster_Algorithm</span> @@ -1918,7 +1918,7 @@ <div class="viewcode-block" id="bellman_ford_path"><a class="viewcode-back" href="../../../../reference/algorithms/generated/networkx.algorithms.shortest_paths.weighted.bellman_ford_path.html#networkx.algorithms.shortest_paths.weighted.bellman_ford_path">[docs]</a><span class="k">def</span> <span class="nf">bellman_ford_path</span><span class="p">(</span><span class="n">G</span><span class="p">,</span> <span class="n">source</span><span class="p">,</span> <span class="n">target</span><span class="p">,</span> <span class="n">weight</span><span class="o">=</span><span class="s2">"weight"</span><span class="p">):</span> - <span class="sd">"""Returns the shortest path from source to target in a weighted graph G.</span> +<span class="w"> </span><span class="sd">"""Returns the shortest path from source to target in a weighted graph G.</span> <span class="sd"> Parameters</span> <span class="sd"> ----------</span> @@ -1976,7 +1976,7 @@ <div class="viewcode-block" id="bellman_ford_path_length"><a class="viewcode-back" href="../../../../reference/algorithms/generated/networkx.algorithms.shortest_paths.weighted.bellman_ford_path_length.html#networkx.algorithms.shortest_paths.weighted.bellman_ford_path_length">[docs]</a><span class="k">def</span> <span class="nf">bellman_ford_path_length</span><span class="p">(</span><span class="n">G</span><span class="p">,</span> <span class="n">source</span><span class="p">,</span> <span class="n">target</span><span class="p">,</span> <span class="n">weight</span><span class="o">=</span><span class="s2">"weight"</span><span class="p">):</span> - <span class="sd">"""Returns the shortest path length from source to target</span> +<span class="w"> </span><span class="sd">"""Returns the shortest path length from source to target</span> <span class="sd"> in a weighted graph.</span> <span class="sd"> Parameters</span> @@ -2046,7 +2046,7 @@ <div class="viewcode-block" id="single_source_bellman_ford_path"><a class="viewcode-back" href="../../../../reference/algorithms/generated/networkx.algorithms.shortest_paths.weighted.single_source_bellman_ford_path.html#networkx.algorithms.shortest_paths.weighted.single_source_bellman_ford_path">[docs]</a><span class="k">def</span> <span class="nf">single_source_bellman_ford_path</span><span class="p">(</span><span class="n">G</span><span class="p">,</span> <span class="n">source</span><span class="p">,</span> <span class="n">weight</span><span class="o">=</span><span class="s2">"weight"</span><span class="p">):</span> - <span class="sd">"""Compute shortest path between source and all other reachable</span> +<span class="w"> </span><span class="sd">"""Compute shortest path between source and all other reachable</span> <span class="sd"> nodes for a weighted graph.</span> <span class="sd"> Parameters</span> @@ -2101,7 +2101,7 @@ <div class="viewcode-block" id="single_source_bellman_ford_path_length"><a class="viewcode-back" href="../../../../reference/algorithms/generated/networkx.algorithms.shortest_paths.weighted.single_source_bellman_ford_path_length.html#networkx.algorithms.shortest_paths.weighted.single_source_bellman_ford_path_length">[docs]</a><span class="k">def</span> <span class="nf">single_source_bellman_ford_path_length</span><span class="p">(</span><span class="n">G</span><span class="p">,</span> <span class="n">source</span><span class="p">,</span> <span class="n">weight</span><span class="o">=</span><span class="s2">"weight"</span><span class="p">):</span> - <span class="sd">"""Compute the shortest path length between source and all other</span> +<span class="w"> </span><span class="sd">"""Compute the shortest path length between source and all other</span> <span class="sd"> reachable nodes for a weighted graph.</span> <span class="sd"> Parameters</span> @@ -2163,7 +2163,7 @@ <div class="viewcode-block" id="single_source_bellman_ford"><a class="viewcode-back" href="../../../../reference/algorithms/generated/networkx.algorithms.shortest_paths.weighted.single_source_bellman_ford.html#networkx.algorithms.shortest_paths.weighted.single_source_bellman_ford">[docs]</a><span class="k">def</span> <span class="nf">single_source_bellman_ford</span><span class="p">(</span><span class="n">G</span><span class="p">,</span> <span class="n">source</span><span class="p">,</span> <span class="n">target</span><span class="o">=</span><span class="kc">None</span><span class="p">,</span> <span class="n">weight</span><span class="o">=</span><span class="s2">"weight"</span><span class="p">):</span> - <span class="sd">"""Compute shortest paths and lengths in a weighted graph G.</span> +<span class="w"> </span><span class="sd">"""Compute shortest paths and lengths in a weighted graph G.</span> <span class="sd"> Uses Bellman-Ford algorithm for shortest paths.</span> @@ -2256,7 +2256,7 @@ <div class="viewcode-block" id="all_pairs_bellman_ford_path_length"><a class="viewcode-back" href="../../../../reference/algorithms/generated/networkx.algorithms.shortest_paths.weighted.all_pairs_bellman_ford_path_length.html#networkx.algorithms.shortest_paths.weighted.all_pairs_bellman_ford_path_length">[docs]</a><span class="k">def</span> <span class="nf">all_pairs_bellman_ford_path_length</span><span class="p">(</span><span class="n">G</span><span class="p">,</span> <span class="n">weight</span><span class="o">=</span><span class="s2">"weight"</span><span class="p">):</span> - <span class="sd">"""Compute shortest path lengths between all nodes in a weighted graph.</span> +<span class="w"> </span><span class="sd">"""Compute shortest path lengths between all nodes in a weighted graph.</span> <span class="sd"> Parameters</span> <span class="sd"> ----------</span> @@ -2310,7 +2310,7 @@ <div class="viewcode-block" id="all_pairs_bellman_ford_path"><a class="viewcode-back" href="../../../../reference/algorithms/generated/networkx.algorithms.shortest_paths.weighted.all_pairs_bellman_ford_path.html#networkx.algorithms.shortest_paths.weighted.all_pairs_bellman_ford_path">[docs]</a><span class="k">def</span> <span class="nf">all_pairs_bellman_ford_path</span><span class="p">(</span><span class="n">G</span><span class="p">,</span> <span class="n">weight</span><span class="o">=</span><span class="s2">"weight"</span><span class="p">):</span> - <span class="sd">"""Compute shortest paths between all nodes in a weighted graph.</span> +<span class="w"> </span><span class="sd">"""Compute shortest paths between all nodes in a weighted graph.</span> <span class="sd"> Parameters</span> <span class="sd"> ----------</span> @@ -2358,7 +2358,7 @@ <div class="viewcode-block" id="goldberg_radzik"><a class="viewcode-back" href="../../../../reference/algorithms/generated/networkx.algorithms.shortest_paths.weighted.goldberg_radzik.html#networkx.algorithms.shortest_paths.weighted.goldberg_radzik">[docs]</a><span class="k">def</span> <span class="nf">goldberg_radzik</span><span class="p">(</span><span class="n">G</span><span class="p">,</span> <span class="n">source</span><span class="p">,</span> <span class="n">weight</span><span class="o">=</span><span class="s2">"weight"</span><span class="p">):</span> - <span class="sd">"""Compute shortest path lengths and predecessors on shortest paths</span> +<span class="w"> </span><span class="sd">"""Compute shortest path lengths and predecessors on shortest paths</span> <span class="sd"> in weighted graphs.</span> <span class="sd"> The algorithm has a running time of $O(mn)$ where $n$ is the number of</span> @@ -2450,7 +2450,7 @@ <span class="n">pred</span> <span class="o">=</span> <span class="p">{</span><span class="n">source</span><span class="p">:</span> <span class="kc">None</span><span class="p">}</span> <span class="k">def</span> <span class="nf">topo_sort</span><span class="p">(</span><span class="n">relabeled</span><span class="p">):</span> - <span class="sd">"""Topologically sort nodes relabeled in the previous round and detect</span> +<span class="w"> </span><span class="sd">"""Topologically sort nodes relabeled in the previous round and detect</span> <span class="sd"> negative cycles.</span> <span class="sd"> """</span> <span class="c1"># List of nodes to scan in this round. Denoted by A in Goldberg and</span> @@ -2506,7 +2506,7 @@ <span class="k">return</span> <span class="n">to_scan</span> <span class="k">def</span> <span class="nf">relax</span><span class="p">(</span><span class="n">to_scan</span><span class="p">):</span> - <span class="sd">"""Relax out-edges of relabeled nodes."""</span> +<span class="w"> </span><span class="sd">"""Relax out-edges of relabeled nodes."""</span> <span class="n">relabeled</span> <span class="o">=</span> <span class="nb">set</span><span class="p">()</span> <span class="c1"># Scan nodes in to_scan in topological order and relax incident</span> <span class="c1"># out-edges. Add the relabled nodes to labeled.</span> @@ -2533,7 +2533,7 @@ <div class="viewcode-block" id="negative_edge_cycle"><a class="viewcode-back" href="../../../../reference/algorithms/generated/networkx.algorithms.shortest_paths.weighted.negative_edge_cycle.html#networkx.algorithms.shortest_paths.weighted.negative_edge_cycle">[docs]</a><span class="k">def</span> <span class="nf">negative_edge_cycle</span><span class="p">(</span><span class="n">G</span><span class="p">,</span> <span class="n">weight</span><span class="o">=</span><span class="s2">"weight"</span><span class="p">,</span> <span class="n">heuristic</span><span class="o">=</span><span class="kc">True</span><span class="p">):</span> - <span class="sd">"""Returns True if there exists a negative edge cycle anywhere in G.</span> +<span class="w"> </span><span class="sd">"""Returns True if there exists a negative edge cycle anywhere in G.</span> <span class="sd"> Parameters</span> <span class="sd"> ----------</span> @@ -2600,7 +2600,7 @@ <div class="viewcode-block" id="find_negative_cycle"><a class="viewcode-back" href="../../../../reference/algorithms/generated/networkx.algorithms.shortest_paths.weighted.find_negative_cycle.html#networkx.algorithms.shortest_paths.weighted.find_negative_cycle">[docs]</a><span class="k">def</span> <span class="nf">find_negative_cycle</span><span class="p">(</span><span class="n">G</span><span class="p">,</span> <span class="n">source</span><span class="p">,</span> <span class="n">weight</span><span class="o">=</span><span class="s2">"weight"</span><span class="p">):</span> - <span class="sd">"""Returns a cycle with negative total weight if it exists.</span> +<span class="w"> </span><span class="sd">"""Returns a cycle with negative total weight if it exists.</span> <span class="sd"> Bellman-Ford is used to find shortest_paths. That algorithm</span> <span class="sd"> stops if there exists a negative cycle. This algorithm</span> @@ -2692,7 +2692,7 @@ <div class="viewcode-block" id="bidirectional_dijkstra"><a class="viewcode-back" href="../../../../reference/algorithms/generated/networkx.algorithms.shortest_paths.weighted.bidirectional_dijkstra.html#networkx.algorithms.shortest_paths.weighted.bidirectional_dijkstra">[docs]</a><span class="k">def</span> <span class="nf">bidirectional_dijkstra</span><span class="p">(</span><span class="n">G</span><span class="p">,</span> <span class="n">source</span><span class="p">,</span> <span class="n">target</span><span class="p">,</span> <span class="n">weight</span><span class="o">=</span><span class="s2">"weight"</span><span class="p">):</span> - <span class="sa">r</span><span class="sd">"""Dijkstra's algorithm for shortest paths using bidirectional search.</span> +<span class="w"> </span><span class="sa">r</span><span class="sd">"""Dijkstra's algorithm for shortest paths using bidirectional search.</span> <span class="sd"> Parameters</span> <span class="sd"> ----------</span> @@ -2839,7 +2839,7 @@ <div class="viewcode-block" id="johnson"><a class="viewcode-back" href="../../../../reference/algorithms/generated/networkx.algorithms.shortest_paths.weighted.johnson.html#networkx.algorithms.shortest_paths.weighted.johnson">[docs]</a><span class="k">def</span> <span class="nf">johnson</span><span class="p">(</span><span class="n">G</span><span class="p">,</span> <span class="n">weight</span><span class="o">=</span><span class="s2">"weight"</span><span class="p">):</span> - <span class="sa">r</span><span class="sd">"""Uses Johnson's Algorithm to compute shortest paths.</span> +<span class="w"> </span><span class="sa">r</span><span class="sd">"""Uses Johnson's Algorithm to compute shortest paths.</span> <span class="sd"> Johnson's Algorithm finds a shortest path between each pair of</span> <span class="sd"> nodes in a weighted graph even if negative weights are present.</span> @@ -2977,7 +2977,7 @@ <p class="copyright"> - © Copyright 2004-2022, NetworkX Developers.<br> + © Copyright 2004-2023, NetworkX Developers.<br> </p> |