精华内容
下载资源
问答
  • 主要为大家详细介绍了Python使用遗传算法解决最大流问题,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • ):最大流最小割定理:最大流求解Ford_Fullkerson方法最大容量增广(MCA,Maximum Capacity Augmentation)最短路径增广(EK算法,Edmond-Karp)MCA和EK算法的实现举例源码输出参考 概念介绍 流(Flow) 一种抽象的...

    概念介绍

    流(Flow)

    一种抽象的实体,在源点流出,通过边输送,在汇点被吸收,将目标从一个地点输送到另一个地点。
    

    网络流(Network flow)

    在一个每条边都有容量(Capacity)的有向图分配流,使一条边的流量不会超过它的容量。
    

    流网络(G,s,t,c)(G,s,t,c)

    (𝑮,𝒔,𝒕,𝒄)
    𝑮→图(𝐺𝑟𝑜𝑢𝑝) 𝒔→源点(𝑆𝑜𝑢𝑟𝑐𝑒) t→汇点(𝑡𝑎𝑟𝑔𝑒𝑡) 𝒄→容量函数(𝑐𝑎𝑝𝑎𝑐𝑖𝑡𝑦)

    流量函数 f(u,v)f(u,v)
    容量函数 c(u,v)c(u,v)
    剩余容量函数 r(u,v)=c(u,v)f(u,v)r(u,v)=c(u,v)-f(u,v)

    对于流量函数f(u,v)f(u,v),满足以下条件:

    1. 斜对称: f(u,v)=f(v,u)f(u,v)=-f(v,u)
    2. 容量约束: f(u,v)=f(u,v)f(u,v)=f(u,v)
    3. 流量守恒: uVs,t,vVf(u,v)=0∀u \in V-{s,t}, \sum_{v \in V}{f(u,v)=0}
    4. 零自流量: f(u,u)=0f(u,u)=0

    顶点𝒗的级𝒍𝒆𝒗𝒆𝒍(𝒗):

    由源点𝑠到顶点𝑣的通路中的最少的边数

    分级图𝑳为(𝑽,𝑬′),其中𝑬′={(𝒖,𝒗)|𝒍𝒆𝒗𝒆𝒍(𝒗)=𝒍𝒆𝒗𝒆𝒍(𝒖)+𝟏}

    最大流最小割定理:

    对流网络(G,s,t,c)(G,s,t,c)ffGG中的流,则下面的命题等价:

    1. 存在一个容量为c(u,v)=fc(u,v)=|f|的割集S,T{S,T};
    2. ffGG中的最大流;
    3. 不存在ff的增广路径。

    最大流求解

    Ford_Fullkerson方法

    根据最大流最小割定理,在寻找图𝐺的最大流时,可以令𝐺的初始流量𝑓=0,然后重复地在𝑓的剩余图中寻找一条增广路径,用该路径的瓶颈流量来扩张流量𝑓,直到剩余图中不存在增广路径为止。

    最大容量增广(MCA,Maximum Capacity Augmentation)

    根据Ford-Fullkerson方法求解最大流问题,不同点在于指定了增广路径的选取方法:搜索一条具有最大瓶颈容量的增广路径来加快算法运行时间(贪婪算法)。

    步骤:

    1. 对所有(u,v)E(u,v) \in E, r(u,v)=c(u,v)r(u,v)=c(u,v);
    2. 对所有(u,v)E(u,v) \in E, f(u,v)=0f(u,v)=0;
    3. 若剩余图𝑅中存在增广路径,找出使得瓶颈流量𝛿最大的增广路径𝑝,转4;不存在转6;
    4. 对所有增广路径pp上的边(u,v)p(u,v) \in p,令 r(u,v)=r(u,v)Δr(u,v)=r(u,v)-\Delta
    5. 对所有增广路径pp上的边(u,v)p(u,v) \in p,令 f(u,v)=f(u,v)+Δf(u,v)=f(u,v)+\Delta,转3;
    6. 返回最大流ff

    最短路径增广(EK算法,Edmond-Karp)

    根据Ford-Fullkerson方法求解最大流问题,不同点在于指定了增广路径的选取方法:搜索一条具有最短路径(边最少)的增广路径来加快算法运行时间。

    步骤:

    1. 对所有(u,v)E(u,v) \in E, r(u,v)=c(u,v)r(u,v)=c(u,v);
    2. 对所有(u,v)E(u,v) \in E, f(u,v)=0f(u,v)=0;
    3. 按照分级图原理,用BFS在剩余图中搜索由𝑠到𝑡的最短路径𝑝,转4;不存在转6;
    4. 对所有增广路径pp上的边(u,v)p(u,v) \in p,令 r(u,v)=r(u,v)Δr(u,v)=r(u,v)-\Delta
    5. 对所有增广路径pp上的边(u,v)p(u,v) \in p,令 f(u,v)=f(u,v)+Δf(u,v)=f(u,v)+\Delta,转3;
    6. 返回最大流ff

    MCA和EK算法的实现

    举例

    c(u,v)c(u,v)

    源码

    # -*- coding: utf-8 -*-
    # Copyright (c) 2019 - Youpeng Hu <yoooooohu@foxmail.com>
    import copy
    
    class Weighted_Gragh:
        def __init__(self, vertices):
            self.adjacent_table = {}
            for vertex in vertices:
                self.adjacent_table.update({vertex: {}})
            print("Weighted Gragh has been created Successfully!!!!!")            
            print('self.adjacent_table', end=" -> \n")
            print(self.adjacent_table)
    
        
        def addNeighbor(self, source, terminal, weigh):
            neighbor_list = self.adjacent_table[source]
            neighbor_list.update({terminal: weigh})
            self.adjacent_table.update({source: neighbor_list})
            print('Add a new Neighbor\nself.adjacent_table', end=" -> \n")
            print(self.adjacent_table)
    
        def maxCapacityAugmentation(self, source, terminal):
            print('###################################')
            print('Max Capacity Augmentation algorithm')
            self.f_table = {}
            self.r_table = copy.deepcopy(self.adjacent_table)
    
            path = self.findMaxBottleneckDFS(source, terminal, 0, {})        
            while path:
                print('path', end=" >>>>>>>>>>>>>>\n")
                print(path)
                bottleneck = self.foundBottleneck(path, terminal)
    
                self.argumentFlow(bottleneck, path, terminal)
    
                path = self.findMaxBottleneckDFS(source, terminal, 0, {})
    
            return self.f_table
    
        def findMaxBottleneckDFS(self, source, terminal, level, level_table, max_bottleneck = 1000):
            print('(source, terminal, max_bottleneck)', end=" ->\n")
            print((source, terminal, max_bottleneck))
    
            level += 1
            for end, weight in self.r_table[source].items():
                if weight > 0:
                    if level not in level_table:
                        level_table[level] = {}
                    if end not in level_table[level]:
                        level_table[level][end] = {}    
                    level_table[level][end] = {source: weight}
                    if end == terminal:
                        return level_table
                    if weight >= max_bottleneck:
                        return self.findMaxBottleneckDFS(end, terminal, level, level_table, max_bottleneck = max_bottleneck)
                    elif weight < max_bottleneck:
                        return self.findMaxBottleneckDFS(end, terminal, level, level_table, max_bottleneck = weight)
                elif weight < 0:
                    raise ("the value of weigh have some problem")
    
        def edmondKarp(self, source, terminal):
            print('###################################')
            print('edmondKarp algorithm')
            self.f_table = {}
            self.r_table = copy.deepcopy(self.adjacent_table)
            path = self.findTerminalBFS([source], terminal, 0, {}, [source])        
            while path:
                print('argument table', end=" >>>>>>>>>>>>>>\n")
                print(path)
                bottleneck = self.foundBottleneck(path, terminal)
    
                self.argumentFlow(bottleneck, path, terminal)
    
                path = self.findTerminalBFS([source], terminal, 0, {}, [source])
      
            return self.f_table
    
        def findTerminalBFS(self, start_list, terminal, level, level_table, visited):
            print('(start_list, terminal, level, level_table, visited)', end=" ->\n")
            print((start_list, terminal, level, level_table, visited))
            level += 1
            end_list = []
            for start in start_list:
                for end, weight in self.r_table[start].items():
                    if (weight > 0) & (end not in visited):
                        if level not in level_table:
                            level_table[level] = {}
                        if end not in level_table[level]:
                            level_table[level][end] = {}
                        level_table[level][end] = {start: weight}
                        if terminal == end:
                            return level_table
                        visited.append(end)
                        end_list.append(end)
    
                    elif weight < 0:
                        raise ("the value of weight have some problem")
            if end_list:
                return self.findTerminalBFS(end_list, terminal, level, level_table, visited)
    
        def foundBottleneck(self, path, terminal):
            weight_list = []
            tmp_level = max(path.keys())
            print('tmp_level', end =" ->")
            print(tmp_level)
    
            start = terminal
            while tmp_level > 0:
                for start, weight in path[tmp_level][start].items():
                    pass
                tmp_level -= 1
                weight_list.append(weight)                
            print('Bottleneck of traffic -> {}'.format(min(weight_list)))
            return min(weight_list)
    
        def argumentFlow(self, bottleneck, path, terminal):
            tmp_level = max(path.keys())
    
            end = terminal
            print('path:\n', terminal, end="")
            while tmp_level > 0:
                for start, weight in path[tmp_level][end].items():
                    pass
                print("->", start, weight, end="")
                if start not in self.f_table:
                    self.f_table[start] = {}           
                if end not in self.f_table[start]:
                    self.f_table[start][end] = 0          
                self.f_table[start][end] += bottleneck
                self.r_table[start][end] -= bottleneck
                tmp_level -= 1
                end = start
            print()     
            print('self.r_table', end=" ->\n")
            print(self.r_table)
            print('self.f_table', end=" ->\n")
            print(self.f_table) 
    
    if __name__ == '__main__':
        gragh = Weighted_Gragh(['s','a','b','c','d','e','f','g','h','i','j','t'])
        gragh.addNeighbor('s', 'a', 6)
        gragh.addNeighbor('s', 'c', 8)
        gragh.addNeighbor('a', 'b', 3)
        gragh.addNeighbor('a', 'd', 3)
        gragh.addNeighbor('b', 't', 10)
        gragh.addNeighbor('c', 'd', 4)
        gragh.addNeighbor('c', 'f', 4)
        gragh.addNeighbor('d', 'e', 3)
        gragh.addNeighbor('d', 'g', 6)
        gragh.addNeighbor('e', 'b', 7)
        gragh.addNeighbor('e', 'j', 4)
        gragh.addNeighbor('f', 'h', 4)
        gragh.addNeighbor('g', 'e', 7)
        gragh.addNeighbor('h', 'g', 1)
        gragh.addNeighbor('h', 'i', 3)
        gragh.addNeighbor('i', 'j', 3)
        gragh.addNeighbor('j', 't', 5)
    
        gragh.edmondKarp('s', 't')
        print('gragh.f_table for Edmond_Karp', end="->>>>>>>>>>>>>>>>>>>>>>>>>>>\n")
        print(gragh.f_table)
        print('gragh.r_table for Edmond_Karp', end="->>>>>>>>>>>>>>>>>>>>>>>>>>>\n")
        print(gragh.r_table)   
    
        gragh.maxCapacityAugmentation('s', 't')
        print('gragh.f_table for maxCapacityAugmentation', end="->>>>>>>>>>>>>>>>>>>>>>>>>>>\n")
        print(gragh.f_table)
        print('gragh.r_table for maxCapacityAugmentation', end="->>>>>>>>>>>>>>>>>>>>>>>>>>>\n")
        print(gragh.r_table)
    

    输出参考

    无论对于MCA或EK算法,输出的r_table

    gragh.r_table
    {'s': {'a': 0, 'c': 0}, 
     'a': {'b': 0, 'd': 0}, 
     'b': {'t': 0}, 
     'c': {'d': 0, 'f': 0}, 
     'd': {'e': 0, 'g': 2}, 
     'e': {'b': 0, 'j': 3}, 
     'f': {'h': 0}, 
     'g': {'e': 2}, 
     'h': {'g': 0, 'i': 0}, 
     'i': {'j': 0}, 
     'j': {'t': 1}, 
     't': {}
    }  
    

    最大流fmax(u,v)f_{max}(u,v)
    最大流

    edited date: 2019-11-15

    展开全文
  • Python算法分析与设计:最大流算法

    千次阅读 2019-02-01 14:30:03
    Python算法分析与设计:最大流算法 一、实验目的 1、掌握最大流问题的定义,了解流量、容量以及他们之间的关系。 2、掌握通过增广路径求最大流问题的Forder-Fulkerson和Edmond-Karp算法,理解这两个算法之间的异同 3...

    Python算法分析与设计:最大流算法

    一、实验目的
    1、掌握最大流问题的定义,了解流量、容量以及他们之间的关系。
    2、掌握通过增广路径求最大流问题的Forder-Fulkerson和Edmond-Karp算法,理解这两个算法之间的异同
    3、了解将计算问题转换为最大流问题的基本流程。掌握通过最大流算法求解二向图最大匹配和文件传输中的不重合边等问题的方法。

    二、实验工具
    Win10操作系统、python3.7编译环境、IDLE编译器

    三、实验内容
    已知一个容量(流量)网络,要求应用Edmond-Karp算法,求出该容量网络的最大流,容量网络各边的容量值可以由用户设置。

    四、实验调试过程
    实验代码如下所示:

    # -*- encoding:gbk -*-
    from queue import Queue
    
    #n #边的个数
    m = 6#点的个数
    
    residual = [[0 for i in range(m)] for j in range(m)]
    #残余图的剩余流量
    maxflowgraph = [[0 for i in range(m)] for j in range(m)]
    #记录最大流图,初始都为0
    flow = [0 for i in range(m)]
    #记录增广路径前进过程记录的最小流量
    pre = [float('inf') for i in range(m)]
    #记录增广路径每个节点的前驱
    q = Queue()
    #队列,用于BFS地寻找增广路径
    
    #设置初始图的流量走向
    residual[0][1]=3
    residual[0][2]=2
    residual[1][2]=1
    residual[1][3]=3
    residual[1][4]=4
    residual[2][4]=2
    residual[3][5]=2
    residual[4][5]=3
    
    def BFS(source,sink):
        q.empty()#清空队列
    
        for i in range(m):
            pre[i] = float('inf')
    
        flow[source] = float('inf')#这里要是不改,那么找到的路径的流量永远是0
        #不用将flow的其他清零
        q.put(source)
        while(not q.empty()):
            index = q.get()
            if(index == sink):
                break
            for i in range(m):
                if( (i!=source) & (residual[index][i]>0) & (pre[i]==float('inf')) ):
                    #i!=source,从source到source不用分析了
                    #residual[index][i]>0,边上有流量可以走
                    #pre[i]==float('inf'),代表BFS还没有延伸到这个点上
                    pre[i] = index
                    flow[i] = min(flow[index],residual[index][i]) 
                    q.put(i)
        if(pre[sink] == float('inf')):
            #汇点的前驱还是初始值,说明已无增广路径
            return -1
        else:
            return flow[sink]
    
    def maxflow(source,sink):
        sumflow = 0#记录最大流,一直累加
        augmentflow = 0#当前寻找到的增广路径的最小通过流量
        while(True):
            augmentflow = BFS(source,sink)
            if(augmentflow == -1):
                break#返回-1说明已没有增广路径
            k = sink
            while(k!=source):#k回溯到起点,停止
                prev = pre[k]#走的方向是从prev到k
                maxflowgraph[prev][k] += augmentflow
                residual[prev][k] -= augmentflow#前进方向消耗掉了
                residual[k][prev] += augmentflow#反向边
                k = prev
            sumflow += augmentflow
        return sumflow
    
    result = maxflow(0,m-1)    
    print(result)
    print(maxflowgraph)#最大流图
    

    五、实验结果分析
    实验结果

    展开全文
  • matlab中最大流代码Holte和Talley混合层深度算法 这是中概述的混合层深度算法的python端口。 安装 要从pypi存储库安装: pip install holteandtalley 如果您想从源代码安装它以进行更改: #run this in the cloned ...
  • 0.测试数据 1.PushRelabel '''MaxflowGraph.py''' class MFGraph(object): def __init__(self): self.vertexnum = 0 self.edgenum = 0 self.origin = None self.destn = None ... self.VertexSet = {} #key:...

    0.测试数据

    1.PushRelabel

    '''MaxflowGraph.py'''
    class MFGraph(object):
        
        def __init__(self):    
            self.vertexnum = 0
            self.edgenum = 0
            
            self.origin = None
            self.destn = None
    
            self.VertexSet = {} #key:vertex's name; value:a list with height and excess
            self.EdgeSet = {}   #key:edge; value:a list with edge's residual capacity and flow
            self.EdgeSet_f = {} #key:edge which is in the residual network; value: residual capacity 
            self.Adjacents_f = {} 
    
            self.ExcessSet = []
    
        def generate_graph(self,v1,v2,capacity):
    
            self.VertexSet.setdefault(v1, [0, 0])
            self.VertexSet.setdefault(v2, [0, 0])
    
            self.EdgeSet.setdefault((v1,v2),[0, capacity])
            
            self.EdgeSet_f.setdefault((v1,v2), capacity)
            self.EdgeSet_f.setdefault((v2,v1), 0)
    
            if not v1 in self.Adjacents_f.keys():
                self.Adjacents_f[v1] = [v2]
            else:
                self.Adjacents_f[v1].append(v2)
                
            if not v2 in self.Adjacents_f.keys():
                self.Adjacents_f[v2] = [v1]
            else:
                self.Adjacents_f[v2].append(v1)
    
    
    '''Maxflow_pushrelabel.py'''
    import string
    from  MaxflowGraph import *
    
    def maxflow():
        G = initial_graph()
        create_preflow(G)
    
        while G.ExcessSet:
            #determine whether applicable push operation
            excess_u = G.ExcessSet.pop()
            
            while G.VertexSet[excess_u][1]>0:
                ispush = 0
                for u_adj in G.Adjacents_f[excess_u]: 
                    if (G.EdgeSet_f[(excess_u,u_adj)] > 0) \
                        and (G.VertexSet[excess_u][0] == G.VertexSet[u_adj][0]+1):     
                        push(G,excess_u,u_adj)
                        ispush = 1
    
                if ispush == 0:
                    relabel(G,excess_u)
        
        #print(G.EdgeSet)
        #print(G.VertexSet[G.origin])
        print(G.VertexSet[G.destn][1])
    
    def push(G,excess_u,u_adj):
        push_flow = min(G.VertexSet[excess_u][1], G.EdgeSet_f[(excess_u,u_adj)]) 
        
        if (excess_u, u_adj) in G.EdgeSet.keys():
            G.EdgeSet[excess_u, u_adj][0] += push_flow #e.f += push_flow
        else:
            G.EdgeSet[u_adj,excess_u][0] -= push_flow #e.f -= push_flow
    
        #f->residual network
        G.EdgeSet_f[(excess_u, u_adj)] -=push_flow  
        G.EdgeSet_f[(u_adj, excess_u)] +=push_flow
        
        G.VertexSet[excess_u][1] -= push_flow #u.excess -= push_flow
        G.VertexSet[u_adj][1] += push_flow #adj.excess += push_flow
        
        if (u_adj!=G.origin)and(u_adj!=G.destn)and(not u_adj in G.ExcessSet):
            G.ExcessSet.append(u_adj)
        
    def relabel(G,excess_u):
        #for all adj, h(u)<= h(adj)
        index = 0
        temp_v = G.Adjacents_f[excess_u][index]
        while G.EdgeSet_f[(excess_u, temp_v)] == 0:
            index += 1
            temp_v = G.Adjacents_f[excess_u][index]
        temp_h = G.VertexSet[temp_v][0]
    
        for u_adj in G.Adjacents_f[excess_u]:
            if (G.EdgeSet_f[(excess_u, u_adj)]>0) and (G.VertexSet[u_adj][0]<temp_h):
                temp_v = u_adj
                temp_h = G.VertexSet[u_adj][0]
    
        G.VertexSet[excess_u][0] = temp_h+1
    
    
    def create_preflow(G):
        #initialize height function
        G.VertexSet[G.origin][0] = G.vertexnum #set origin's height 
        for adj in G.Adjacents_f[G.origin]:
            if (G.origin, adj) in G.EdgeSet.keys():
                e_capacity = G.EdgeSet[(G.origin, adj)][1]
    
                G.EdgeSet[(G.origin, adj)][0] = e_capacity  #e.flow = e.capacity
                G.VertexSet[adj][1] = e_capacity  #adj.excess = e.capacity
                
                if adj != G.destn:
                    G.ExcessSet.append(adj)
    
                G.VertexSet[G.origin][1] -= e_capacity
    
                #f->residual network
                G.EdgeSet_f[(G.origin, adj)] = 0
                G.EdgeSet_f[(adj, G.origin)] = e_capacity
            
            
    def initial_graph():
        Graph = MFGraph()
    
        with open('test-3.txt','r') as f:
            Graph.vertexnum = int(f.readline().strip())
            Graph.edgenum = int(f.readline().strip())
    
            for i,line in enumerate(f.readlines()):
                if i == Graph.edgenum:
                    Graph.origin, Graph.destn = line.strip().split()
                else:
                    v1,v2,c = line.strip().split()
                    Graph.generate_graph(str(v1),str(v2),int(c))
        
        return Graph 
    
    
    if  __name__ == "__main__":
       maxflow()  
    
    展开全文
  • 文章目录基本概念图邻接矩阵最大流问题python解决最大流问题 基本概念 图 定义: 图G(V,E)是指一个二元组(V(G),E(G)),其中: V(G)={v1,v2,…, vn}是非空有限集,称为顶点集, E(G)是V(G)中的元素对(vi,vj)...


    喜欢的话请关注我们的微信公众号~《你好世界炼丹师》。

    • 公众号主要讲统计学,数据科学,机器学习,深度学习,以及一些参加Kaggle竞赛的经验。
    • 公众号内容建议作为课后的一些相关知识的补充,饭后甜点。
    • 此外,为了不过多打扰,公众号每周推送一次,每次4~6篇精选文章。

    微信搜索公众号:你好世界炼丹师。期待您的关注。


    基本概念

    定义: 图G(V,E)是指一个二元组(V(G),E(G)),其中:

    1. V(G)={v1,v2,…, vn}是非空有限集,称为顶点集,
    2. E(G)是V(G)中的元素对(vi,vj)组成的集合称为边集。

    举例:
    在这里插入图片描述
    V(G)={v1,v2,v3,v4}
    E(G)= {e1,e2,e3,e4,e5,e6}


    • 若图G的边是有方向的,称G是有向图,有向图的边称为有向边或弧
    • 与同一条边关联的两个端点称为相邻的顶点
    • 与同一个顶点关联的两条边称为相邻的边
    • 端点重合为一点的边称为
    • 若一对顶点之间有两条以上的边联结,则这些边称为重边
    • 既没有环也没有重边的图,称为简单图
    • 若图G的每一条边e 都赋以一个实数w(e),称w(e)为边e的, G连同边上的权称为赋权图 ,
    • 图G的中顶点的个数, 称为图G的阶
    • 图中与某个顶点相关联的边的数目,称为该顶点的度
    • 完全图:若无向图的任意两个顶点之间都存在着一条边,称此图为完全图。

    邻接矩阵

    • 以下均假设图为简单图,没有重边和环
    • 图G的邻接矩阵是表示顶点之间相邻关系的矩阵
      在这里插入图片描述

    举个例子:
    在这里插入图片描述
    在这里插入图片描述


    最大流问题

    • 设G(V,E)为有向图,若在每条边e上定义一个非负权c, 则称图G为一个网络,称c为边e的容量函数,记为c(e)。

    • 若在有向图G(V,E)中有两个不同的顶点vs与vt ,
      若顶点vs只有出度没有入度,称vs为图G的

    • 若顶点vt只有入度没有出度, 称vt为G的

    • 若顶点v 既不是源也不是汇, 称为v中间顶点


    在这里插入图片描述如图,就是从v1到v9怎么流动,在受每一个有向边的流动最大限制下,才是最大流。大学考试的内容一般都是用手算的,这里我们还是用python来解决最大流问题。

    python解决最大流问题

    在这里插入图片描述

    from ortools.graph import pywrapgraph
    start_nodes = [0, 0, 0, 1, 1, 2, 2, 3, 3]
    end_nodes = [1, 2, 3, 2, 4, 3, 4, 2, 4]
    capacities = [20, 30, 10, 40, 30, 10, 20, 5, 20]
    max_flow = pywrapgraph.SimpleMaxFlow()
    for i in range(0, len(start_nodes)):
        max_flow.AddArcWithCapacity(start_nodes[i], end_nodes[i], capacities[i])
    # Find the maximum flow between node 0 and node 4.
    if max_flow.Solve(0, 4) == max_flow.OPTIMAL:
        print('Max flow:', max_flow.OptimalFlow())
        print('')
        print('  Arc    Flow / Capacity')
        for i in range(max_flow.NumArcs()):
            print('%1s -> %1s   %3s  / %3s' % (
              max_flow.Tail(i),
              max_flow.Head(i),
              max_flow.Flow(i),
              max_flow.Capacity(i)))
        print('Source side min-cut:', max_flow.GetSourceSideMinCut())
        print('Sink side min-cut:', max_flow.GetSinkSideMinCut())
    else:
        print('There was an issue with the max flow input.')
    

    运行结果如下:
    在这里插入图片描述

    python解决最大流最小费用问题

    跟最大流问题类似,但是每一条边多了一个费用的概念
    在这里插入图片描述

    • 从图中可以看到,0点生产了20个货物,然后要送5个到3,15个到4
    • 一条边(15,4)意味着这个最多可以运输15个货物,每运输一个货物就要支付4点费用
    
    from ortools.graph import pywrapgraph
    #between each pair. For instance, the arc from node 0 to node 1 has acapacity of 15 and a unit cost of 4.
    start_nodes = [ 0, 0,  1, 1,  1,  2, 2,  3, 4]
    end_nodes   = [ 1, 2,  2, 3,  4,  3, 4,  4, 2]
    capacities  = [15, 8, 20, 4, 10, 15, 4, 20, 5]
    unit_costs  = [ 4, 4,  2, 2,  6,  1, 3,  2, 3]
    # Define an array of supplies at each node.
    supplies = [20, 0, 0, -5, -15]
    # Instantiate a SimpleMinCostFlow solver.
    min_cost_flow = pywrapgraph.SimpleMinCostFlow()
    # Add each arc.
    for i in range(0, len(start_nodes)):
        min_cost_flow.AddArcWithCapacityAndUnitCost(start_nodes[i], end_nodes[i],
                                                    capacities[i], unit_costs[i])
    # Add node supplies.
    for i in range(0, len(supplies)):
        min_cost_flow.SetNodeSupply(i, supplies[i])
     # Find the minimum cost flow between node 0 and node 4.
    if min_cost_flow.Solve() == min_cost_flow.OPTIMAL:
        print('Minimum cost:', min_cost_flow.OptimalCost())
        print('')
        print('  Arc    Flow / Capacity  Cost')
        for i in range(min_cost_flow.NumArcs()):
          cost = min_cost_flow.Flow(i) * min_cost_flow.UnitCost(i)
          print('%1s -> %1s   %3s  / %3s       %3s' % (
              min_cost_flow.Tail(i),
              min_cost_flow.Head(i),
              min_cost_flow.Flow(i),
              min_cost_flow.Capacity(i),
              cost))
    else:
        print('There was an issue with the min cost flow input.')
        
    

    运行结果:
    在这里插入图片描述
    参考:
    ortool 官网

    展开全文
  • 跑网上的python代码需要调用最大流算法,但是发现通过pip3.7 install maxflow无法安装 最后看了下能跑通的环境,发现需要安装的是PyMaxFlow库 直接在终端中(我的是python3.7版本) pip3.7 install PymaxFlow 即可安装...
  • EK代码如下: import time start_1=time.time() edgeLinks=dict()#边 edgeWeight=dict()#权重 stack_bfs_i=[]# ...SUB=[]#MIN的集合,最后相加即最大流 def BFS(start,end): global edgeLinks,edgeWeight,ju b
  • 测试用例的第一行为图的节点数和边数,第二行为最大流算法的起始节点和中止节点,剩余所有行均为有向加权边,其中前两个数字代表边的两个端点,后一个数字代表边的权重。 ·测试用例1(将txt压缩为xz后使用base16384...
  • 最大流问题 (使用遗传算法解决 Python 实现)Generate_matrix def Generate_matrix(x,y): import numpy as np import random return np.ceil(np.array([random.random()*10 for i in range(x*y)]).reshape(x,y))...
  • 测试用例的第一行为图的节点数和边数,第二行为最大流算法的起始节点和中止节点,剩余所有行均为有向加权边,其中前两个数字代表边的两个端点,后一个数字代表边的权重。 ·测试用例1(将txt压缩为xz后使用base16384...
  • [0,4,6,M,M], #最大流 7 完全正常 [M,0,2,3,M], [M,0,0,M,4], [M,M,0,0,5], [M,0,M,0,0]] s=0 # s为源点 t=4 # t为汇点 GF=copy.deepcopy(max_flow(capacity, s,t)) # for i in range(len(GF)): ## 输出残差图 # ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 503
精华内容 201
关键字:

最大流python

python 订阅