Dinic's algorithm (original) (raw)
Dinicův algoritmus je algoritmus vyvinutý Jefimem Dinicem (1970) pro výpočet maximálního toku v síti. Hlavní myšlenka algoritmu spočívá v iterativním výpočtu tzv. "blokujících" toků, které se postupně nasčítají až na tok maximální. Tento přístup dovoluje v průměrném případě počítat maximální tok rychleji než Fordovým–Fulkersonovým algoritmem, který pro výpočet využívá hledání zlepšujících cest.
| Property | Value |
|---|---|
| dbo:abstract | Dinicův algoritmus je algoritmus vyvinutý Jefimem Dinicem (1970) pro výpočet maximálního toku v síti. Hlavní myšlenka algoritmu spočívá v iterativním výpočtu tzv. "blokujících" toků, které se postupně nasčítají až na tok maximální. Tento přístup dovoluje v průměrném případě počítat maximální tok rychleji než Fordovým–Fulkersonovým algoritmem, který pro výpočet využívá hledání zlepšujících cest. (cs) Dinic's algorithm or Dinitz's algorithm is a strongly polynomial algorithm for computing the maximum flow in a flow network, conceived in 1970 by Israeli (formerly Soviet) computer scientist Yefim (Chaim) A. Dinitz. The algorithm runs in time and is similar to the Edmonds–Karp algorithm, which runs in time, in that it uses shortest augmenting paths. The introduction of the concepts of the level graph and blocking flow enable Dinic's algorithm to achieve its performance. (en) Der Algorithmus von Dinic ist ein Algorithmus aus der Graphentheorie zur Bestimmung eines maximalen Flusses in einem Netzwerk. Er wurde von (Jefim (Chaim) Dinic) entwickelt und 1970 publiziert. Er ist eine Weiterentwicklung des Edmonds-Karp-Algorithmus, den Dinic unabhängig von Jack Edmonds und Richard M. Karp entwickelte. Der Algorithmus von Dinic unterscheidet sich vom Edmonds-Karp-Algorithmus, indem in jedem Durchgang nicht nur an einem einzelnen kürzesten s-t-Weg augmentiert wird, sondern mitunter an größeren s-t-Flüssen, die sich aus mehreren kürzesten s-t-Wegen zusammensetzen. (de) El algoritmo de Dinic es un algoritmo de Tiempo polinómico para la computación de un Flujo maximal en una red de flujo, concebida en 1970 por el científico de la computación , israelí de origen soviético. El algoritmo es ejecutado en un tiempo de y está basado en el Algoritmo de Edmonds-Karp, el cual a su vez se ejecuta en un tiempo , y utiliza trayectorias de aumento más cortas. La introducción de los conceptos nivel de grafo y bloqueo de flujo es lo que define el rendimiento del algoritmo de Dinic. (es) L'algorithme de Dinic ou algorithme de Dinitz est un algorithme en temps polynomial (et même fortement polynomial) de calcul du flot maximum dans un réseau, publié en 1970 par Yefim Dinitz.Le temps de calcul est en pour un graphe dont est l'ensemble des sommets et l’ensemble des arcs. Il est semblable à l'algorithme d'Edmonds-Karp dont le temps d'exécution est en . Comme lui, il utilise des chemins augmentants de longueur minimale. L'introduction des concepts de graphe de niveau et de flot bloquant permet d'obtenir cette meilleure performance. (fr) Algorytm Dynica – algorytm o złożoności czasowej rozwiązujący problem maksymalnego przepływu w sieci przepływowej umożliwiający odnajdywanie przepływu blokującego w . Algorytm skonstruowany został w 1970 roku przez izraelskiego profesora - . Strukturą zbliżony jest do alg. Edmondsa-Karpa. 1. * krok - dziel graf na L warstw (przegląd wszerz) 2. * krok - utwórz ścieżki powiększające (przegląd w głąb), nie przemieszczając się względem tej samej warstwy 3. * krok - wyznacz maksymalny przepływ (pl) Алгоритм Диница — полиномиальный алгоритм для нахождения максимального потока в транспортной сети, предложенный в 1970 году советским (впоследствии израильским) математиком . Временная сложность алгоритма составляет . Получить такую оценку позволяет введение понятий вспомогательной сети и блокирующего (псевдомаксимального) потока. В сетях с единичными пропускными способностями существует более сильная оценка временной сложности: . (ru) Алгоритм Дініца — поліноміальний алгоритм для знаходження максимального потоку у транспортної мережі, запропонований 1970 року ізраїльським (колишнім радянським) ученим Юхимом Дініцем. І алгоритм Дініца, і алгоритм Едмондса–Карпа незалежно показують, що в алгоритмі Форда — Фалкерсона в разі найкоротшого доповнювального шляху його довжина доповнює шляху не зменшується. Часова складність алгоритму становить . Отримати таку оцінку дозволяє введення понять допоміжної мережі та блокуючого (псевдомаксимального) потоку. В мережах з одиничними пропускними здатностями існує сильніша оцінка часової складності: . (uk) 迪尼茨算法是在网络流计算最大流的强多项式复杂度的算法，设想由以色列计算机科学家叶菲姆·迪尼茨在1970年提出。算法的时间复杂度类似于埃德蒙兹-卡普算法，其时间复杂度为，迪尼茨算法与埃德蒙兹-卡普算法的不同之处在于它每轮算法都选择最短的可行路径进行增广。迪尼茨算法中采用高度标号（level graph）以及阻塞流（blocking flow）实现性能。 (zh) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Dinic_algorithm_G1.svg?width=300 |
| dbo:wikiPageExternalLink | http://www.cs.bgu.ac.il/~dinitz/Papers/Dinitz_alg.pdf |
| dbo:wikiPageID | 23635821 (xsd:integer) |
| dbo:wikiPageLength | 10875 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1119884267 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Bipartite_matching dbc:Network_flow_problem dbr:Depth-first_search dbr:Maximum_flow_problem dbr:Alexander_V._Karzanov dbr:Hopcroft–Karp_algorithm dbc:Graph_algorithms dbr:Flow_network dbr:Breadth-first_search dbr:Edmonds–Karp_algorithm dbr:Ford–Fulkerson_algorithm dbr:Georgy_Adelson-Velsky dbr:Technion_–_Israel_Institute_of_Technology dbr:Maximum_flow dbr:Shimon_Even dbr:Strongly_polynomial dbr:Dynamic_trees dbr:File:Dinic_algorithm_G1.svg dbr:File:Dinic_algorithm_G2.svg dbr:File:Dinic_algorithm_G3.svg dbr:File:Dinic_algorithm_GL1.svg dbr:File:Dinic_algorithm_GL2.svg dbr:File:Dinic_algorithm_GL3.svg dbr:File:Dinic_algorithm_Gf1.svg dbr:File:Dinic_algorithm_Gf2.svg dbr:File:Dinic_algorithm_Gf3.svg |
| dbp:wikiPageUsesTemplate | dbt:Cite_book dbt:Reflist dbt:Sfn dbt:Optimization_algorithms |
| dct:subject | dbc:Network_flow_problem dbc:Graph_algorithms |
| rdf:type | yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:WikicatGraphAlgorithms yago:YagoPermanentlyLocatedEntity yago:Rule105846932 |
| rdfs:comment | Dinicův algoritmus je algoritmus vyvinutý Jefimem Dinicem (1970) pro výpočet maximálního toku v síti. Hlavní myšlenka algoritmu spočívá v iterativním výpočtu tzv. "blokujících" toků, které se postupně nasčítají až na tok maximální. Tento přístup dovoluje v průměrném případě počítat maximální tok rychleji než Fordovým–Fulkersonovým algoritmem, který pro výpočet využívá hledání zlepšujících cest. (cs) Dinic's algorithm or Dinitz's algorithm is a strongly polynomial algorithm for computing the maximum flow in a flow network, conceived in 1970 by Israeli (formerly Soviet) computer scientist Yefim (Chaim) A. Dinitz. The algorithm runs in time and is similar to the Edmonds–Karp algorithm, which runs in time, in that it uses shortest augmenting paths. The introduction of the concepts of the level graph and blocking flow enable Dinic's algorithm to achieve its performance. (en) Der Algorithmus von Dinic ist ein Algorithmus aus der Graphentheorie zur Bestimmung eines maximalen Flusses in einem Netzwerk. Er wurde von (Jefim (Chaim) Dinic) entwickelt und 1970 publiziert. Er ist eine Weiterentwicklung des Edmonds-Karp-Algorithmus, den Dinic unabhängig von Jack Edmonds und Richard M. Karp entwickelte. Der Algorithmus von Dinic unterscheidet sich vom Edmonds-Karp-Algorithmus, indem in jedem Durchgang nicht nur an einem einzelnen kürzesten s-t-Weg augmentiert wird, sondern mitunter an größeren s-t-Flüssen, die sich aus mehreren kürzesten s-t-Wegen zusammensetzen. (de) El algoritmo de Dinic es un algoritmo de Tiempo polinómico para la computación de un Flujo maximal en una red de flujo, concebida en 1970 por el científico de la computación , israelí de origen soviético. El algoritmo es ejecutado en un tiempo de y está basado en el Algoritmo de Edmonds-Karp, el cual a su vez se ejecuta en un tiempo , y utiliza trayectorias de aumento más cortas. La introducción de los conceptos nivel de grafo y bloqueo de flujo es lo que define el rendimiento del algoritmo de Dinic. (es) L'algorithme de Dinic ou algorithme de Dinitz est un algorithme en temps polynomial (et même fortement polynomial) de calcul du flot maximum dans un réseau, publié en 1970 par Yefim Dinitz.Le temps de calcul est en pour un graphe dont est l'ensemble des sommets et l’ensemble des arcs. Il est semblable à l'algorithme d'Edmonds-Karp dont le temps d'exécution est en . Comme lui, il utilise des chemins augmentants de longueur minimale. L'introduction des concepts de graphe de niveau et de flot bloquant permet d'obtenir cette meilleure performance. (fr) Algorytm Dynica – algorytm o złożoności czasowej rozwiązujący problem maksymalnego przepływu w sieci przepływowej umożliwiający odnajdywanie przepływu blokującego w . Algorytm skonstruowany został w 1970 roku przez izraelskiego profesora - . Strukturą zbliżony jest do alg. Edmondsa-Karpa. 1. * krok - dziel graf na L warstw (przegląd wszerz) 2. * krok - utwórz ścieżki powiększające (przegląd w głąb), nie przemieszczając się względem tej samej warstwy 3. * krok - wyznacz maksymalny przepływ (pl) Алгоритм Диница — полиномиальный алгоритм для нахождения максимального потока в транспортной сети, предложенный в 1970 году советским (впоследствии израильским) математиком . Временная сложность алгоритма составляет . Получить такую оценку позволяет введение понятий вспомогательной сети и блокирующего (псевдомаксимального) потока. В сетях с единичными пропускными способностями существует более сильная оценка временной сложности: . (ru) Алгоритм Дініца — поліноміальний алгоритм для знаходження максимального потоку у транспортної мережі, запропонований 1970 року ізраїльським (колишнім радянським) ученим Юхимом Дініцем. І алгоритм Дініца, і алгоритм Едмондса–Карпа незалежно показують, що в алгоритмі Форда — Фалкерсона в разі найкоротшого доповнювального шляху його довжина доповнює шляху не зменшується. Часова складність алгоритму становить . Отримати таку оцінку дозволяє введення понять допоміжної мережі та блокуючого (псевдомаксимального) потоку. В мережах з одиничними пропускними здатностями існує сильніша оцінка часової складності: . (uk) 迪尼茨算法是在网络流计算最大流的强多项式复杂度的算法，设想由以色列计算机科学家叶菲姆·迪尼茨在1970年提出。算法的时间复杂度类似于埃德蒙兹-卡普算法，其时间复杂度为，迪尼茨算法与埃德蒙兹-卡普算法的不同之处在于它每轮算法都选择最短的可行路径进行增广。迪尼茨算法中采用高度标号（level graph）以及阻塞流（blocking flow）实现性能。 (zh) |
| rdfs:label | Dinicův algoritmus (cs) Algorithmus von Dinic (de) Algoritmo de Dinic (es) Dinic's algorithm (en) Algorithme de Dinic (fr) Algorytm Dynica (pl) Алгоритм Диница (ru) Алгоритм Дініца (uk) 迪尼茨算法 (zh) |
| owl:sameAs | freebase:Dinic's algorithm yago-res:Dinic's algorithm wikidata:Dinic's algorithm dbpedia-cs:Dinic's algorithm dbpedia-de:Dinic's algorithm dbpedia-es:Dinic's algorithm dbpedia-fa:Dinic's algorithm dbpedia-fr:Dinic's algorithm dbpedia-pl:Dinic's algorithm dbpedia-ru:Dinic's algorithm dbpedia-sr:Dinic's algorithm dbpedia-th:Dinic's algorithm dbpedia-uk:Dinic's algorithm dbpedia-vi:Dinic's algorithm dbpedia-zh:Dinic's algorithm https://global.dbpedia.org/id/4tWip |
| prov:wasDerivedFrom | wikipedia-en:Dinic's_algorithm?oldid=1119884267&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Dinic_algorithm_G1.svg wiki-commons:Special:FilePath/Dinic_algorithm_G2.svg wiki-commons:Special:FilePath/Dinic_algorithm_G3.svg wiki-commons:Special:FilePath/Dinic_algorithm_GL1.svg wiki-commons:Special:FilePath/Dinic_algorithm_GL2.svg wiki-commons:Special:FilePath/Dinic_algorithm_GL3.svg wiki-commons:Special:FilePath/Dinic_algorithm_Gf1.svg wiki-commons:Special:FilePath/Dinic_algorithm_Gf2.svg wiki-commons:Special:FilePath/Dinic_algorithm_Gf3.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Dinic's_algorithm |
| is dbo:wikiPageDisambiguates of | dbr:Dinic |
| is dbo:wikiPageRedirects of | dbr:Dinitz_blocking_flow_algorithm dbr:Dinic's_Algorithm dbr:Blocking_flow dbr:Dinic_algorithm |
| is dbo:wikiPageWikiLink of | dbr:List_of_algorithms dbr:Maximum_flow_problem dbr:Network_flow_problem dbr:Timeline_of_algorithms dbr:Link/cut_tree dbr:Hopcroft–Karp_algorithm dbr:Flow_network dbr:Edmonds–Karp_algorithm dbr:Ford–Fulkerson_algorithm dbr:Dinitz_blocking_flow_algorithm dbr:Dinic dbr:Dinic's_Algorithm dbr:Parallel_breadth-first_search dbr:Blocking_flow dbr:Dinic_algorithm |
| is foaf:primaryTopic of | wikipedia-en:Dinic's_algorithm |
