ফোর্ড-ফালকারসন অ্যালগরিদম (Ford-Fulkerson Algorithm)

ম্যাক্স ফ্লো মিন কাট থিওরেম (Max Flow Min Cut Theorem) - গ্রাফ থিওরি (Graph Theory) - Computer Science

307

ফোর্ড-ফালকসন অ্যালগরিদম (Ford-Fulkerson Algorithm)

ফোর্ড-ফালকসন অ্যালগরিদম একটি ক্লাসিকাল অ্যালগরিদম যা একটি ফ্লো নেটওয়ার্কে সর্বাধিক প্রবাহ (maximum flow) নির্ধারণ করতে ব্যবহৃত হয়। এই অ্যালগরিদমটি একটি উৎস (source) থেকে গন্তব্য (sink) পর্যন্ত প্রবাহ বাড়ানোর জন্য একটি পাথ খুঁজে বের করে এবং ধাপে ধাপে প্রবাহ বাড়াতে থাকে যতক্ষণ না আর কোন পাথ পাওয়া যায়।

অ্যালগরিদমের কাজ করার পদ্ধতি

ফ্লো নেটওয়ার্ক প্রস্তুতি:
- একটি ফ্লো নেটওয়ার্ক $G$ $G$ তৈরি করুন যেখানে প্রতিটি এজের একটি ক্ষমতা (capacity) থাকে।
সর্বাধিক প্রবাহ নির্ধারণ:
- শুরুতে, সমস্ত এজে প্রবাহ $0$ $0$ হিসেবে সেট করুন।
- একটি বৈধ পথ খুঁজুন উৎস থেকে গন্তব্যে (sink) যা এখনও অদ্বিতীয় এজের ক্ষমতা রয়েছে (অর্থাৎ, ফ্লো সীমার মধ্যে আছে)।
পাথের ফ্লো বাড়ানো:
- যখন একটি বৈধ পাথ পাওয়া যায়, তখন এই পাথের উপর দিয়ে প্রবাহ বাড়ান, যা এই পাথের মধ্যে সবচেয়ে কম ক্ষমতা (bottleneck capacity) দ্বারা নির্ধারিত হয়।
ফ্লো আপডেট:
- প্রতিটি এজে প্রবাহ আপডেট করুন এবং যদি কোনও এজের ফ্লো বাড়ানোর পর ইতিমধ্যে সেটি পূর্ণ হয়, তবে ফ্লো কমানোর জন্য বিপরীত এজ যোগ করুন।
পুনরাবৃত্তি:
- পদ্ধতিটি পুনরাবৃত্তি করুন যতক্ষণ না আর কোন বৈধ পাথ পাওয়া যায়।
ফলাফল:
- সর্বাধিক প্রবাহ নির্ধারণ করতে $f$ $f$ ফ্লো পেতে হবে, যা গন্তব্যের প্রাপ্ত ফ্লোর সমান হবে।

pseudocode for Ford-Fulkerson Algorithm

function FordFulkerson(Graph G, source s, sink t):
    Initialize flow f(e) = 0 for all edges e in G
    while there exists an augmenting path p from s to t in residual graph:
        // Find the bottleneck capacity
        capacity = min capacity of edges in p
        for each edge e in p:
            f(e) += capacity  // Update flow
            f(reverse edge e) -= capacity  // Update reverse flow
    return total flow f(t)

উদাহরণ

ধরি, আমাদের একটি ফ্লো নেটওয়ার্ক আছে:

      (10)
   A --------> B
    |          |
  (5)|          |(15)
    |          |
   v          v
   C --------> D
      (10)

উৎস: A
গন্তব্য: D
এজের ক্ষমতা: A-B (10), A-C (5), B-D (15), C-D (10)

অ্যালগরিদমের প্রক্রিয়া:

শুরুতে, সমস্ত ফ্লো $0$ $0$ ।
A থেকে D এর জন্য একটি পাথ A-B-D খুঁজে বের করুন, যেখানে সর্বাধিক ক্যাপাসিটি $10$ $10$ ।
ফ্লো আপডেট করুন: A-B তে $10$ $10$ , B-D তে $10$ $10$ ।
A থেকে D এর জন্য একটি নতুন পাথ A-C-D খুঁজে বের করুন, যেখানে সর্বাধিক ক্যাপাসিটি $5$ $5$ ।
ফ্লো আপডেট করুন: A-C তে $5$ $5$ , C-D তে $5$ $5$ ।

এখন, সর্বাধিক প্রবাহ হবে $10 + 5 = 15$ $10$ $+$ $5$ $=$ $15$ ।

সুবিধা

সাধারণতা: অ্যালগরিদমটি সহজ এবং বাস্তবায়নে সুবিধাজনক।
বিভিন্ন প্রবাহ সমস্যা সমাধান: এটি বিভিন্ন ফ্লো সমস্যা সমাধানে কার্যকর।

অসুবিধা

জটিলতা: ফোর্ড-ফালকসন অ্যালগরিদমের সময় জটিলতা সাধারণত $O(|E| \cdot |f|)$ $O$ $($ $∣$ $E$ $∣$ $\cdot$ $∣$ $f$ $∣$ $)$ , যেখানে $|f|$ $∣$ $f$ $∣$ হল সর্বাধিক প্রবাহ। এটি অন্যান্য অ্যালগরিদমের তুলনায় ধীর হতে পারে।

সারসংক্ষেপ

ফোর্ড-ফালকসন অ্যালগরিদম একটি কার্যকরী পদ্ধতি যা একটি ফ্লো নেটওয়ার্কে সর্বাধিক প্রবাহ নির্ধারণ করতে ব্যবহৃত হয়। এটি একটি সহজ এবং কার্যকরী সমাধান প্রদান করে, যা বিভিন্ন বাস্তব জীবনের সমস্যার সমাধানে অপরিহার্য।

Content added By

Md. Shakil khan

ম্যাক্স ফ্লো এর ধারণা এবং অ্যাপ্লিকেশন ফ্লো নেটওয়ার্ক এবং ক্যাপাসিটি ফ্লো নেটওয়ার্কে সমস্যা এবং সমাধান

ফোর্ড-ফালকারসন অ্যালগরিদম (Ford-Fulkerson Algorithm)

ফোর্ড-ফালকসন অ্যালগরিদম (Ford-Fulkerson Algorithm)

অ্যালগরিদমের কাজ করার পদ্ধতি

pseudocode for Ford-Fulkerson Algorithm

উদাহরণ

সুবিধা

অসুবিধা

সারসংক্ষেপ

Promotion

Satt AI

Hi, আমি SATT AI!

ফোর্ড-ফালকারসন অ্যালগরিদম (Ford-Fulkerson Algorithm)

ফোর্ড-ফালকসন অ্যালগরিদম (Ford-Fulkerson Algorithm)

অ্যালগরিদমের কাজ করার পদ্ধতি

pseudocode for Ford-Fulkerson Algorithm

উদাহরণ

সুবিধা

অসুবিধা

সারসংক্ষেপ

All Notifications

Promotion

Satt AI

Hi, আমি SATT AI!