در این مطلب، روش حل مساله بیشینه جریان (Maximum Flow Problem) بیان و راهکار بیان شده برای آن در زبان‌های برنامهنویسی گوناگون شامل «سی‌پلاس‌پلاس» (++C)، «جاوا» (Java)، «پایتون» (Python) و «سی‌شارپ» (#C) پیاده‌سازی شده است. یک گراف داده شده که نشانگر یک «شبکه جریان» (Flow Network) است و در آن، هر «یال» (Edge) دارای ظرفیت است. همچنین، دو راس s (مبدا | Source) و t (مقصد | Sink) در گراف داده شده است. هدف پیدا کردن بیشینه جریان ممکنی است که از s به t با در نظر داشتن محدودیت‌های زیر، شکل می‌گیرد.
- جریان روی یک یال از ظرفیت داده شده روی آن یال سر ریز نمی‌کند.
- جریان ورودی برای هر راس، به جز s و t، مساوی با جریان خروجی است.
برای مثال، می‌توان گراف زیر را در نظر گرفت.
بیشینه جریان ممکن در گراف بالا برابر با ۲۳ است.
الگوریتم فورد–فالکرسون برای حل مساله بیشینه جریان
در ادامه، «الگوریتم فورد–فالکرسون» (Ford-Fulkerson Algorithm) برای حل مساله بیشینه جریان ارائه شده است.
- با جریان اولیه ۰ شروع کن.
- تا هنگامی که یک مسیر تجمعی از مبدا به مقصد وجود دارد، این «مسیر-جریان» (Path-Flow) را به «جریان» اضافه کن.
- جریان را بازگردان.
پیچیدگی زمانی الگوریتم بالا از درجه O(max_flow * E) است. هنگامی که یک مسیر تجمعی وجود داشته باشد، یک حلقه اجرا می‌شود. در بدترین حالت، ممکن است ۱ واحد جریان در هر تکرار اضافه شود. بنابراین، پیچیدگی زمانی برابر با O(max_flow * E) خواهد شد.
پیاده‌سازی الگوریتم ساده بالا
برای پیاده‌سازی الگوریتم بالا، ابتدا باید مفهوم «گراف باقیمانده» (Residual Graph) تعریف شود که برای درک این پیاده‌سازی مورد نیاز است. گراف باقیمانده از یک شبکه جریان، گرافی است که جریان اضافی ممکن را نشان می‌دهد. اگر مسیری از مبدا به مقصد وجود داشته باشد، این امکان وجود دارد که جریان اضافه شود. هر یال از گراف دارای مقداری است که به آن ظرفیت باقیمانده گفته می‌شود. ظرفیت باقیمانده برابر با ظرفیت اصلی یال‌ها منهای جریان کنونی است. ظرفیت باقیمانده اساسا ظرفیت کنونی یال‌ها است.
اکنون، پیرامون جزئیات پیاده‌سازی صحبت خواهد شد. اگر هیچ یالی بین دو راس از گراف باقیمانده وجود نداشته باشد، ظرفیت باقیمانده برابر با ۰ است. می‌توان با توجه به اینکه هیچ جریان اولیه‌ای وجود ندارد، به گراف باقیمانده مقداردهی اولیه کرد. همچنین، ظرفیت باقیمانده اولیه برابر با ظرفیت اصلی است. برای پیدا کردن مسیر تجمعی، می‌توان از الگوریتم «جستجوی اول سطح» (Breadth-First Search) یا «جستجوی اول عمق» (Depth-First Search) استفاده کرد. در پیاده‌سازی زیر، برای پیدا کردن مسیر تجمعی از BFS استفاده شده است.
با استفاده از BFS، می‌توان بررسی کرد که آیا مسیری از مبدا به مقصد وجود دارد یا خیر. همچنین، BFS، آرایه parent[] را می‌سازد. با استفاده از آرایه parent[]، پیمایش در مسیر یافته شده انجام و جریان احتمالی از طریق این مسیر با پیدا کردن ظرفیت باقیمانده در طول مسیر پیدا می‌شود. در ادامه، جریان مسیر یافت شده به جریان کلی اضافه می‌شود. نکته مهم آن است که به روز رسانی ظرفیت باقیمانده‌ها در گراف باقیمانده مورد نیاز است. جریان مسیر از همه یال‌ها در طول مسیر کسر می‌شود و جریان مسیر در امتداد یال‌های معکوس اضافه می‌شود. نیاز به اضافه کردن جریان مسیر در طول یال‌های معکوس است، زیرا ممکن است بعدا نیاز به ارسال جریان در جهت معکوس باشد.
حل مساله بیشینه جریان در ++C
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
|
// C++ program for implementation of Ford Fulkerson algorithm
#include <iostream>
#include <limits.h>
#include <string.h>
#include <queue>
using namespace std;
// Number of vertices in given graph
#define V 6
/* Returns true if there is a path from source 's' to sink 't' in
residual graph. Also fills parent[] to store the path */
bool bfs(int rGraph[V][V], int s, int t, int parent[])
{
// Create a visited array and mark all vertices as not visited
bool visited[V];
memset(visited, 0, sizeof(visited));
// Create a queue, enqueue source vertex and mark source vertex
// as visited
queue <int> q;
q.push(s);
visited[s] = true;
parent[s] = -1;
// Standard BFS Loop
while (!q.empty())
{
int u = q.front();
q.pop();
for (int v=0; v<V; v++)
{
if (visited[v]==false && rGraph[u][v] > 0)
{
q.push(v);
parent[v] = u;
visited[v] = true;
}
}
}
// If we reached sink in BFS starting from source, then return
// true, else false
return (visited[t] == true);
}
// Returns the maximum flow from s to t in the given graph
int fordFulkerson(int graph[V][V], int s, int t)
{
int u, v;
// Create a residual graph and fill the residual graph with
// given capacities in the original graph as residual capacities
// in residual graph
int rGraph[V][V]; // Residual graph where rGraph[i][j] indicates
// residual capacity of edge from i to j (if there
// is an edge. If rGraph[i][j] is 0, then there is not)
for (u = 0; u < V; u++)
for (v = 0; v < V; v++)
rGraph[u][v] = graph[u][v];
int parent[V]; // This array is filled by BFS and to store path
int max_flow = 0; // There is no flow initially
// Augment the flow while tere is path from source to sink
while (bfs(rGraph, s, t, parent))
{
// Find minimum residual capacity of the edges along the
// path filled by BFS. Or we can say find the maximum flow
// through the path found.
int path_flow = INT_MAX;
for (v=t; v!=s; v=parent[v])
{
u = parent[v];
path_flow = min(path_flow, rGraph[u][v]);
}
// update residual capacities of the edges and reverse edges
// along the path
for (v=t; v != s; v=parent[v])
{
u = parent[v];
rGraph[u][v] -= path_flow;
rGraph[v][u] += path_flow;
}
// Add path flow to overall flow
max_flow += path_flow;
}
// Return the overall flow
return max_flow;
}
// Driver program to test above functions
int main()
{
// Let us create a graph shown in the above example
int graph[V][V] = { {0, 16, 13, 0, 0, 0},
{0, 0, 10, 12, 0, 0},
{0, 4, 0, 0, 14, 0},
{0, 0, 9, 0, 0, 20},
{0, 0, 0, 7, 0, 4},
{0, 0, 0, 0, 0, 0}
};
cout << "The maximum possible flow is " << fordFulkerson(graph, 0, 5);
return 0;
}
|
حل مساله بیشینه جریان در جاوا
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
|
// Java program for implementation of Ford Fulkerson algorithm
import java.util.*;
import java.lang.*;
import java.io.*;
import java.util.LinkedList;
class MaxFlow
{
static final int V = 6; //Number of vertices in graph
/* Returns true if there is a path from source 's' to sink
't' in residual graph. Also fills parent[] to store the
path */
boolean bfs(int rGraph[][], int s, int t, int parent[])
{
// Create a visited array and mark all vertices as not
// visited
boolean visited[] = new boolean[V];
for(int i=0; i<V; ++i)
visited[i]=false;
// Create a queue, enqueue source vertex and mark
// source vertex as visited
LinkedList<Integer> queue = new LinkedList<Integer>();
queue.add(s);
visited[s] = true;
parent[s]=-1;
// Standard BFS Loop
while (queue.size()!=0)
{
int u = queue.poll();
for (int v=0; v<V; v++)
{
if (visited[v]==false && rGraph[u][v] > 0)
{
queue.add(v);
parent[v] = u;
visited[v] = true;
}
}
}
// If we reached sink in BFS starting from source, then
// return true, else false
return (visited[t] == true);
}
// Returns tne maximum flow from s to t in the given graph
int fordFulkerson(int graph[][], int s, int t)
{
int u, v;
// Create a residual graph and fill the residual graph
// with given capacities in the original graph as
// residual capacities in residual graph
// Residual graph where rGraph[i][j] indicates
// residual capacity of edge from i to j (if there
// is an edge. If rGraph[i][j] is 0, then there is
// not)
int rGraph[][] = new int[V][V];
for (u = 0; u < V; u++)
for (v = 0; v < V; v++)
rGraph[u][v] = graph[u][v];
// This array is filled by BFS and to store path
int parent[] = new int[V];
int max_flow = 0; // There is no flow initially
// Augment the flow while tere is path from source
// to sink
while (bfs(rGraph, s, t, parent))
{
// Find minimum residual capacity of the edhes
// along the path filled by BFS. Or we can say
// find the maximum flow through the path found.
int path_flow = Integer.MAX_VALUE;
for (v=t; v!=s; v=parent[v])
{
u = parent[v];
path_flow = Math.min(path_flow, rGraph[u][v]);
}
// update residual capacities of the edges and
// reverse edges along the path
for (v=t; v != s; v=parent[v])
{
u = parent[v];
rGraph[u][v] -= path_flow;
rGraph[v][u] += path_flow;
}
// Add path flow to overall flow
max_flow += path_flow;
}
// Return the overall flow
return max_flow;
}
// Driver program to test above functions
public static void main (String[] args) throws java.lang.Exception
{
// Let us create a graph shown in the above example
int graph[][] =new int[][] { {0, 16, 13, 0, 0, 0},
{0, 0, 10, 12, 0, 0},
{0, 4, 0, 0, 14, 0},
{0, 0, 9, 0, 0, 20},
{0, 0, 0, 7, 0, 4},
{0, 0, 0, 0, 0, 0}
};
MaxFlow m = new MaxFlow();
System.out.println("The maximum possible flow is " +
m.fordFulkerson(graph, 0, 5));
}
}
|
حل مساله بیشینه جریان در پایتون
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
|
# Python program for implementation of Ford Fulkerson algorithm
from collections import defaultdict
#This class represents a directed graph using adjacency matrix representation
class Graph:
def __init__(self,graph):
self.graph = graph # residual graph
self. ROW = len(graph)
#self.COL = len(gr[0])
'''Returns true if there is a path from source 's' to sink 't' in
residual graph. Also fills parent[] to store the path '''
def BFS(self,s, t, parent):
# Mark all the vertices as not visited
visited =[False]*(self.ROW)
# Create a queue for BFS
queue=[]
# Mark the source node as visited and enqueue it
queue.append(s)
visited[s] = True
# Standard BFS Loop
while queue:
#Dequeue a vertex from queue and print it
u = queue.pop(0)
# Get all adjacent vertices of the dequeued vertex u
# If a adjacent has not been visited, then mark it
# visited and enqueue it
for ind, val in enumerate(self.graph[u]):
if visited[ind] == False and val > 0 :
queue.append(ind)
visited[ind] = True
parent[ind] = u
# If we reached sink in BFS starting from source, then return
# true, else false
return True if visited[t] else False
# Returns tne maximum flow from s to t in the given graph
def FordFulkerson(self, source, sink):
# This array is filled by BFS and to store path
parent = [-1]*(self.ROW)
max_flow = 0 # There is no flow initially
# Augment the flow while there is path from source to sink
while self.BFS(source, sink, parent) :
# Find minimum residual capacity of the edges along the
# path filled by BFS. Or we can say find the maximum flow
# through the path found.
path_flow = float("Inf")
s = sink
while(s != source):
path_flow = min (path_flow, self.graph[parent[s]][s])
s = parent[s]
# Add path flow to overall flow
max_flow += path_flow
# update residual capacities of the edges and reverse edges
# along the path
v = sink
while(v != source):
u = parent[v]
self.graph[u][v] -= path_flow
self.graph[v][u] += path_flow
v = parent[v]
return max_flow
# Create a graph given in the above diagram
graph = [[0, 16, 13, 0, 0, 0],
[0, 0, 10, 12, 0, 0],
[0, 4, 0, 0, 14, 0],
[0, 0, 9, 0, 0, 20],
[0, 0, 0, 7, 0, 4],
[0, 0, 0, 0, 0, 0]]
g = Graph(graph)
source = 0; sink = 5
print ("The maximum possible flow is %d " % g.FordFulkerson(source, sink))
#This code is contributed by Neelam Yadav
|
حل مساله بیشینه جریان در #C
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
|
// C# program for implementation
// of Ford Fulkerson algorithm
using System;
using System.Collections.Generic;
public class MaxFlow
{
static readonly int V = 6; //Number of vertices in graph
/* Returns true if there is a path
from source 's' to sink 't' in residual
graph. Also fills parent[] to store the
path */
bool bfs(int [,]rGraph, int s, int t, int []parent)
{
// Create a visited array and mark
// all vertices as not visited
bool []visited = new bool[V];
for(int i = 0; i < V; ++i)
visited[i] = false;
// Create a queue, enqueue source vertex and mark
// source vertex as visited
List<int> queue = new List<int>();
queue.Add(s);
visited[s] = true;
parent[s] = -1;
// Standard BFS Loop
while (queue.Count != 0)
{
int u = queue[0];
queue.RemoveAt(0);
for (int v = 0; v < V; v++)
{
if (visited[v] == false && rGraph[u, v] > 0)
{
queue.Add(v);
parent[v] = u;
visited[v] = true;
}
}
}
// If we reached sink in BFS
// starting from source, then
// return true, else false
return (visited[t] == true);
}
// Returns tne maximum flow
// from s to t in the given graph
int fordFulkerson(int [,]graph, int s, int t)
{
int u, v;
// Create a residual graph and fill
// the residual graph with given
// capacities in the original graph as
// residual capacities in residual graph
// Residual graph where rGraph[i,j]
// indicates residual capacity of
// edge from i to j (if there is an
// edge. If rGraph[i,j] is 0, then
// there is not)
int [,]rGraph = new int[V, V];
for (u = 0; u < V; u++)
for (v = 0; v < V; v++)
rGraph[u, v] = graph[u, v];
// This array is filled by BFS and to store path
int []parent = new int[V];
int max_flow = 0; // There is no flow initially
// Augment the flow while tere is path from source
// to sink
while (bfs(rGraph, s, t, parent))
{
// Find minimum residual capacity of the edhes
// along the path filled by BFS. Or we can say
// find the maximum flow through the path found.
int path_flow = int.MaxValue;
for (v = t; v != s; v = parent[v])
{
u = parent[v];
path_flow = Math.Min(path_flow, rGraph[u,v]);
}
// update residual capacities of the edges and
// reverse edges along the path
for (v = t; v != s; v = parent[v])
{
u = parent[v];
rGraph[u,v] -= path_flow;
rGraph[v,u] += path_flow;
}
// Add path flow to overall flow
max_flow += path_flow;
}
// Return the overall flow
return max_flow;
}
// Driver code
public static void Main ()
{
// Let us create a graph shown in the above example
int [,]graph =new int[,] { {0, 16, 13, 0, 0, 0},
{0, 0, 10, 12, 0, 0},
{0, 4, 0, 0, 14, 0},
{0, 0, 9, 0, 0, 20},
{0, 0, 0, 7, 0, 4},
{0, 0, 0, 0, 0, 0}
};
MaxFlow m = new MaxFlow();
Console.WriteLine("The maximum possible flow is " +
m.fordFulkerson(graph, 0, 5));
}
}
/* This code contributed by PrinciRaj1992 */
|
The maximum possible flow is 23
پیاده‌سازی بالا از الگوریتم فورد–فالکرسون را «الگوریتم ادموندز کارپ» (Edmonds-Karp Algorithm) می‌گویند. ایده اصلی نهفته در پس استفاده از الگوریتم ادموندز کارپ، استفاده از BFS است؛ زیرا BFS همیشه مسیری با کمترین تعداد یال را انتخاب می‌کند.
هنگامی که BFS مورد استفاده قرار می‌گیرد، پیچیدگی زمانی بدترین حالت را می‌توان به O(VE2) کاهش داد. پیاده‌سازی بالا از ارائه ماتریس مجاورت استفاده می‌کند و BFS دارای پیچیدگی زمانی از درجه O(V2) است.
این مسأله با توجه به اینکه در بسیاری از موقعیت‌های عملی به وقوع می‌پیوندد، بسیار حائز است. از جمله مثال‌هایی برای مسأله بیشینه جریان می‌توان زد، افزایش حمل و نقل با توجه به محدودیت‌های ترافیکی داده شده و افزایش جریان بسته‌ها در شبکه‌های کامپیوتری است.
اگر نوشته بالا برای شما مفید بوده است، آموزشهای زیر نیز به شما پیشنهاد می‌شوند:
- مجموعه آموزشهای برنامهنویسی
- آموزش ساختمان داده‌ها
- مجموعه آموزشهای ساختمان داده و طراحی الگوریتم
- یافتن دور همیلتونی با الگوریتم پس گرد — به زبان ساده
- الگوریتم بازی مار و پله همراه با کد — به زبان ساده
- حل مساله n وزیر با الگوریتم پس‌گرد (Backtracking) — به زبان ساده
^^
