运筹学英汉词汇(0,1) normalized ――0-1规范化Aactivity ――工序additivity――可加性adjacency matrix――邻接矩阵adjacent――邻接aligned game――结盟对策analytic functional equation――分析函数方程approximation method――近似法arc ――弧artificial constraint technique ――人工约束法artificial variable――人工变量augmenting path――增广路avoid cycle method ――避圈法Bbackward algorithm――后向算法balanced transportation problem――产销平衡运输问题basic feasible solution ――基本可行解basic matrix――基阵basic solution ――基本解basic variable ――基变量basic ――基basis iteration ――换基迭代Bayes decision――贝叶斯决策big M method ――大M 法binary integer programming ――0-1整数规划binary operation――二元运算binary relation――二元关系binary tree――二元树binomial distribution――二项分布bipartite graph――二部图birth and death process――生灭过程Bland rule ――布兰德法则branch node――分支点branch――树枝bridge――桥busy period――忙期Ccapacity of system――系统容量capacity――容量Cartesian product――笛卡儿积chain――链characteristic function――特征函数chord――弦circuit――回路coalition structure――联盟结构coalition――联盟combination me――组合法complement of a graph――补图complement of a set――补集complementary of characteristic function――特征函数的互补性complementary slackness condition ――互补松弛条件complementary slackness property――互补松弛性complete bipartite graph――完全二部图complete graph――完全图completely undeterministic decision――完全不确定型决策complexity――计算复杂性congruence method――同余法connected component――连通分支connected graph――连通图connected graph――连通图constraint condition――约束条件constraint function ――约束函数constraint matrix――约束矩阵constraint method――约束法constraint ――约束continuous game――连续对策convex combination――凸组合convex polyhedron ――凸多面体convex set――凸集core――核心corner-point ――顶点（角点）cost coefficient――费用系数cost function――费用函数cost――费用criterion ; test number――检验数critical activity ――关键工序critical path method ――关键路径法（CMP ）critical path scheduling ――关键路径cross job ――交叉作业curse of dimensionality――维数灾customer resource――顾客源customer――顾客cut magnitude ――截量cut set ――截集cut vertex――割点cutting plane method ――割平面法cycle ――回路cycling ――循环Ddecision fork――决策结点decision maker决――策者decision process of unfixed step number――不定期决策过程decision process――决策过程decision space――决策空间decision variable――决策变量decision决－－策decomposition algorithm――分解算法degenerate basic feasible solution ――退化基本可行解degree――度demand――需求deterministic inventory model――确定贮存模型deterministic type decision――确定型决策diagram method ――图解法dictionary ordered method ――字典序法differential game――微分对策digraph――有向图directed graph――有向图directed tree――有向树disconnected graph――非连通图distance――距离domain――定义域dominate――优超domination of strategies――策略的优超关系domination――优超关系dominion――优超域dual graph――对偶图Dual problem――对偶问题dual simplex algorithm ――对偶单纯形算法dual simplex method――对偶单纯形法dummy activity――虚工序dynamic game――动态对策dynamic programming――动态规划Eearliest finish time――最早可能完工时间earliest start time――最早可能开工时间economic ordering quantity formula――经济定购批量公式edge ――边effective set――有效集efficient solution――有效解efficient variable――有效变量elementary circuit――初级回路elementary path――初级通路elementary ――初等的element――元素empty set――空集entering basic variable ――进基变量equally liability method――等可能性方法equilibrium point――平衡点equipment replacement problem――设备更新问题equipment replacing problem――设备更新问题equivalence relation――等价关系equivalence――等价Erlang distribution――爱尔朗分布Euler circuit――欧拉回路Euler formula――欧拉公式Euler graph――欧拉图Euler path――欧拉通路event――事项expected value criterion――期望值准则expected value of queue length――平均排队长expected value of sojourn time――平均逗留时间expected value of team length――平均队长expected value of waiting time――平均等待时间exponential distribution――指数分布external stability――外部稳定性Ffeasible basis ――可行基feasible flow――可行流feasible point――可行点feasible region ――可行域feasible set in decision space――决策空间上的可行集feasible solution――可行解final fork――结局结点final solution――最终解finite set――有限集合flow――流following activity ――紧后工序forest――森林forward algorithm――前向算法free variable ――自由变量function iterative method――函数迭代法functional basic equation――基本函数方程function――函数fundamental circuit――基本回路fundamental cut-set――基本割集fundamental system of cut-sets――基本割集系统fundamental system of cut-sets――基本回路系统Ggame phenomenon――对策现象game theory――对策论game――对策generator――生成元geometric distribution――几何分布goal programming――目标规划graph theory――图论graph――图HHamilton circuit――哈密顿回路Hamilton graph――哈密顿图Hamilton path――哈密顿通路Hasse diagram――哈斯图hitchock method ――表上作业法hybrid method――混合法Iideal point――理想点idle period――闲期implicit enumeration method――隐枚举法in equilibrium――平衡incidence matrix――关联矩阵incident――关联indegree――入度indifference curve――无差异曲线indifference surface――无差异曲面induced subgraph――导出子图infinite set――无限集合initial basic feasible solution ――初始基本可行解initial basis ――初始基input process――输入过程Integer programming ――整数规划inventory policy―v存贮策略inventory problem―v货物存储问题inverse order method――逆序解法inverse transition method――逆转换法isolated vertex――孤立点isomorphism――同构Kkernel――核knapsack problem ――背包问题Llabeling method ――标号法latest finish time――最迟必须完工时间leaf――树叶least core――最小核心least element――最小元least spanning tree――最小生成树leaving basic variable ――出基变量lexicographic order――字典序lexicographic rule――字典序lexicographically positive――按字典序正linear multiobjective programming――线性多目标规划Linear Programming Model――线性规划模型Linear Programming――线性规划local noninferior solution――局部非劣解loop method――闭回路loop――圈loop――自环（环）loss system――损失制Mmarginal rate of substitution――边际替代率Marquart decision process――马尔可夫决策过程matching problem――匹配问题matching――匹配mathematical programming――数学规划matrix form ――矩阵形式matrix game――矩阵对策maximum element――最大元maximum flow――最大流maximum matching――最大匹配middle square method――平方取中法minimal regret value method――最小后悔值法minimum-cost flow――最小费用流mixed expansion――混合扩充mixed integer programming ――混合整数规划mixed Integer programming――混合整数规划mixed Integer ――混合整数规划mixed situation――混合局势mixed strategy set――混合策略集mixed strategy――混合策略mixed system――混合制most likely estimate――最可能时间multigraph――多重图multiobjective programming――多目标规划multiobjective simplex algorithm――多目标单纯形算法multiple optimal solutions ――多个最优解multistage decision problem――多阶段决策问题multistep decision process――多阶段决策过程Nn- person cooperative game ――n人合作对策n- person noncooperative game――n人非合作对策n probability distribution of customer arrive――顾客到达的n 概率分布natural state――自然状态nature state probability――自然状态概率negative deviational variables――负偏差变量negative exponential distribution――负指数分布network――网络newsboy problem――报童问题no solutions ――无解node――节点non-aligned game――不结盟对策nonbasic variable ――非基变量nondegenerate basic feasible solution――非退化基本可行解nondominated solution――非优超解noninferior set――非劣集noninferior solution――非劣解nonnegative constrains ――非负约束non-zero-sum game――非零和对策normal distribution――正态分布northwest corner method ――西北角法n-person game――多人对策nucleolus――核仁null graph――零图Oobjective function ――目标函数objective( indicator) function――指标函数one estimate approach――三时估计法operational index――运行指标operation――运算optimal basis ――最优基optimal criterion ――最优准则optimal solution ――最优解optimal strategy――最优策略optimal value function――最优值函数optimistic coefficient method――乐观系数法optimistic estimate――最乐观时间optimistic method――乐观法optimum binary tree――最优二元树optimum service rate――最优服务率optional plan――可供选择的方案order method――顺序解法ordered forest――有序森林ordered tree――有序树outdegree――出度outweigh――胜过Ppacking problem ――装箱问题parallel job――平行作业partition problem――分解问题partition――划分path――路path――通路pay-off function――支付函数payoff matrix――支付矩阵payoff――支付pendant edge――悬挂边pendant vertex――悬挂点pessimistic estimate――最悲观时间pessimistic method――悲观法pivot number ――主元plan branch――方案分支plane graph――平面图plant location problem――工厂选址问题player――局中人Poisson distribution――泊松分布Poisson process――泊松流policy――策略polynomial algorithm――多项式算法positive deviational variables――正偏差变量posterior――后验分析potential method ――位势法preceding activity ――紧前工序prediction posterior analysis――预验分析prefix code――前级码price coefficient vector ――价格系数向量primal problem――原问题principal of duality ――对偶原理principle of optimality――最优性原理prior analysis――先验分析prisoner’s dilemma――囚徒困境probability branch――概率分支production scheduling problem――生产计划program evaluation and review technique――计划评审技术(PERT) proof――证明proper noninferior solution――真非劣解pseudo-random number――伪随机数pure integer programming ――纯整数规划pure strategy――纯策略Qqueue discipline――排队规则queue length――排队长queuing theory――排队论Rrandom number――随机数random strategy――随机策略reachability matrix――可达矩阵reachability――可达性regular graph――正则图regular point――正则点regular solution――正则解regular tree――正则树relation――关系replenish――补充resource vector ――资源向量revised simplex method――修正单纯型法risk type decision――风险型决策rooted tree――根树root――树根Ssaddle point――鞍点saturated arc ――饱和弧scheduling (sequencing) problem――排序问题screening method――舍取法sensitivity analysis ――灵敏度分析server――服务台set of admissible decisions(policies) ――允许决策集合set of admissible states――允许状态集合set theory――集合论set――集合shadow price ――影子价格shortest path problem――最短路线问题shortest path――最短路径simple circuit――简单回路simple graph――简单图simple path――简单通路Simplex method of goal programming――目标规划单纯形法Simplex method ――单纯形法Simplex tableau――单纯形表single slack time ――单时差situation――局势situation――局势slack variable ――松弛变量sojourn time――逗留时间spanning graph――支撑子图spanning tree――支撑树spanning tree――生成树stable set――稳定集stage indicator――阶段指标stage variable――阶段变量stage――阶段standard form――标准型state fork――状态结点state of system――系统状态state transition equation――状态转移方程state transition――状态转移state variable――状态变量state――状态static game――静态对策station equilibrium state――统计平衡状态stationary input――平稳输入steady state――稳态stochastic decision process――随机性决策过程stochastic inventory method――随机贮存模型stochastic simulation――随机模拟strategic equivalence――策略等价strategic variable, decision variable ――决策变量strategy (policy) ――策略strategy set――策略集strong duality property ――强对偶性strong ε-core――强ε-核心strongly connected component――强连通分支strongly connected graph――强连通图structure variable ――结构变量subgraph――子图sub-policy――子策略subset――子集subtree――子树surplus variable ――剩余变量surrogate worth trade-off method――代替价值交换法symmetry property ――对称性system reliability problem――系统可靠性问题Tteam length――队长tear cycle method――破圈法technique coefficient vector ――技术系数矩阵test number of cell ――空格检验数the branch-and-bound technique ――分支定界法the fixed-charge problem ――固定费用问题three estimate approach一―时估计法total slack time――总时差traffic intensity――服务强度transportation problem ――运输问题traveling salesman problem――旅行售货员问题tree――树trivial graph――平凡图two person finite zero-sum game二人有限零和对策two-person game――二人对策two-phase simplex method ――两阶段单纯形法Uunbalanced transportation problem ――产销不平衡运输问题unbounded ――无界undirected graph――无向图uniform distribution――均匀分布unilaterally connected component――单向连通分支unilaterally connected graph――单向连通图union of sets――并集utility function――效用函数Vvertex――顶点voting game――投票对策Wwaiting system――等待制waiting time――等待时间weak duality property ――弱对偶性weak noninferior set――弱非劣集weak noninferior solution――弱非劣解weakly connected component――弱连通分支weakly connected graph――弱连通图weighed graph ――赋权图weighted graph――带权图weighting method――加权法win expectation――收益期望值Zzero flow――零流zero-sum game――零和对策zero-sum two person infinite game――二人无限零和对策。
![stoerwagner-mincut.[Stoer-Wagner,Prim,连通性,无向图,最小边割集]](https://imgs-1438308264.cos.ap-hongkong.myqcloud.com/072209d5360cba1aa811da51.webp)
A Simple Min-Cut AlgorithmMECHTHILD STOERTeleverkets Forskningsinstitutt,Kjeller,NorwayANDFRANK WAGNERFreie Universita¨t Berlin,Berlin-Dahlem,GermanyAbstract.We present an algorithm for finding the minimum cut of an undirected edge-weighted graph.It is simple in every respect.It has a short and compact description,is easy to implement,and has a surprisingly simple proof of correctness.Its runtime matches that of the fastest algorithm known.The runtime analysis is straightforward.In contrast to nearly all approaches so far,the algorithm uses no flow techniques.Roughly speaking,the algorithm consists of about͉V͉nearly identical phases each of which is a maximum adjacency search.Categories and Subject Descriptors:G.L.2[Discrete Mathematics]:Graph Theory—graph algorithms General Terms:AlgorithmsAdditional Key Words and Phrases:Min-Cut1.IntroductionGraph connectivity is one of the classical subjects in graph theory,and has many practical applications,for example,in chip and circuit design,reliability of communication networks,transportation planning,and cluster analysis.Finding the minimum cut of an undirected edge-weighted graph is a fundamental algorithmical problem.Precisely,it consists in finding a nontrivial partition of the graphs vertex set V into two parts such that the cut weight,the sum of the weights of the edges connecting the two parts,is minimum.A preliminary version of this paper appeared in Proceedings of the2nd Annual European Symposium on Algorithms.Lecture Notes in Computer Science,vol.855,1994,pp.141–147.This work was supported by the ESPRIT BRA Project ALCOM II.Authors’addresses:M.Stoer,Televerkets Forskningsinstitutt,Postboks83,2007Kjeller,Norway; e-mail:mechthild.stoer@nta.no.;F.Wagner,Institut fu¨r Informatik,Fachbereich Mathematik und Informatik,Freie Universita¨t Berlin,Takustraße9,Berlin-Dahlem,Germany;e-mail:wagner@inf.fu-berlin.de.Permission to make digital/hard copy of part or all of this work for personal or classroom use is granted without fee provided that the copies are not made or distributed for profit or commercial advantage,the copyright notice,the title of the publication,and its date appear,and notice is given that copying is by permission of the Association for Computing Machinery(ACM),Inc.To copy otherwise,to republish,to post on servers,or to redistribute to lists,requires prior specific permission and/or a fee.᭧1997ACM0004-5411/97/0700-0585$03.50Journal of the ACM,Vol.44,No.4,July1997,pp.585–591.586M.STOER AND F.WAGNER The usual approach to solve this problem is to use its close relationship to the maximum flow problem.The famous Max-Flow-Min-Cut-Theorem by Ford and Fulkerson[1956]showed the duality of the maximum flow and the so-called minimum s-t-cut.There,s and t are two vertices that are the source and the sink in the flow problem and have to be separated by the cut,that is,they have to lie in different parts of the partition.Until recently all cut algorithms were essentially flow algorithms using this duality.Finding a minimum cut without specified vertices to be separated can be done by finding minimum s-t-cuts for a fixed vertex s and all͉V͉Ϫ1possible choices of tʦVگ{s}and then selecting the lightest one.Recently Hao and Orlin[1992]showed how to use the maximum flow algorithm by Goldberg and Tarjan[1988]in order to solve the minimum cut problem in timeᏻ(͉VʈE͉log(͉V͉2/͉E͉),which is nearly as fast as the fastest maximum flow algorithms so far[Alon1990;Ahuja et al.1989;Cheriyan et al. 1990].Nagamochi and Ibaraki[1992a]published the first deterministic minimum cut algorithm that is not based on a flow algorithm,has the slightly better running time ofᏻ(͉VʈE͉ϩ͉V͉2log͉V͉),but is still rather complicated.In the unweighted case,they use a fast-search technique to decompose a graph’s edge set E into subsets E1,...,Esuch that the union of the first k E i’s is a k-edge-connected spanning subgraph of the given graph and has at most k͉V͉edges.They simulate this approach in the weighted case.Their work is one of a small number of papers treating questions of graph connectivity by non-flow-based methods [Nishizeki and Poljak1989;Nagamochi and Ibaraki1992a;Matula1992].Karger and Stein[1993]suggest a randomized algorithm that with high probability finds a minimum cut in timeᏻ(͉V͉2log͉V͉).In this context,we present in this paper a remarkably simple deterministic minimum cut algorithm with the fastest running time so far,established in Nagamochi and Ibaraki[1992b].We reduce the complexity of the algorithm of Nagamochi and Ibaraki by avoiding the unnecessary simulated decomposition of the edge set.This enables us to give a comparably straightforward proof of correctness avoiding,for example,the distinction between the unweighted, integer-,rational-,and real-weighted case.This algorithm was found independently by Frank[1994].Queyranne[1995]generalizes our simple approach to the minimization of submodular functions.The algorithm described in this paper was implemented by Kurt Mehlhorn from the Max-Planck-Institut,Saarbru¨cken and is part of the algorithms library LEDA[Mehlhorn and Na¨her1995].2.The AlgorithmThroughout the paper,we deal with an ordinary undirected graph G with vertex set V and edge set E.Every edge e has nonnegative real weight w(e).The simple key observation is that,if we know how to find two vertices s and t, and the weight of a minimum s-t-cut,we are nearly done:T HEOREM2.1.Let s and t be two vertices of a graph G.Let G/{s,t}be the graph obtained by merging s and t.Then a minimum cut of G can be obtained by taking the smaller of a minimum s-t-cut of G and a minimum cut of G/{s,t}.The theorem holds since either there is a minimum cut of G that separates s and t ,then a minimum s -t -cut of G is a minimum cut of G ;or there is none,then a minimum cut of G /{s ,t }does the job.So a procedure finding an arbitrary minimum s -t -cut can be used to construct a recursive algorithm to find a minimum cut of a graph.The following algorithm,known in the literature as maximum adjacency search or maximum cardinality search ,yields the desired s -t -cut.M INIMUM C UT P HASE (G ,w ,a )A 4{a }while A Vadd to A the most tightly connected vertexstore the cut-of-the-phase and shrink G by merging the two vertices added lastA subset A of the graphs vertices grows starting with an arbitrary single vertex until A is equal to V .In each step,the vertex outside of A most tightly connected with A is added.Formally,we add a vertexz ʦ͞A such that w ͑A ,z ͒ϭmax ͕w ͑A ,y ͉͒y ʦ͞A ͖,where w (A ,y )is the sum of the weights of all the edges between A and y .At the end of each such phase,the two vertices added last are merged ,that is,the two vertices are replaced by a new vertex,and any edges from the two vertices to a remaining vertex are replaced by an edge weighted by the sum of the weights of the previous two edges.Edges joining the merged nodes are removed.The cut of V that separates the vertex added last from the rest of the graph is called the cut-of-the-phase .The lightest of these cuts-of-the-phase is the result of the algorithm,the desired minimum cut:M INIMUM C UT (G ,w ,a )while ͉V ͉Ͼ1M INIMUM C UT P HASE (G ,w ,a )if the cut-of-the-phase is lighter than the current minimum cutthen store the cut-of-the-phase as the current minimum cutNotice that the starting vertex a stays the same throughout the whole algorithm.It can be selected arbitrarily in each phase instead.3.CorrectnessIn order to proof the correctness of our algorithms,we need to show the following somewhat surprising lemma.L EMMA 3.1.Each cut -of -the -phase is a minimum s -t -cut in the current graph ,where s and t are the two vertices added last in the phase .P ROOF .The run of a M INIMUM C UT P HASE orders the vertices of the current graph linearly,starting with a and ending with s and t ,according to their order of addition to A .Now we look at an arbitrary s -t -cut C of the current graph and show,that it is at least as heavy as the cut-of-the-phase.587A Simple Min-Cut Algorithm588M.STOER AND F.WAGNER We call a vertex v a active(with respect to C)when v and the vertex added just before v are in the two different parts of C.Let w(C)be the weight of C,A v the set of all vertices added before v(excluding v),C v the cut of A vഫ{v} induced by C,and w(C v)the weight of the induced cut.We show that for every active vertex vw͑A v,v͒Յw͑C v͒by induction on the set of active vertices:For the first active vertex,the inequality is satisfied with equality.Let the inequality be true for all active vertices added up to the active vertex v,and let u be the next active vertex that is added.Then we havew͑A u,u͒ϭw͑A v,u͒ϩw͑A uگA v,u͒ϭ:␣Now,w(A v,u)Յw(A v,v)as v was chosen as the vertex most tightly connected with A v.By induction w(A v,v)Յw(C v).All edges between A uگA v and u connect the different parts of C.Thus they contribute to w(C u)but not to w(C v).So␣Յw͑C v͒ϩw͑A uگA v,u͒Յw͑C u͒As t is always an active vertex with respect to C we can conclude that w(A t,t)Յw(C t)which says exactly that the cut-of-the-phase is at most as heavy as C.4.Running TimeAs the running time of the algorithm M INIMUM C UT is essentially equal to the added running time of the͉V͉Ϫ1runs of M INIMUM C UT P HASE,which is called on graphs with decreasing number of vertices and edges,it suffices to show that a single M INIMUM C UT P HASE needs at mostᏻ(͉E͉ϩ͉V͉log͉V͉)time yielding an overall running time ofᏻ(͉VʈE͉ϩ͉V͉2log͉V͉).The key to implementing a phase efficiently is to make it easy to select the next vertex to be added to the set A,the most tightly connected vertex.During execution of a phase,all vertices that are not in A reside in a priority queue based on a key field.The key of a vertex v is the sum of the weights of the edges connecting it to the current A,that is,w(A,v).Whenever a vertex v is added to A we have to perform an update of the queue.v has to be deleted from the queue,and the key of every vertex w not in A,connected to v has to be increased by the weight of the edge v w,if it exists.As this is done exactly once for every edge,overall we have to perform͉V͉E XTRACT M AX and͉E͉I NCREASE K EY ing Fibonacci heaps[Fredman and Tarjun1987],we can perform an E XTRACT M AX operation inᏻ(log͉V͉)amortized time and an I NCREASE K EY operation inᏻ(1)amortized time.Thus,the time we need for this key step that dominates the rest of the phase, isᏻ(͉E͉ϩ͉V͉log͉V͉).5.AnExample F IG .1.A graph G ϭ(V ,E )withedge-weights.F IG .2.The graph after the first M INIMUM C UT P HASE (G ,w ,a ),a ϭ2,and the induced ordering a ,b ,c ,d ,e ,f ,s ,t of the vertices.The first cut-of-the-phase corresponds to the partition {1},{2,3,4,5,6,7,8}of V with weight w ϭ5.F IG .3.The graph after the second M INIMUM C UT P HASE (G ,w ,a ),and the induced ordering a ,b ,c ,d ,e ,s ,t of the vertices.The second cut-of-the-phase corresponds to the partition {8},{1,2,3,4,5,6,7}of V with weight w ϭ5.F IG .4.After the third M INIMUM C UT P HASE (G ,w ,a ).The third cut-of-the-phase corresponds to the partition {7,8},{1,2,3,4,5,6}of V with weight w ϭ7.589A Simple Min-Cut AlgorithmACKNOWLEDGMENT .The authors thank Dorothea Wagner for her helpful re-marks.REFERENCESA HUJA ,R.K.,O RLIN ,J.B.,AND T ARJAN ,R.E.1989.Improved time bounds for the maximum flow problem.SIAM put.18,939–954.A LON ,N.1990.Generating pseudo-random permutations and maximum flow algorithms.Inf.Proc.Lett.35,201–204.C HERIYAN ,J.,H AGERUP ,T.,AND M EHLHORN ,K.1990.Can a maximum flow be computed in o (nm )time?In Proceedings of the 17th International Colloquium on Automata,Languages and Programming .pp.235–248.F ORD ,L.R.,AND F ULKERSON ,D.R.1956.Maximal flow through a network.Can.J.Math.8,399–404.F RANK , A.1994.On the Edge-Connectivity Algorithm of Nagamochi and Ibaraki .Laboratoire Artemis,IMAG,Universite ´J.Fourier,Grenoble,Switzerland.F REDMAN ,M.L.,AND T ARJAN ,R.E.1987.Fibonacci heaps and their uses in improved network optimization algorithms.J.ACM 34,3(July),596–615.G OLDBERG ,A.V.,AND T ARJAN ,R.E.1988.A new approach to the maximum-flow problem.J.ACM 35,4(Oct.),921–940.H AO ,J.,AND O RLIN ,J.B.1992.A faster algorithm for finding the minimum cut in a graph.In Proceedings of the 3rd ACM-SIAM Symposium on Discrete Algorithms (Orlando,Fla.,Jan.27–29).ACM,New York,pp.165–174.K ARGER ,D.,AND S TEIN ,C.1993.An O˜(n 2)algorithm for minimum cuts.In Proceedings of the 25th ACM Symposium on the Theory of Computing (San Diego,Calif.,May 16–18).ACM,New York,pp.757–765.F IG .5.After the fourth and fifth M INIMUM C UT P HASE (G ,w ,a ),respectively.The fourth cut-of-the-phase corresponds to the partition {4,7,8},{1,2,3,5,6}.The fifth cut-of-the-phase corresponds to the partition {3,4,7,8},{1,2,5,6}with weight w ϭ4.F IG .6.After the sixth and seventh M INIMUM C UT P HASE (G ,w ,a ),respectively.The sixth cut-of-the-phase corresponds to the partition {1,5},{2,3,4,6,7,8}with weight w ϭ7.The last cut-of-the-phase corresponds to the partition {2},V گ{2};its weight is w ϭ9.The minimum cut of the graph G is the fifth cut-of-the-phase and the weight is w ϭ4.590M.STOER AND F.WAGNERM ATULA ,D.W.1993.A linear time 2ϩ⑀approximation algorithm for edge connectivity.In Proceedings of the 4th ACM–SIAM Symposium on Discrete Mathematics ACM,New York,pp.500–504.M EHLHORN ,K.,AND N ¨AHER ,S.1995.LEDA:a platform for combinatorial and geometric mun.ACM 38,96–102.N AGAMOCHI ,H.,AND I BARAKI ,T.1992a.Linear time algorithms for finding a sparse k -connected spanning subgraph of a k -connected graph.Algorithmica 7,583–596.N AGAMOCHI ,H.,AND I BARAKI ,puting edge-connectivity in multigraphs and capaci-tated graphs.SIAM J.Disc.Math.5,54–66.N ISHIZEKI ,T.,AND P OLJAK ,S.1989.Highly connected factors with a small number of edges.Preprint.Q UEYRANNE ,M.1995.A combinatorial algorithm for minimizing symmetric submodular functions.In Proceedings of the 6th ACM–SIAM Symposium on Discrete Mathematics ACM,New York,pp.98–101.RECEIVED APRIL 1995;REVISED FEBRUARY 1997;ACCEPTED JUNE 1997Journal of the ACM,Vol.44,No.4,July 1997.591A Simple Min-Cut Algorithm。
负权边的单源最短路问题解决方法Dealing with the negative weight edge single-source shortest path problem can be challenging, but there are several effective methods to tackle this issue. One of the most commonly used algorithms for this problem is the Bellman-Ford algorithm, which can handle graphs with negative weight edges by detecting and updating the shortest paths iteratively. The algorithm is designed to accommodate negative weight edges by allowing for relaxation of edges multiple times until the shortest paths are determined. However, it is important to note that the Bellman-Ford algorithm has a time complexity of O(VE), where V is the number of vertices and E is the number of edges, which can make it less efficient for large graphs.解决负权边的单源最短路径问题可能是具有挑战性的，但有几种有效的方法可以应对这个问题。
其中最常用的算法之一是贝尔曼-福特算法，该算法可以通过迭代地检测和更新最短路径来处理带有负权边的图。
