ফ্লয়েড-ওয়ারশল অ্যালগরিদম (Floyd-Warshall Algorithm)

শর্টেস্ট পাথ অ্যালগরিদম (Shortest Path Algorithms) - গ্রাফ থিওরি (Graph Theory) - Computer Science

318

ফ্লয়েড-ওয়ারশল অ্যালগরিদম (Floyd-Warshall Algorithm)

ফ্লয়েড-ওয়ারশল অ্যালগরিদম হল একটি গ্রাফের মধ্যে সমস্ত জোড়ের মধ্যে সর্বনিম্ন পথ (shortest path) নির্ধারণ করার জন্য ব্যবহৃত একটি কার্যকরী অ্যালগরিদম। এটি একটি ডাইনামিক প্রোগ্রামিং পদ্ধতি যা ঋণাত্মক ওজনের এজ সমর্থন করে এবং সম্পূর্ণ গ্রাফের জন্য পাথের দৈর্ঘ্য নির্ধারণ করতে সক্ষম।

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

ম্যাট্রিক্স প্রস্তুতি:
- একটি $V \times V$ $V$ $\times$ $V$ ম্যাট্রিক্স তৈরি করুন, যেখানে $V$ $V$ হল গ্রাফের ভেরটেক্স সংখ্যা। এই ম্যাট্রিক্সে সরাসরি সংযুক্ত ভেরটেক্সের মধ্যে দূরত্ব নির্ধারণ করুন।
- যদি দুটি ভেরটেক্সের মধ্যে সরাসরি সংযোগ না থাকে, তবে দূরত্ব অসীম (∞) হিসেবে চিহ্নিত করুন।
অ্যালগরিদমের পুনরাবৃত্তি:
- তিনটি স্তরের লুপ ব্যবহার করে সমস্ত ভেরটেক্স $k$ $k$ , $i$ $i$ , $j$ $j$ এর জন্য সর্বনিম্ন দূরত্ব আপডেট করুন।
- যদি $dist[i][k] + dist[k][j] < dist[i][j]$ $dist$ $[$ $i$ $]$ $[$ $k$ $]$ $+$ $dist$ $[$ $k$ $]$ $[$ $j$ $]$ $<$ $dist$ $[$ $i$ $]$ $[$ $j$ $]$ হয়, তবে $dist[i][j]$ $dist$ $[$ $i$ $]$ $[$ $j$ $]$ আপডেট করুন।
ঋণাত্মক চক্র চেক:
- যদি $dist[i][i] < 0$ $dist$ $[$ $i$ $]$ $[$ $i$ $]$ $<$ $0$ হয়, তবে গ্রাফে ঋণাত্মক চক্র আছে।

পseudocode for Floyd-Warshall Algorithm

Floyd-Warshall(Graph G):
  Create a distance matrix dist[][] and initialize it
  for k from 1 to |V|:
    for i from 1 to |V|:
      for j from 1 to |V|:
        if dist[i][j] > dist[i][k] + dist[k][j]:
          dist[i][j] = dist[i][k] + dist[k][j]

  return dist

উদাহরণ

ধরি, আমাদের একটি গ্রাফ আছে

    (2)
 A ------- B
  |         |
(1)       (-5)
  |         |
 C ------- D
     (4)

ভেরটেক্স: A, B, C, D
এজ: A-B (2), A-C (1), B-D (-5), C-D (4)

ফ্লয়েড-ওয়ারশল অ্যালগরিদমের প্রক্রিয়া:

প্রাথমিক ম্যাট্রিক্স তৈরি করা হবে:

     A    B    C    D
 A   0    2    1    ∞
 B   ∞    0    ∞    -5
 C   ∞    ∞    0    4
 D   ∞    ∞    ∞    0

$k$ k হিসেবে A, B, C, D কে পরপর ব্যবহার করা হবে এবং ম্যাট্রিক্স আপডেট করা হবে:
- প্রথমে A কে ব্যবহার করে A থেকে B এবং C এর দূরত্বগুলি আপডেট হবে।
- তারপর B কে ব্যবহার করে B থেকে D এর মাধ্যমে A থেকে D এর নতুন দূরত্ব আপডেট হবে।
- পরবর্তীতে C এবং D কে ব্যবহার করে ম্যাট্রিক্স আরও আপডেট হবে।

শেষ ম্যাট্রিক্স হবে:

     A    B    C    D
 A   0    2    1    -3
 B   ∞    0    ∞    -5
 C   ∞    ∞    0    4
 D   ∞    ∞    ∞    0

সুবিধা

সর্বনিম্ন পাথের জন্য প্রযোজ্য: সমস্ত জোড়ের মধ্যে সর্বনিম্ন পাথ খুঁজে বের করার জন্য কার্যকরী।
ঋণাত্মক ওজনের সমর্থন: ঋণাত্মক এজ থাকার ক্ষেত্রে এটি কাজ করে।

অসুবিধা

জটিলতা: O(V^3), যা বড় গ্রাফের জন্য ধীর গতির হতে পারে।
মেমরি ব্যবহারের সমস্যা: মেমরি ব্যবহারে যথেষ্ট বেশি, কারণ এটি একটি ম্যাট্রিক্সের আকারে কাজ করে।

সারসংক্ষেপ

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

Content added By

Md. Shakil khan

ডাইকস্ট্রা'স অ্যালগরিদম (Dijkstra’s Algorithm) বেলম্যান-ফোর্ড অ্যালগরিদম (Bellman-Ford Algorithm) শর্টেস্ট পাথের বিভিন্ন সমস্যা এবং তার সমাধান

ফ্লয়েড-ওয়ারশল অ্যালগরিদম (Floyd-Warshall Algorithm)

ফ্লয়েড-ওয়ারশল অ্যালগরিদম (Floyd-Warshall Algorithm)

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

পseudocode for Floyd-Warshall Algorithm

উদাহরণ

সুবিধা

অসুবিধা

সারসংক্ষেপ

Promotion

Satt AI

Hi, আমি SATT AI!

ফ্লয়েড-ওয়ারশল অ্যালগরিদম (Floyd-Warshall Algorithm)

ফ্লয়েড-ওয়ারশল অ্যালগরিদম (Floyd-Warshall Algorithm)

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

পseudocode for Floyd-Warshall Algorithm

উদাহরণ

সুবিধা

অসুবিধা

সারসংক্ষেপ

All Notifications

Promotion

Satt AI

Hi, আমি SATT AI!