前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >网络流问题,及其代码

网络流问题,及其代码

作者头像
流川疯
发布2019-01-18 15:32:39
8360
发布2019-01-18 15:32:39
举报

之前的一个学习一直在看图像分割的部分内容,基于交互的图像分割基本都是用图割的算法,全自动的图割算法也有最小生成树的改进算法。

现在想写点东西,从算法 的最本质问题,图论中的网络流问题开始,做个总结,也算是对知识的一个回顾。

网络最大流,增广路,残留网络,最小割这几个基本概念是构成最大流最小割定理的基本概念。而该定理是网络流理论的基础。

我们还有一下几个问题需要搞清楚:

1.最本质问题就是使用图割算法解决具体问题时候,是怎样构建图的,节点对应什么,边的权值对应什么。

2.为什么说图割算法能够达到能量最小化。

3.怎么引入能量这个概念的。

几种最大流算法的时间复杂度:

Algorithm

Principle

Complexity

Ford--Fulkerson, 1956

Finding flow augmenting paths

O(nm2)

Dinic, 1970

Shortest augmenting paths in one step

O(n2m)

in a dense graph:

O(n3)

in a sparse graph:

O(nm log(n))

Goldberg--Tarjan, 1985

Pushing a pre-flow

O(nm log(n2/m))

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2014年10月29日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
相关产品与服务
图像处理
图像处理基于腾讯云深度学习等人工智能技术,提供综合性的图像优化处理服务,包括图像质量评估、图像清晰度增强、图像智能裁剪等。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档