当前位置：首页 » 编程博文

开发技术指南» 文章正文

    引言： 求最短路径的Dijkstra算法： Dijkstra算法是一种解

 

 

组合算法概论(3)
求最短路径的dijkstra算法:

dijkstra算法是一种解决最短路径问题的非常有效的算法,时间复杂度为 o(│v│2),下面是一段精确的描述（本段引自mit的课程主页,不翻译了,保持原作）中文描述一般的书上都会有: 【程序编程相关:VB中常用的数据类型和C#中数据类型的对】

【推荐阅读:由励志书籍的泛滥和良莠不齐想到的】

1. set i=0, s0= {u0=s}, l(u0)=0, and l(v)=infinity for v <> u0. if │v│ = 1 then stop, otherwise go to step 2. 【扩展信息:我做过的项目】

2. for each v in v\si, replace l(v) by min{l(v), l(ui)+dvui}. if l(v) is replaced, put a label (l(v), ui) on v.

3. find a vertex v which minimizes {l(v): v in v\si}, say ui+1.

4. let si+1 = si cup {ui+1}.

5. replace i by i+1. if i=│v?1 then stop, otherwise go to step 2.

6. set i=0, s0= {u0=s}, l(u0)=0, and l(v)=infinity for v <> u0. if │v│ = 1 then stop, otherwise go to step 2.

7. for each v in v\si, replace l(v) by min{l(v), l(ui)+dvui}. if l(v) is replaced, put a label (l(v), ui) on v.

8. find a vertex v which minimizes {l(v): v in v\si}, say ui+1.

9. let si+1 = si cup {ui+1}.

10. replace i by i+1. if i=│v│-1 then stop, otherwise go to step 2.

求二部图最大匹配（指派问题）的匈牙利算法:

谈匈牙利算法自然避不开hall定理,即是:对于二部图g,存在一个匹配m,使得x的所有顶点关于m饱与的充要条件是:对于x的任意一个子集a,与a邻接的点集为t(a),恒有: │t(a)│ >= │a│

匈牙利算法是基于hall定理中充分性证明的思想,其基本步骤为:

1．任给初始匹配m;

2．若x已饱与则结束,否则进行第3步;

3．在x中找到一个非饱与顶点x0,作v1 ← {x0},  v2 ← φ;

4．若t(v1) = v2则因为无法匹配而停止,否则任选一点y ∈t(v1)\v2;

5．若y已饱与则转6,否则做一条从x0 →y的可增广道路p,m←m⊕e(p),转2;

6．由于y已饱与,所以m中有一条边(y,z),作 v1 ← v1 ∪{z}, v2 ← v2 ∪ {y}, 转4;

关于求网络最大流与最小割的标号算法:

给定一个有向图g=(v,e),把图中的边看作管道,每条边上有一个权值,表示该管道的流量上限.给定源点s与汇点t,现在假设在s处有一个水源,t处有一个蓄水池,问从s到t的最大水流量是多少.这就叫做网络流问题.用数学语言描述就是:

...   下一页

» 本期热门文章：

· 热门栏目：

» 相关精选文章

» 其它相关：