埃德蒙兹-卡普算法 编辑
计算机科学中，埃德蒙兹-卡普算法通过实现福特-富尔克森算法来计算网络中的最大流，其时间复杂度为



O



{\displaystyle O}

。该算法由叶菲姆·迪尼茨在1970年最先提出，并由杰克·埃德蒙兹和理察德·卡普在1972年独立发表。
5
图片 0 图片
评论 0 评论
匿名用户 · [[ show_time(comment.timestamp) ]]
[[ nltobr(comment.content) ]]
相关
迪尼茨算法是在网络流计算最大流的时间复杂度复杂度的算法，设想由以色列计算机科学家叶菲姆·迪尼茨在1970年提出。算法



O



{\displaystyle O}

的时间复杂度类似于埃德蒙兹-卡普算法，其时间复杂度为



O



{\displaystyle O}

，迪尼茨算法与埃德蒙兹-卡普算法的不同之处在于它每轮算法都选择最短的可行路径进行增广。迪尼茨算法中采用高度标号以及阻塞流实现性能。
福特-富尔克森方法，又称福特-富尔克森算法，是一类计算网络流的最大流问题的贪心算法。之所以称之为“方法”而不是“算法”，是因为它寻找增广路径的方式并不是完全确定的，而是有几种不同时间复杂度的实现方式。它在1956年由小莱斯特·伦道夫·福特及德尔伯特·雷·富尔克森发表。“福特-富尔克森”这个名词通常也指代埃德蒙兹-卡普算法，这是一个特殊的福特-富尔克森算法实现。
福特-富尔克森方法，又称福特-富尔克森算法，是一类计算网络流的最大流问题的贪心算法。之所以称之为“方法”而不是“算法”，是因为它寻找增广路径的方式并不是完全确定的，而是有几种不同时间复杂度的实现方式。它在1956年由小莱斯特·伦道夫·福特及德尔伯特·雷·富尔克森发表。“福特-富尔克森”这个名词通常也指代埃德蒙兹-卡普算法，这是一个特殊的福特-富尔克森算法实现。
迪尼茨算法是在网络流计算最大流的时间复杂度复杂度的算法，设想由以色列计算机科学家叶菲姆·迪尼茨在1970年提出。算法



O



{\displaystyle O}

的时间复杂度类似于埃德蒙兹-卡普算法，其时间复杂度为



O



{\displaystyle O}

，迪尼茨算法与埃德蒙兹-卡普算法的不同之处在于它每轮算法都选择最短的可行路径进行增广。迪尼茨算法中采用高度标号以及阻塞流实现性能。
福特-富尔克森方法，又称福特-富尔克森算法，是一类计算网络流的最大流问题的贪心算法。之所以称之为“方法”而不是“算法”，是因为它寻找增广路径的方式并不是完全确定的，而是有几种不同时间复杂度的实现方式。它在1956年由小莱斯特·伦道夫·福特及德尔伯特·雷·富尔克森发表。“福特-富尔克森”这个名词通常也指代埃德蒙兹-卡普算法，这是一个特殊的福特-富尔克森算法实现。
迪尼茨算法是在网络流计算最大流的时间复杂度复杂度的算法，设想由以色列计算机科学家叶菲姆·迪尼茨在1970年提出。算法



O



{\displaystyle O}

的时间复杂度类似于埃德蒙兹-卡普算法，其时间复杂度为



O



{\displaystyle O}

，迪尼茨算法与埃德蒙兹-卡普算法的不同之处在于它每轮算法都选择最短的可行路径进行增广。迪尼茨算法中采用高度标号以及阻塞流实现性能。