Ford–Fulkerson algorithm (original) (raw)
L'algorisme de Ford-Fulkerson és un algorisme que calcula el flux màxim en una xarxa de flux. L'algorisme proposa buscar camins en els quals es pugui augmentar el flux, fins que s'aconsegueixi el flux màxim. La idea és trobar una ruta de penetració amb un flux positiu net que uneixi els nodes origen i destinació. El seu nom ve donat pels seus creadors, L. R. Ford, Jr. i D. R. Fulkerson.
| Property | Value |
|---|---|
| dbo:abstract | L'algorisme de Ford-Fulkerson és un algorisme que calcula el flux màxim en una xarxa de flux. L'algorisme proposa buscar camins en els quals es pugui augmentar el flux, fins que s'aconsegueixi el flux màxim. La idea és trobar una ruta de penetració amb un flux positiu net que uneixi els nodes origen i destinació. El seu nom ve donat pels seus creadors, L. R. Ford, Jr. i D. R. Fulkerson. (ca) Fordův-Fulkersonův algoritmus (pojmenovaný podle a D. R. Fulkersona) počítá maximální tok v síti. Název Ford-Fulkerson je také často používán pro Edmondsův-Karpův algoritmus, který je specializací Fordova-Fulkersonova algoritmu. Myšlenka algoritmu je velmi jednoduchá: Dokud existuje cesta ze zdroje (výchozí bod) do spotřebiče (koncový bod), taková, že je možnost ještě zvětšit její tok, neboli, že každá hrana na této cestě muže ještě „propustit“ vyšší tok (není ve stavu saturace), tak na všech hranách této cesty zvýšíme tok o největší hodnotu, o kterou lze zvětšit tok ve všech hranách cesty. Poté celý postup opakujeme. Cesta s volnou kapacitou se nazývá . (cs) Der Algorithmus von Ford und Fulkerson ist ein Algorithmus aus dem mathematischen Teilgebiet der Graphentheorie zur Bestimmung eines maximalen Flusses in einem Flussnetzwerk mit rationalen Kapazitäten. Er wurde nach seinen Erfindern L.R. Ford Jr. und D.R. Fulkerson benannt.Die Anzahl der benötigten Operationen hängt vom Wert des maximalen Flusses ab und ist im Allgemeinen nicht polynomiell beschränkt.Weiterentwicklungen führten zum Algorithmus von Edmonds und Karp und dem Algorithmus von Dinic. (de) El algoritmo de Ford-Fulkerson propone buscar caminos en los que se pueda aumentar el flujo, hasta que se alcance el flujo máximo. Es aplicable a los Flujos maximales. La idea es encontrar una ruta de penetración con un flujo positivo neto que una los nodos origen y destino. Su nombre viene dado por sus creadores, y D. R. Fulkerson. (es) The Ford–Fulkerson method or Ford–Fulkerson algorithm (FFA) is a greedy algorithm that computes the maximum flow in a flow network. It is sometimes called a "method" instead of an "algorithm" as the approach to finding augmenting paths in a residual graph is not fully specified or it is specified in several implementations with different running times. It was published in 1956 by L. R. Ford Jr. and D. R. Fulkerson. The name "Ford–Fulkerson" is often also used for the Edmonds–Karp algorithm, which is a fully defined implementation of the Ford–Fulkerson method. The idea behind the algorithm is as follows: as long as there is a path from the source (start node) to the sink (end node), with available capacity on all edges in the path, we send flow along one of the paths. Then we find another path, and so on. A path with available capacity is called an augmenting path. (en) En informatique, l'algorithme de Ford-Fulkerson est un algorithme pour le problème de flot maximum, un problème d'optimisation classique dans le domaine de la recherche opérationnelle. Il est dû à Lester Randolph Ford junior et D. R. Fulkerson et c'est une variante de l'algorithme de Busacker et Gowen. (fr) In informatica, l'algoritmo di Ford-Fulkerson permette di trovare il flusso massimo che attraversa un grafo da un punto ad un altro di questo. Il nome deriva dai suoi due ideatori, Lester Randolph Ford e . (it) フォード・ファルカーソンのアルゴリズム（英: Ford-Fulkerson algorithm）とは、フローネットワークにおける最大フローを求めるアルゴリズムである。 と にちなんで命名されたもので、1956年に発表された。フォード・ファルカーソンのアルゴリズムの特殊版であるエドモンズ-カープアルゴリズムも「フォード・ファルカーソン」と呼ばれることがある。 このアルゴリズムの背景にある考え方は非常に単純である。始点から終点への経路があって、経路上の各辺に容量の空きがあるとき、その経路を使って流れを作ることができる。これを経路が見つかるたびにくりかえす。容量に空きがある経路を「増加道; augmenting path」と呼ぶ。 (ja) Metoda Forda-Fulkersona jest stosowana do znajdowania maksymalnego przepływu w sieci przepływowej. Stanowi podstawę wielu algorytmów, między innymi algorytmu Edmondsa-Karpa czy algorytmu Dynica Zasadę jej działania można streścić w następujący sposób: Należy zwiększać przepływ wzdłuż dowolnej ścieżki ze źródła do ujścia, dopóki jest to możliwe. (pl) Алгоритм Форда — Фалкерсона решает задачу нахождения максимального потока в транспортной сети. Идея алгоритма заключается в следующем. Изначально величине потока присваивается значение 0: для всех . Затем величина потока итеративно увеличивается посредством поиска увеличивающего пути (путь от источника к стоку , вдоль которого можно послать больший поток). Процесс повторяется, пока можно найти увеличивающий путь. (ru) O algoritmo de Ford-Fulkerson (assim designado em honra de e Delbert Ray Fulkerson) é um algoritmo utilizado para resolver problemas de fluxo em rede (network flow). O algoritmo é empregado quando se deseja encontrar um fluxo de valor máximo que faça o melhor uso possível das capacidades disponíveis na rede em questão. A história do algoritmo está relacionada à análise da rede ferroviária da União Soviética, tanto por russos quanto por americanos, nas décadas de 1930, 1940 e 1950. O problema resolvido pelo algoritmo é o de encontrar um fluxo máximo em uma rede. Uma rede pode ser uma rede elétrica, um sistema de transporte de fluidos ou a distribuição de produtos ao longo de uma rede de transportes, como uma malha ferroviária ou rodoviária. Por exemplo, deseja-se transportar o máximo de minério de ferro através de uma rede ferroviária, limitadas pela capacidade de cada via. O tratamento aqui dado ao algoritmo supõe a existência de um único “ponto de entrada” (uma fonte) e de um único “ponto de saída” (um terminal). Para valores de fluxo irracionais, o algoritmo poderá ficar em um loop infinito e nunca retornar o fluxo máximo desejado. O algoritmo de Edmonds-Karp é uma variação do algoritmo de Ford-Fulkerson, mas com um final garantido e com um tempo de execução independente do valor do fluxo máximo. (pt) 福特-富尔克森方法（英語：Ford–Fulkerson method），又稱福特-富尔克森算法（Ford–Fulkerson algorithm），是一类计算网络流的最大流的贪心算法。之所以称之为“方法”而不是“算法”，是因为它寻找增广路径的方式并不是完全确定的，而是有几种不同时间复杂度的实现方式。它在1956年由及发表。“福特-富尔克森”这个名词通常也指代埃德蒙兹-卡普算法，这是一个特殊的福特-富尔克森算法实现。 算法的思想如下：只要有一条从源点（开始节点）到汇点（结束节点）的路径，在路径的所有边上都有可用容量，就沿着这条路径发送一个流，流量由路径上的最小容量限制。 然后再找到另一条路径，一直到网络中不存在这种路径为止。 一条有可用容量的路径被称为一条增广路径。 (zh) Алгоритм або метод Форда — Фалкерсона знаходить максимальний потік у транспортній мережі. Метод Форда — Фалкерсона — метод, який базується на трьох концепціях: залишкові мережі, шляхи що збільшуються і розрізи. Ключову роль у методі Форда — Фалкерсона грають два поняття: залишкові мережі і доповнюють шляху. Дані концепції лежать в основі важливої теореми про максимальний потік і мінімальний розріз, яка визначає значення максимального нащадка за допомогою розрізів траспортної мережі. Метод Форда — Фалкерсона є ітеративним. Спочатку величині потоку присвоюється значення 0: при будь-яких , Є . На кожній ітерації величина потоку збільшується за допомогою пошуку «шляху, що збільшується» (тобто деякого шляху від джерела до стоку , уздовж якого можна послати більший потік) і подальшого збільшення потоку. Цей процес повторюється до тих пір, поки вже неможливо буде відшукати збільшуючийся шлях. (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Ford-Fulkerson_example_0.svg?width=300 |
| dbo:wikiPageExternalLink | http://community.topcoder.com/tc%3Fmodule=Static&d1=tutorials&d2=maxFlow http://rrusin.blogspot.com/2011/03/implementing-graph-editor-in-javafx.html https://archive.org/details/algorithmdesign0000klei/page/378 http://www.cs.pitt.edu/~kirk/cs1501/animations/Network.html |
| dbo:wikiPageID | 53777 (xsd:integer) |
| dbo:wikiPageLength | 17365 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1121114552 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Approximate_max-flow_min-cut_theorem dbc:Network_flow_problem dbr:Augmenting_path dbr:Depth-first_search dbr:Introduction_to_Algorithms dbr:L._R._Ford_Jr. dbr:Max-flow_min-cut_theorem dbr:Maximum_flow_problem dbr:Ordinal_numbers dbr:Berge's_theorem dbc:Articles_with_example_pseudocode dbc:Graph_algorithms dbr:D._R._Fulkerson dbr:Euclidean_algorithm dbr:Flow_network dbr:Breadth-first_search dbr:Dinic's_algorithm dbr:Edmonds–Karp_algorithm dbc:Articles_with_example_Python_(programming_language)_code dbr:Big_O_notation dbr:Greedy_algorithm dbr:Turn_restriction_routing dbr:Oreilly_Media dbr:Edmonds–Karp dbr:File:Ford-Fulkerson_example_0.svg dbr:File:Ford-Fulkerson_example_1.svg dbr:File:Ford-Fulkerson_example_2.svg dbr:File:Ford-Fulkerson_example_final.svg dbr:File:Ford-Fulkerson_forever.svg |
| dbp:wikiPageUsesTemplate | dbt:Cite_book dbt:Cite_journal dbt:Clear dbt:Commons_category-inline dbt:Harvtxt dbt:Mvar dbt:Reflist dbt:Short_description dbt:Use_American_English dbt:Algorithm-begin dbt:Algorithm-end |
| dcterms:subject | dbc:Network_flow_problem dbc:Articles_with_example_pseudocode dbc:Graph_algorithms dbc:Articles_with_example_Python_(programming_language)_code |
| gold:hypernym | dbr:Algorithm |
| rdf:type | dbo:Software yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:WikicatGraphAlgorithms yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:WikicatAlgorithms |
| rdfs:comment | L'algorisme de Ford-Fulkerson és un algorisme que calcula el flux màxim en una xarxa de flux. L'algorisme proposa buscar camins en els quals es pugui augmentar el flux, fins que s'aconsegueixi el flux màxim. La idea és trobar una ruta de penetració amb un flux positiu net que uneixi els nodes origen i destinació. El seu nom ve donat pels seus creadors, L. R. Ford, Jr. i D. R. Fulkerson. (ca) Der Algorithmus von Ford und Fulkerson ist ein Algorithmus aus dem mathematischen Teilgebiet der Graphentheorie zur Bestimmung eines maximalen Flusses in einem Flussnetzwerk mit rationalen Kapazitäten. Er wurde nach seinen Erfindern L.R. Ford Jr. und D.R. Fulkerson benannt.Die Anzahl der benötigten Operationen hängt vom Wert des maximalen Flusses ab und ist im Allgemeinen nicht polynomiell beschränkt.Weiterentwicklungen führten zum Algorithmus von Edmonds und Karp und dem Algorithmus von Dinic. (de) El algoritmo de Ford-Fulkerson propone buscar caminos en los que se pueda aumentar el flujo, hasta que se alcance el flujo máximo. Es aplicable a los Flujos maximales. La idea es encontrar una ruta de penetración con un flujo positivo neto que una los nodos origen y destino. Su nombre viene dado por sus creadores, y D. R. Fulkerson. (es) En informatique, l'algorithme de Ford-Fulkerson est un algorithme pour le problème de flot maximum, un problème d'optimisation classique dans le domaine de la recherche opérationnelle. Il est dû à Lester Randolph Ford junior et D. R. Fulkerson et c'est une variante de l'algorithme de Busacker et Gowen. (fr) In informatica, l'algoritmo di Ford-Fulkerson permette di trovare il flusso massimo che attraversa un grafo da un punto ad un altro di questo. Il nome deriva dai suoi due ideatori, Lester Randolph Ford e . (it) フォード・ファルカーソンのアルゴリズム（英: Ford-Fulkerson algorithm）とは、フローネットワークにおける最大フローを求めるアルゴリズムである。 と にちなんで命名されたもので、1956年に発表された。フォード・ファルカーソンのアルゴリズムの特殊版であるエドモンズ-カープアルゴリズムも「フォード・ファルカーソン」と呼ばれることがある。 このアルゴリズムの背景にある考え方は非常に単純である。始点から終点への経路があって、経路上の各辺に容量の空きがあるとき、その経路を使って流れを作ることができる。これを経路が見つかるたびにくりかえす。容量に空きがある経路を「増加道; augmenting path」と呼ぶ。 (ja) Metoda Forda-Fulkersona jest stosowana do znajdowania maksymalnego przepływu w sieci przepływowej. Stanowi podstawę wielu algorytmów, między innymi algorytmu Edmondsa-Karpa czy algorytmu Dynica Zasadę jej działania można streścić w następujący sposób: Należy zwiększać przepływ wzdłuż dowolnej ścieżki ze źródła do ujścia, dopóki jest to możliwe. (pl) Алгоритм Форда — Фалкерсона решает задачу нахождения максимального потока в транспортной сети. Идея алгоритма заключается в следующем. Изначально величине потока присваивается значение 0: для всех . Затем величина потока итеративно увеличивается посредством поиска увеличивающего пути (путь от источника к стоку , вдоль которого можно послать больший поток). Процесс повторяется, пока можно найти увеличивающий путь. (ru) 福特-富尔克森方法（英語：Ford–Fulkerson method），又稱福特-富尔克森算法（Ford–Fulkerson algorithm），是一类计算网络流的最大流的贪心算法。之所以称之为“方法”而不是“算法”，是因为它寻找增广路径的方式并不是完全确定的，而是有几种不同时间复杂度的实现方式。它在1956年由及发表。“福特-富尔克森”这个名词通常也指代埃德蒙兹-卡普算法，这是一个特殊的福特-富尔克森算法实现。 算法的思想如下：只要有一条从源点（开始节点）到汇点（结束节点）的路径，在路径的所有边上都有可用容量，就沿着这条路径发送一个流，流量由路径上的最小容量限制。 然后再找到另一条路径，一直到网络中不存在这种路径为止。 一条有可用容量的路径被称为一条增广路径。 (zh) Fordův-Fulkersonův algoritmus (pojmenovaný podle a D. R. Fulkersona) počítá maximální tok v síti. Název Ford-Fulkerson je také často používán pro Edmondsův-Karpův algoritmus, který je specializací Fordova-Fulkersonova algoritmu. (cs) The Ford–Fulkerson method or Ford–Fulkerson algorithm (FFA) is a greedy algorithm that computes the maximum flow in a flow network. It is sometimes called a "method" instead of an "algorithm" as the approach to finding augmenting paths in a residual graph is not fully specified or it is specified in several implementations with different running times. It was published in 1956 by L. R. Ford Jr. and D. R. Fulkerson. The name "Ford–Fulkerson" is often also used for the Edmonds–Karp algorithm, which is a fully defined implementation of the Ford–Fulkerson method. (en) O algoritmo de Ford-Fulkerson (assim designado em honra de e Delbert Ray Fulkerson) é um algoritmo utilizado para resolver problemas de fluxo em rede (network flow). O algoritmo é empregado quando se deseja encontrar um fluxo de valor máximo que faça o melhor uso possível das capacidades disponíveis na rede em questão. A história do algoritmo está relacionada à análise da rede ferroviária da União Soviética, tanto por russos quanto por americanos, nas décadas de 1930, 1940 e 1950. (pt) Алгоритм або метод Форда — Фалкерсона знаходить максимальний потік у транспортній мережі. Метод Форда — Фалкерсона — метод, який базується на трьох концепціях: залишкові мережі, шляхи що збільшуються і розрізи. Ключову роль у методі Форда — Фалкерсона грають два поняття: залишкові мережі і доповнюють шляху. Дані концепції лежать в основі важливої теореми про максимальний потік і мінімальний розріз, яка визначає значення максимального нащадка за допомогою розрізів траспортної мережі. Метод Форда — Фалкерсона є ітеративним. Спочатку величині потоку присвоюється значення 0: при будь-яких , Є . На кожній ітерації величина потоку збільшується за допомогою пошуку «шляху, що збільшується» (тобто деякого шляху від джерела до стоку , уздовж якого можна послати більший потік) і подальшого збільш (uk) |
| rdfs:label | Algorisme de Ford-Fulkerson (ca) Fordův–Fulkersonův algoritmus (cs) Algorithmus von Ford und Fulkerson (de) Algoritmo de Ford-Fulkerson (es) Ford–Fulkerson algorithm (en) Algoritmo di Ford-Fulkerson (it) Algorithme de Ford-Fulkerson (fr) フォード・ファルカーソンのアルゴリズム (ja) Metoda Forda-Fulkersona (pl) Algoritmo de Ford-Fulkerson (pt) Алгоритм Форда — Фалкерсона (ru) 福特-富尔克森算法 (zh) Алгоритм Форда — Фалкерсона (uk) |
| owl:sameAs | freebase:Ford–Fulkerson algorithm wikidata:Ford–Fulkerson algorithm dbpedia-ca:Ford–Fulkerson algorithm dbpedia-cs:Ford–Fulkerson algorithm dbpedia-de:Ford–Fulkerson algorithm dbpedia-es:Ford–Fulkerson algorithm dbpedia-fa:Ford–Fulkerson algorithm dbpedia-fr:Ford–Fulkerson algorithm dbpedia-he:Ford–Fulkerson algorithm http://hy.dbpedia.org/resource/Ֆորդ-ֆալկերսոնի_ալգորիթմ dbpedia-it:Ford–Fulkerson algorithm dbpedia-ja:Ford–Fulkerson algorithm dbpedia-pl:Ford–Fulkerson algorithm dbpedia-pt:Ford–Fulkerson algorithm dbpedia-ro:Ford–Fulkerson algorithm dbpedia-ru:Ford–Fulkerson algorithm dbpedia-sr:Ford–Fulkerson algorithm dbpedia-th:Ford–Fulkerson algorithm dbpedia-uk:Ford–Fulkerson algorithm dbpedia-vi:Ford–Fulkerson algorithm dbpedia-zh:Ford–Fulkerson algorithm https://global.dbpedia.org/id/2eQbE |
| prov:wasDerivedFrom | wikipedia-en:Ford–Fulkerson_algorithm?oldid=1121114552&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Ford-Fulkerson_example_0.svg wiki-commons:Special:FilePath/Ford-Fulkerson_example_1.svg wiki-commons:Special:FilePath/Ford-Fulkerson_example_2.svg wiki-commons:Special:FilePath/Ford-Fulkerson_example_final.svg wiki-commons:Special:FilePath/Ford-Fulkerson_forever.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Ford–Fulkerson_algorithm |
| is dbo:wikiPageDisambiguates of | dbr:Fulkerson |
| is dbo:wikiPageRedirects of | dbr:Ford-Fulkerson_algorithm dbr:Augmenting-path_method dbr:Ford-Fulkerson dbr:Ford-Fulkerson_method dbr:Ford_Fulkerson dbr:Ford_Fulkerson_method dbr:Ford–Fulkerson_method |
| is dbo:wikiPageWikiLink of | dbr:Push–relabel_maximum_flow_algorithm dbr:FFA dbr:List_of_algorithms dbr:Blossom_algorithm dbr:Approximate_max-flow_min-cut_theorem dbr:L._R._Ford_Jr. dbr:List_of_important_publications_in_mathematics dbr:Timeline_of_computational_mathematics dbr:Max-flow_min-cut_theorem dbr:Maximum_cardinality_matching dbr:Maximum_cut dbr:Maximum_flow_problem dbr:Network_flow_problem dbr:Quadratic_pseudo-Boolean_optimization dbr:Timeline_of_algorithms dbr:Zachary's_karate_club dbr:Hopcroft–Karp_algorithm dbr:Fulkerson dbr:Widest_path_problem dbr:Linear_network_coding dbr:Minimum-cost_flow_problem dbr:D._R._Fulkerson dbr:Flow_network dbr:Ford-Fulkerson_algorithm dbr:Breadth-first_search dbr:Dinic's_algorithm dbr:Edmonds–Karp_algorithm dbr:Graph_cut_optimization dbr:Graph_theory dbr:Graph_traversal dbr:Routing_Information_Protocol dbr:Hungarian_algorithm dbr:Birkhoff_polytope dbr:Heuristic_routing dbr:OpenLisp dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Pseudocode dbr:Augmenting-path_method dbr:Ford-Fulkerson dbr:Ford-Fulkerson_method dbr:Ford_Fulkerson dbr:Ford_Fulkerson_method dbr:Ford–Fulkerson_method |
| is foaf:primaryTopic of | wikipedia-en:Ford–Fulkerson_algorithm |
