1. Toy模板网首页
  2. > Toy博客

【运筹优化】网络最大流问题及三种求解算法详解 + Python代码实现

9月前 作者：WSKH0929 分类：Toy博客 阅读(53) 违法举报

这篇具有很好参考价值的文章主要介绍了【运筹优化】网络最大流问题及三种求解算法详解 + Python代码实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

标题中时间复杂度用到的符号说明：f 代表最大流的大小，m代表边的数量，n 代表节点的数量
本博客学习自：B站-ShusenWang

一、网络最大流问题

最大流问题，是网络流理论研究的一个基本问题，求网络中一个可行流 f ∗ f* f∗，使其流量 v ( f ) v(f) v(f)达到最大， 这种流 f f f 称为最大流，这个问题称为 (网络)最大流问题。

最大流问题是一个特殊的线性规划问题，就是在容量网络中，寻找流量最大的可行流。

下面我们用一个例子来直观理解网络最大流问题

如下图所示，S处是一个水源，图中的弧是水管，管道由于材质、直径的不同，其所能承受的输水量也不同，所以就出现了下图所示的不同数值的弧，我们的目标是将水源从 S 通过管道运输到 T 点，且在满足管道能承受的输水量的前提下尽可能使得输送到 T 点的水最大化。

这就是最大流问题。

网络最大流问题例题详解,# 运筹优化,人工智能,算法,python,最大流问题,人工智能,图论

二、Ford-Fulkerson 算法（最坏时间复杂度：O(f×m)）

2.1 残存网络

残存网络其实就是用边的剩余容量来表示每条边，如下图所示的残存网络。S->v2这条边上的数字“2”代表这条边剩余可通过容量为2。

实际写代码只用残存网络即可求出最大流

网络最大流问题例题详解,# 运筹优化,人工智能,算法,python,最大流问题,人工智能,图论

2.2 增广路径

一条能从起点S到达起点T的流量大于0的路径就被称为增广路径，通过增广路径，流量一定会增加。

网络最大流问题例题详解,# 运筹优化,人工智能,算法,python,最大流问题,人工智能,图论

2.3 算法介绍

该算法概况起来，就是在残存网络中不断寻找增广路径，每找到一条增广路径，就递增最大流 f f f，并更新残存网络，直到残存网络中不存在增广路径，则此时f即为最终的最大流。

Ford-Fulkerson 算法是通过 DFS（深度优先遍历）的方式在当前残存网络中寻找增广路径的。

根据木桶原理，增广路径的流量等于该路径的边的最小剩余流量。如下图所示的增广路径，它的流量就是3，因为 v4->t 的容量为3

网络最大流问题例题详解,# 运筹优化,人工智能,算法,python,最大流问题,人工智能,图论
在找到增广路径后，我们要更新残存网络。首先就是对该增广路径的正向边进行更新，将正向边的剩余流量全部减去3

网络最大流问题例题详解,# 运筹优化,人工智能,算法,python,最大流问题,人工智能,图论
网络最大流问题例题详解,# 运筹优化,人工智能,算法,python,最大流问题,人工智能,图论

然后对该增广路径的反向边进行更新（反向边在初始化的时候，剩余流量都为0，所以在上面的图中没有画出来，反向边的作用就是让算法可以反悔，从而通过多次迭代，找到最优解），反向边的剩余流量全部加上3

网络最大流问题例题详解,# 运筹优化,人工智能,算法,python,最大流问题,人工智能,图论
添加反向边是这一算法能够精确求解最大流问题的基础保障

然后重复上述过程，直到找不到增广路径，算法结束

Ford-Fulkerson 算法的整体实现思路如下，其实就是不断从残存网络寻找增广路径的过程

网络最大流问题例题详解,# 运筹优化,人工智能,算法,python,最大流问题,人工智能,图论

2.4 完整代码

完整代码

# -*- coding: utf-8 -*-#
# Author: WSKH
# Blog: wskh0929.blog.csdn.net
# Time: 2023/2/13 9:45
# Description: Ford Fulkerson 算法求解最大流问题

class Node:
    def __init__(self, name, arc_dict):
        self.name = name
        self.arc_dict = arc_dict


def create_node(name, next_list, flow_list):
    arc_dict = {}
    for i in range(len(next_list)):
        arc_dict[next_list[i]] = flow_list[i]
    return Node(name, arc_dict)


def Ford_Fulkerson_Solve(s, e, node_list, name_index_dict):
    '''
    Ford_Fulkerson 算法核心函数
    :param s: 起始节点名称
    :param e: 终止节点名称
    :param node_list: 节点列表
    :param name_index_dict: 节点名字和索引字典
    :return: 返回搜索到的所有增广路径及其流值
    '''
    routes = []
    while True:
        res = dfs(e, [s], None, node_list, name_index_dict)
        if res is None:
            return routes
        # 追加增广路径到routes
        routes.append(res)
        # 更新node_list
        route, flow = res
        for i in range(len(route) - 1):
            n1 = node_list[name_index_dict[route[i]]]
            n2 = node_list[name_index_dict[route[i + 1]]]
            # 正向更新 n1 -> n2 剩余流量减少
            if n2.name in n1.arc_dict.keys() and n1.arc_dict[n2.name] is not None:
                n1.arc_dict[n2.name] = n1.arc_dict[n2.name] - flow
            # 反向更新 n2 -> n1 剩余流量增加
            if n1.name in n2.arc_dict.keys() and n2.arc_dict[n1.name] is not None:
                n2.arc_dict[n1.name] = n2.arc_dict[n1.name] + flow


def dfs(e, cur_route, last_flow, node_list, name_index_dict):
    '''
    DFS搜索增广路径
    :param e: 终点节点名称
    :param cur_route: 当前路径
    :param last_flow: 上一个节点的流值，用来计算最小流
    :param node_list: 节点列表
    :param name_index_dict: 节点名字和索引字典
    :return: 返回搜索到的增广路径及其流值，如果没找到就返回 None
    '''
    if cur_route[-1] == e:
        return cur_route, last_flow
    index = name_index_dict[cur_route[-1]]
    for next_node_name in node_list[index].arc_dict.keys():
        if next_node_name not in cur_route:
            flow = node_list[index].arc_dict[next_node_name]
            if flow is None or flow > 0:
                cur_route.append(next_node_name)
                res = dfs(e, cur_route, min_flow(last_flow, flow), node_list, name_index_dict)
                if res is not None:
                    return res
                cur_route.pop(-1)


def min_flow(f1, f2):
    '''
    求两个流量的较小者
    '''
    if f1 is None:
        return f2
    elif f2 is None:
        return f1
    else:
        return min(f1, f2)


if __name__ == '__main__':
    # 格式: [节点名, 后继节点的名称, 当前节点到各个后继的流量] （None 代表流量无穷大）
    graph = [
        ["S", ["1", "2", "3"], [None, None, None]],
        ["1", ["4"], [1]],
        ["2", ["4", "6"], [1, 1]],
        ["3", ["5"], [1]],
        ["4", ["1", "2", "E"], [0, 0, 1]],
        ["5", ["3", "E"], [0, 1]],
        ["6", ["2", "E"], [0, 1]],
        ["E", [], []]
    ]
    name_index_dict = dict()
    node_list = []
    for i in range(len(graph)):
        node_list.append(create_node(graph[i][0], graph[i][1], graph[i][2]))
        name_index_dict[graph[i][0]] = i

    # 调用算法求解最大流
    routes = Ford_Fulkerson_Solve("S", "E", node_list, name_index_dict)
    for i, (route, flow) in enumerate(routes):
        print(f"Route-{i + 1}: {route} , flow: {flow}")

测试案例

网络最大流问题例题详解,# 运筹优化,人工智能,算法,python,最大流问题,人工智能,图论

程序输出

Route-1: ['S', '1', '4', 'E'] , flow: 1
Route-2: ['S', '2', '6', 'E'] , flow: 1
Route-3: ['S', '3', '5', 'E'] , flow: 1

三、Edmons-Karp 算法（最坏时间复杂度：O(m×m×n)）

3.1 算法介绍

Edmons-Karp 算法比 Ford-Fulkerson 算法晚16年提出，它和 Ford-Fulkerson 算法唯一的区别在于寻找增广路径的方式不同，其余步骤完全一样。Edmons-Karp 算法在寻找增广路的时候是将残存网络看作一个无权图然后求S到T的最短路，这条最短路上的最小剩余流量如果大于0，那么就作为增广路径，进行残存网络的更新。

网络最大流问题例题详解,# 运筹优化,人工智能,算法,python,最大流问题,人工智能,图论

Edmons-Karp 算法贡献在于，它具有比 Ford-Fulkerson 算法更小的时间复杂度，Ford-Fulkerson 算法的时间复杂度受最大流大小影响，而 Edmons-Karp 算法只受节点数量和边的数量的影响

3.2 完整代码

本代码使用 BFS（广度优先搜索） 求最短路，测试案例还是和上面的一样

# -*- coding: utf-8 -*-#
# Author: WSKH
# Blog: wskh0929.blog.csdn.net
# Time: 2023/2/13 11:54
# Description: Edmons Karp 算法求解最大流问题

from queue import PriorityQueue


class Node:
    def __init__(self, name, arc_dict):
        self.name = name
        self.arc_dict = arc_dict


class Label:
    def __init__(self, route, last_flow):
        self.route = route
        self.last_flow = last_flow

    def __lt__(self, o):
        if len(self.route) == len(o.route):
            return 0
        else:
            return 1 if len(self.route) > len(o.route) else -1


def create_node(name, next_list, flow_list):
    arc_dict = {}
    for i in range(len(next_list)):
        arc_dict[next_list[i]] = flow_list[i]
    return Node(name, arc_dict)


def Edmons_Karp_Solve(s, e, node_list, name_index_dict):
    '''
    Edmons Karp 算法核心函数
    :param s: 起始节点名称
    :param e: 终止节点名称
    :param node_list: 节点列表
    :param name_index_dict: 节点名字和索引字典
    :return: 返回搜索到的所有增广路径及其流值
    '''
    routes = []
    while True:
        res = bfs(s, e, node_list, name_index_dict)
        if res is None:
            return routes
        # 追加增广路径到routes
        routes.append([res.route, res.last_flow])
        # 更新node_list
        route, flow = res.route, res.last_flow
        for i in range(len(route) - 1):
            n1 = node_list[name_index_dict[route[i]]]
            n2 = node_list[name_index_dict[route[i + 1]]]
            # 正向更新 n1 -> n2 剩余流量减少
            if n2.name in n1.arc_dict.keys() and n1.arc_dict[n2.name] is not None:
                n1.arc_dict[n2.name] = n1.arc_dict[n2.name] - flow
            # 反向更新 n2 -> n1 剩余流量增加
            if n1.name in n2.arc_dict.keys() and n2.arc_dict[n1.name] is not None:
                n2.arc_dict[n1.name] = n2.arc_dict[n1.name] + flow


def bfs(s, e, node_list, name_index_dict):
    queue = PriorityQueue()
    queue.put(Label([s], None))
    while queue.empty() is False:
        res = queue.get()
        index = name_index_dict[res.route[-1]]
        for next_node_name in node_list[index].arc_dict.keys():
            if next_node_name not in res.route:
                flow = node_list[index].arc_dict[next_node_name]
                if flow is None or flow > 0:
                    route = res.route.copy()
                    route.append(next_node_name)
                    if next_node_name == e:
                        return Label(route, min_flow(res.last_flow, flow))
                    queue.put(Label(route, min_flow(res.last_flow, flow)))


def min_flow(f1, f2):
    '''
    求两个流量的较小者
    '''
    if f1 is None:
        return f2
    elif f2 is None:
        return f1
    else:
        return min(f1, f2)


if __name__ == '__main__':
    # 格式: [节点名, 后继节点的名称, 当前节点到各个后继的流量] （None 代表流量无穷大）
    graph = [
        ["S", ["1", "2", "3"], [None, None, None]],
        ["1", ["4"], [1]],
        ["2", ["4", "6"], [1, 1]],
        ["3", ["5"], [1]],
        ["4", ["1", "2", "E"], [0, 0, 1]],
        ["5", ["3", "E"], [0, 1]],
        ["6", ["2", "E"], [0, 1]],
        ["E", [], []]
    ]
    name_index_dict = dict()
    node_list = []
    for i in range(len(graph)):
        node_list.append(create_node(graph[i][0], graph[i][1], graph[i][2]))
        name_index_dict[graph[i][0]] = i

    # 调用算法求解最大流
    routes = Edmons_Karp_Solve("S", "E", node_list, name_index_dict)
    for i, (route, flow) in enumerate(routes):
        print(f"Route-{i + 1}: {route} , flow: {flow}")

程序输出

Route-1: ['S', '1', '4', 'E'] , flow: 1
Route-2: ['S', '2', '6', 'E'] , flow: 1
Route-3: ['S', '3', '5', 'E'] , flow: 1

四、Dinic 算法（最坏时间复杂度：O(m×n×n)）

由于边的数量 m 通常远远大于节点数量 n，所以通常情况下 Dinic 算法比 Edmons-Karp 算法更快。而且 Dinic 算法发表时间比 Edmons-Karp 算法还要早两年。

为了更好的讲解 Dinic 算法，下面先介绍一个重要的概念 Level Graph

4.1 Level Graph

Level Graph 是原图的一个子图，保留了原图中的所有节点和一部分边，下面图解 Level Graph 的构造过程

首先，将 S 作为 Level Graph 的第零层

网络最大流问题例题详解,# 运筹优化,人工智能,算法,python,最大流问题,人工智能,图论

然后，从 S 出发，可以到达的点有 v2，将 v2 加入 Level Graph，记作第一层 ，保留第零层到第一层的边

网络最大流问题例题详解,# 运筹优化,人工智能,算法,python,最大流问题,人工智能,图论

看一下右边的原图，从第一层可以到达的节点有 S 和 v4，由于 S 已经在 Level Graph 中了，所以不考虑。将 v4 加入 Level Graph，记作第二层，保留第一层到第二层的边。

网络最大流问题例题详解,# 运筹优化,人工智能,算法,python,最大流问题,人工智能,图论

看一下右边的原图，从第二层可以到达的节点有 v1、v2和v3，由于 v2 已经在 Level Graph中了，所以只考虑 v1和v3，将它们加入 Level Graph，记作第三层，保留第二层到第三层的边

网络最大流问题例题详解,# 运筹优化,人工智能,算法,python,最大流问题,人工智能,图论

看一下右边的原图，从第三层可以到达所有节点，由于目前只剩下节点 t 没有加入 Level Graph，所以将 t 加入 Level Graph，记作第四层，保留第三层到第四层的边。

网络最大流问题例题详解,# 运筹优化,人工智能,算法,python,最大流问题,人工智能,图论

至此，原图的 Level Graph 构造完毕！Level Graph 中节点的层数代表着从起点到达该起点所需要的最少步数（其实就是无权图下的最短路），这么看来，Dinic 算法其实结合了 Ford-Filkerson 和 Edmons-Karp 两个算法的思想呀！

4.2 算法介绍

介绍完 Level Graph，下面开始正式介绍 Dinic 算法！

网络最大流问题例题详解,# 运筹优化,人工智能,算法,python,最大流问题,人工智能,图论

4.3 完整代码

# -*- coding: utf-8 -*-#
# Author: WSKH
# Blog: wskh0929.blog.csdn.net
# Time: 2023/2/13 19:26
# Description: Dinic 算法求解最大流问题
import numpy as np


class Node:
    def __init__(self, name, arc_dict):
        self.name = name
        self.arc_dict = arc_dict


def create_node(name, next_list, flow_list):
    arc_dict = {}
    for i in range(len(next_list)):
        arc_dict[next_list[i]] = flow_list[i]
    return Node(name, arc_dict)


def create_level_graph(s, e, node_list, name_index_dict):
    level_graph = np.zeros((len(node_list), len(node_list))).tolist()
    cur_layer = [s]
    all_node = set()
    all_node.add(s)
    next_layer = set()
    while len(cur_layer) > 0:
        for node_name in cur_layer:
            node = node_list[name_index_dict[node_name]]
            for key in node.arc_dict.keys():
                if key not in all_node and (node.arc_dict[key] is None or node.arc_dict[key] > 0):
                    level_graph[name_index_dict[node_name]][name_index_dict[key]] = node.arc_dict[key]
                    next_layer.add(key)
                    all_node.add(key)
        cur_layer = list(next_layer)
        next_layer = set()
    return level_graph if e in all_node else None


def Dinic_Solve(s, e, node_list, name_index_dict):
    routes = []
    s_index = name_index_dict[s]
    e_index = name_index_dict[e]
    level_graph = create_level_graph(s, e, node_list, name_index_dict)
    while level_graph is not None:
        res_list = []
        while True:
            res = dfs(e_index, [s_index], None, level_graph)
            if res is None:
                break
            # 更新 level graph
            route, flow = res
            for i in range(len(route) - 1):
                if level_graph[route[i]][route[i + 1]] is not None:
                    level_graph[route[i]][route[i + 1]] -= flow
            # 追加记录增广路径
            res_list.append(res)
            routes.append([[node_list[n].name for n in res[0]], res[1]])
        # 更新残存网络
        for res in res_list:
            update(res, node_list)
        # 重新构造 level graph
        level_graph = create_level_graph(s, e, node_list, name_index_dict)
    return routes


def update(res, node_list):
    route, flow = res
    for i in range(len(route) - 1):
        n1 = node_list[route[i]]
        n2 = node_list[route[i + 1]]
        # 正向更新 n1 -> n2 剩余流量减少
        if n2.name in n1.arc_dict.keys() and n1.arc_dict[n2.name] is not None:
            n1.arc_dict[n2.name] = n1.arc_dict[n2.name] - flow
        # 反向更新 n2 -> n1 剩余流量增加
        if n1.name in n2.arc_dict.keys() and n2.arc_dict[n1.name] is not None:
            n2.arc_dict[n1.name] = n2.arc_dict[n1.name] + flow


def dfs(e_index, cur_route, last_flow, level_graph):
    if cur_route[-1] == e_index:
        return cur_route, last_flow
    for next_node in range(len(level_graph)):
        if next_node not in cur_route:
            if level_graph[cur_route[-1]][next_node] is None or level_graph[cur_route[-1]][next_node] > 0:
                flow = min_flow(level_graph[cur_route[-1]][next_node], last_flow)
                cur_route.append(next_node)
                res = dfs(e_index, cur_route, flow, level_graph)
                if res is not None:
                    return res
                cur_route.pop(-1)


def min_flow(f1, f2):
    '''
    求两个流量的较小者
    '''
    if f1 is None:
        return f2
    elif f2 is None:
        return f1
    else:
        return min(f1, f2)


if __name__ == '__main__':
    # 格式: [节点名, 后继节点的名称, 当前节点到各个后继的流量] （None 代表流量无穷大）
    graph = [
        ["S", ["1", "2", "3"], [None, None, None]],
        ["1", ["4"], [1]],
        ["2", ["4", "6"], [1, 1]],
        ["3", ["5"], [1]],
        ["4", ["1", "2", "E"], [0, 0, 1]],
        ["5", ["3", "E"], [0, 1]],
        ["6", ["2", "E"], [0, 1]],
        ["E", [], []]
    ]
    name_index_dict = dict()
    node_list = []
    for i in range(len(graph)):
        node_list.append(create_node(graph[i][0], graph[i][1], graph[i][2]))
        name_index_dict[graph[i][0]] = i

    # 调用算法求解最大流
    routes = Dinic_Solve("S", "E", node_list, name_index_dict)
    for i, (route, flow) in enumerate(routes):
        print(f"Route-{i + 1}: {route} , flow: {flow}")

程序输出

Route-1: ['S', '3', '5', 'E'] , flow: 1
Route-2: ['S', '1', '4', 'E'] , flow: 1
Route-3: ['S', '2', '6', 'E'] , flow: 1

五、三种算法的性能测试

本节测试所用的案例是随机案例，如下图所示，根据指定的 m 和 n，构造一个中间有两层节点的网络图

网络最大流问题例题详解,# 运筹优化,人工智能,算法,python,最大流问题,人工智能,图论

5.1 测试1

在测试1中，固定 m = 10，n 从 2 开始以 1 的步长一直自增到 20

网络最大流问题例题详解,# 运筹优化,人工智能,算法,python,最大流问题,人工智能,图论

5.2 测试2

在测试2中，固定 n = 10，m 从 2 开始以 1 的步长一直自增到 20

网络最大流问题例题详解,# 运筹优化,人工智能,算法,python,最大流问题,人工智能,图论文章来源地址https://www.toymoban.com/news/detail-782094.html

5.3 测试部分完整代码

# -*- coding: utf-8 -*-#
# Author: WSKH
# Blog: wskh0929.blog.csdn.net
# Time: 2023/2/13 15:23
# Description:

import time
import random

from matplotlib import pyplot as plt

plt.rcParams['font.sans-serif'] = ['SimHei']  # 用来正常显示中文标签
plt.rcParams['axes.unicode_minus'] = False  # 用来正常显示负号 #有中文出现的情况，需要u'内容'

from EdmonsKarp import Edmons_Karp_Solve
from FordFulkerson import Ford_Fulkerson_Solve
from Dinic import Dinic_Solve
from copy import deepcopy


class Node:
    def __init__(self, name, arc_dict):
        self.name = name
        self.arc_dict = arc_dict


def create_node(name, next_list, flow_list):
    arc_dict = {}
    for i in range(len(next_list)):
        arc_dict[next_list[i]] = flow_list[i]
    return Node(name, arc_dict)


def create_instance(m, n, seed=666):
    random.seed(seed)
    S = "S"
    E = "E"
    node_list = []
    name_index_dict = {}
    name_index_dict["S"] = 0
    name_index_dict["E"] = m + n + 1
    for i in range(m + n):
        name_index_dict[str(i + 1)] = i + 1
    # 构造起点
    node_list.append(create_node("S", [str(i + 1) for i in range(m)], [random.randint(800, 1200) for _ in range(m)]))
    # 构造第一层
    for i in range(m):
        node_list.append(
            create_node(str(i + 1), [str(i + j + 2) for j in range(n)], [random.randint(800, 1200) for _ in range(n)]))
    # 构造第二层
    for i in range(n):
        next_list = ["E"]
        flow_list = [random.randint(800, 1200)]
        for j in range(m):
            next_list.append(str(j + 1))
            flow_list.append(0)
        node_list.append(create_node(str(m + i + 1), next_list, flow_list))

    # 构造终点
    node_list.append(create_node("E", [], []))
    return S, E, node_list, name_index_dict


def test1():
    m = 10
    n_arr = [i for i in range(1, 21, 1)]
    time_dict = {
        "Ford-Fulkerson": [],
        "Edmons-Karp": [],
        "Dinic": []
    }
    for n in n_arr:
        instance = create_instance(m, n)

        S, E, node_list, name_index_dict = deepcopy(instance)
        start_time = time.time()
        Ford_Fulkerson_Solve(S, E, node_list, name_index_dict)
        time_dict["Ford-Fulkerson"].append(time.time() - start_time)

        S, E, node_list, name_index_dict = deepcopy(instance)
        start_time = time.time()
        Edmons_Karp_Solve(S, E, node_list, name_index_dict)
        time_dict["Edmons-Karp"].append(time.time() - start_time)

        S, E, node_list, name_index_dict = deepcopy(instance)
        start_time = time.time()
        Dinic_Solve(S, E, node_list, name_index_dict)
        time_dict["Dinic"].append(time.time() - start_time)
    plot(time_dict, n_arr, "固定m为10，n与运行时间的关系", "n")


def test2():
    n = 10
    m_arr = [i for i in range(1, 21, 1)]
    time_dict = {
        "Ford-Fulkerson": [],
        "Edmons-Karp": [],
        "Dinic": []
    }
    for m in m_arr:
        print(m)
        instance = create_instance(m, n)

        S, E, node_list, name_index_dict = deepcopy(instance)
        start_time = time.time()
        Ford_Fulkerson_Solve(S, E, node_list, name_index_dict)
        time_dict["Ford-Fulkerson"].append(time.time() - start_time)

        S, E, node_list, name_index_dict = deepcopy(instance)
        start_time = time.time()
        Edmons_Karp_Solve(S, E, node_list, name_index_dict)
        time_dict["Edmons-Karp"].append(time.time() - start_time)

        S, E, node_list, name_index_dict = deepcopy(instance)
        start_time = time.time()
        Dinic_Solve(S, E, node_list, name_index_dict)
        time_dict["Dinic"].append(time.time() - start_time)
    plot(time_dict, m_arr, "固定n为10，m与运行时间的关系", "m")


def plot(time_dict, arr, title, x_label):
    for key in time_dict.keys():
        plt.plot(arr, time_dict[key], marker=".", label=key)
    plt.legend()
    plt.xlabel(x_label)
    plt.ylabel("运行时间(s)")
    plt.title(title)
    plt.grid(True)
    plt.show()


if __name__ == '__main__':
    # test1()
    test2()

5.4 结论（仅供参考）

  • 当点的数量远大于边的数量时，采用 Edmons-Karp 算法
  • 否则采用 Ford-Filkerson 算法和 Dinic 算法（在我的测试中，这两种该算法性能差不多，不过 Dinic 算法看起来更加稳健一些，当然有条件的话最好都尝试一下）

到了这里，关于【运筹优化】网络最大流问题及三种求解算法详解 + Python代码实现的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 带约束条件的运筹规划问题求解（模拟退火算法实现）

    超级简单的模拟退火算法实现ε٩(๑ ₃ )۶з搭配最简单的线性规划模型进行讲解！但是如果需要的话，可以直接修改程序求解非线性问题哦(´つヮ⊂︎) [max,f(x)=10x_1+9x_2] (s.t.) [6x_1+5x_2leq{60}tag{1}] [10x_1+20x_2leq{150}tag{2}] [0leq{x_1}leq{8}tag{3}] [0leq{x_2}leq{8}tag{4}] 对约束

    2023年04月18日
    浏览(43)
  • 【运筹优化】带时间窗约束的车辆路径规划问题（VRPTW）详解 + Python 调用 Gurobi 建模求解

    【运筹优化】带时间窗约束的车辆路径规划问题（VRPTW）详解 + Python 调用 Gurobi 建模求解

    车辆路径规划问题(Vehicle Routing Problem，VRP)一般指的是：对一系列发货点和收货点，组织调用一定的车辆，安排适当的行车路线，使车辆有序地通过它们，在满足指定的约束条件下（例如：货物的需求量与发货量，交发货时间，车辆容量限制，行驶里程限制，行驶时间限制等）

    2024年02月02日
    浏览(49)
  • 【运筹优化】子集和问题（Subset Sum Problems , SSP）介绍 + 动态规划求解 + Java代码实现

    【运筹优化】子集和问题（Subset Sum Problems , SSP）介绍 + 动态规划求解 + Java代码实现

    子集和问题（Subset Sum Problems , SSP），它是复杂性理论中最重要的问题之一。 SSP会给定一组整数 a 1 , a 2 , . . . . , a n a_1,a_2,....,a_n a 1 ​ , a 2 ​ , .... , a n ​ ，最多 n n n 个整数，我们需要判断是否存在一个非空子集，使得子集的总和为 M M M 整数？如果存在则需要输出该子集。

    2024年01月17日
    浏览(46)
  • C# PSO 粒子群优化算法 遗传算法 随机算法 求解复杂方程的最大、最小值

    C# PSO 粒子群优化算法 遗传算法 随机算法 求解复杂方程的最大、最小值

    复杂方程可以自己定义，以下是看别人的题目，然后自己来做 以下是计算结果

    2024年02月09日
    浏览(42)
  • 软件工具 | Python调用运筹优化求解器（一）：以CVRP&VRPTW为例

    软件工具 | Python调用运筹优化求解器（一）：以CVRP&VRPTW为例

    欢迎关注个人微信公众号：Python助力交通 优化求解器是解决复杂工程问题不可或缺的工具，可以帮助我们验证模型的正确性、理解决策变量的耦合关系、获取最优决策方案（合适规模条件下）。小编搜罗了网上关于各类常见（其实并不常见）的优化求解器介绍的帖子： 优化

    2024年02月10日
    浏览(55)
  • 运筹系列82：使用动态规划求解TSP问题

    运筹系列82：使用动态规划求解TSP问题

    定义 c ( s , k ) c(s,k) c ( s , k ) 为当前在 k k k ，待访问点的集合 s s s ，最后返回城市0的最短路径，那么Bellman方程为： c ( s , k ) = min ⁡ i ∈ s { c ( s − { i } , i ) + d i , k } c(s,k)=min_{i in s}{c(s-{i},i)+d_{i,k}} c ( s , k ) = min i ∈ s ​ { c ( s − { i } , i ) + d i , k ​ } 为了使用方便，这里

    2024年02月06日
    浏览(38)
  • 运筹系列87：julia求解随机动态规划问题入门

    运筹系列87：julia求解随机动态规划问题入门

    随机动态规划问题的特点是： 有多个阶段，每个阶段的随机性互不相关，且有有限个实现值 (finite realizations) 具有马尔可夫性质，即每个阶段只受上一个阶段影响，可以用状态转移方程来描述阶段与阶段之间的变化过程。 我们使用julia的SDDP算法包来求解随机动态规划问题。

    2024年01月16日
    浏览(40)
  • 运筹说 第80期 | 最小费用最大流问题

    运筹说 第80期 | 最小费用最大流问题

    前面我们学习了图与网络分析的基础知识及经典问题，大家是否已经学会了呢？接下来小编和大家学习最后一个经典问题—— 最小费用最大流问题 。 最小费用最大流问题是经济学和管理学中的一类典型问题。在一个网络中每段路径都有“容量”和“费用”两个限制的条件下

    2024年01月16日
    浏览(41)
  • scipy求解约束无导数优化问题：SHGO算法

    scipy求解约束无导数优化问题：SHGO算法

    SHGO，即simplicial homology global optimize，来自2018年的文章，是一种基于组合拓扑学的优化方法，是一个非常新的算法。 这种算法适用于CDFO(constrained deriviate free optimisation)问题，所谓无导数优化，就是把目标函数当作黑箱子处理，而无法获取其一阶导数，自然也不能通过导数来判

    2024年02月14日
    浏览(46)
  • 模拟退火算法与遗传算法求解多目标优化问题的算法实现（数学建模）

    模拟退火算法与遗传算法求解多目标优化问题的算法实现（数学建模）

    模拟退火算法是一种全局优化算法，解决的问题通常是找到一个最小化（或最大化）某个函数的全局最优解。它通过模拟物理退火的过程来搜索解空间，在开始时以一定的温度随机生成初始解，然后一步步降低温度，同时在当前解的周围随机搜索新的解，并根据一定概率接受

    2024年02月02日
    浏览(52)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包