গ্রাফ অ্যালগরিদম (Graph Algorithms)

গ্রাফ অ্যালগরিদম এমন কিছু গাণিতিক পদ্ধতি যা গ্রাফ তত্ত্ব (Graph Theory)-এর বিভিন্ন সমস্যার সমাধান করতে ব্যবহৃত হয়। গ্রাফ হলো একটি গাণিতিক কাঠামো যা বিভিন্ন নোড বা শীর্ষবিন্দু (Vertex) এবং তাদের মধ্যে সংযোগ বা প্রান্ত (Edge) নিয়ে গঠিত। গ্রাফ অ্যালগরিদম কম্পিউটার বিজ্ঞান ও ডেটা স্ট্রাকচারে অত্যন্ত গুরুত্বপূর্ণ, কারণ এটি নেটওয়ার্ক বিশ্লেষণ, রুট প্ল্যানিং, গেম থিওরি ইত্যাদিতে ব্যবহৃত হয়।

গ্রাফের প্রকারভেদ

গ্রাফ সাধারণত বিভিন্ন ধরনের হতে পারে:

1. নির্দেশিত গ্রাফ (Directed Graph): এখানে প্রতিটি প্রান্তের একটি নির্দিষ্ট দিক থাকে, অর্থাৎ গ্রাফে নোডগুলোতে নির্দিষ্ট পথে যাওয়া সম্ভব।
2. অনির্দেশিত গ্রাফ (Undirected Graph): এখানে প্রান্তগুলোর কোনো নির্দিষ্ট দিক থাকে না, অর্থাৎ যে কোনো দুই নোডে উভয় দিক থেকে যাওয়া সম্ভব।
3. ওজনযুক্ত গ্রাফ (Weighted Graph): এখানে প্রতিটি প্রান্তের জন্য একটি ওজন বা কস্ট নির্ধারিত থাকে, যা সাধারণত পথের দূরত্ব বা সময় নির্দেশ করে।
4. বাইপার্টাইট গ্রাফ (Bipartite Graph): এটি এমন একটি গ্রাফ যেখানে নোডগুলোকে দুইটি পৃথক সেটে ভাগ করা যায় এবং প্রান্তগুলো কেবল ভিন্ন সেটের নোডের মধ্যে থাকে।

বিভিন্ন ধরনের গ্রাফ অ্যালগরিদম

গ্রাফ অ্যালগরিদম মূলত গ্রাফের বিভিন্ন সমস্যা সমাধানে ব্যবহৃত হয়। কিছু গুরুত্বপূর্ণ গ্রাফ অ্যালগরিদম হলো:

1. ব্রেডথ ফার্স্ট সার্চ (BFS): এটি একটি অন্বেষণ অ্যালগরিদম যা একটি গ্রাফের একটি নির্দিষ্ট শীর্ষবিন্দু থেকে শুরু করে সেই শীর্ষবিন্দুর নিকটবর্তী নোডগুলো অন্বেষণ করে এবং ধীরে ধীরে দূরবর্তী নোডগুলোতে পৌঁছায়।
2. ডেপথ ফার্স্ট সার্চ (DFS): এটি একটি অন্বেষণ অ্যালগরিদম যা একটি শীর্ষবিন্দু থেকে শুরু করে একটানা গভীরের দিকে চলে যতক্ষণ পর্যন্ত নতুন শীর্ষবিন্দু পাওয়া যায়। যখন কোনও শীর্ষবিন্দুতে আর এগোনো সম্ভব হয় না, তখন এটি পূর্বের অবস্থানে ফিরে যায়।
3. ডিজকস্ট্রা অ্যালগরিদম (Dijkstra’s Algorithm): এটি ওজনযুক্ত গ্রাফের সর্বনিম্ন পথ নির্ণয় করতে ব্যবহৃত হয়। এটি একটি নির্দিষ্ট উৎস শীর্ষবিন্দু থেকে অন্য সকল শীর্ষবিন্দুর সর্বনিম্ন পথ নির্ধারণ করে।
4. বেলম্যান-ফোর্ড অ্যালগরিদম (Bellman-Ford Algorithm): এটি সর্বনিম্ন পথ নির্ধারণের জন্য ব্যবহৃত হয় এবং এটি নেগেটিভ ওজন বিশিষ্ট গ্রাফেও কাজ করে, যা ডিজকস্ট্রা অ্যালগরিদমে সম্ভব নয়।
5. ফ্লয়েড-ওয়ারশাল অ্যালগরিদম (Floyd-Warshall Algorithm): এটি সর্ব-জোড়া সর্বনিম্ন পথ নির্ণয় করতে ব্যবহৃত হয়, যেখানে গ্রাফের প্রতিটি শীর্ষবিন্দু থেকে প্রতিটি শীর্ষবিন্দুর মধ্যে সর্বনিম্ন পথ নির্ধারণ করা হয়।
6. প্রাইম অ্যালগরিদম (Prim’s Algorithm): এটি একটি গ্রাফের ন্যূনতম বিস্তৃত গাছ (Minimum Spanning Tree) তৈরিতে ব্যবহৃত হয়, যেখানে গ্রাফের সকল শীর্ষবিন্দুকে যুক্ত করার জন্য ন্যূনতম ওজনের প্রান্তগুলো নির্বাচন করা হয়।
7. ক্রুসকাল অ্যালগরিদম (Kruskal’s Algorithm): এটি ওজনযুক্ত গ্রাফের ন্যূনতম বিস্তৃত গাছ তৈরির জন্য ব্যবহৃত হয়, এবং এটি প্রান্তগুলোকে ওজনের ভিত্তিতে সাজিয়ে কাজ করে।

গ্রাফ অ্যালগরিদমের ব্যবহার

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

1. নেটওয়ার্ক রাউটিং: ইন্টারনেট প্রোটোকল রাউটিংয়ে সর্বনিম্ন পথ নির্ধারণে ডিজকস্ট্রা এবং বেলম্যান-ফোর্ড অ্যালগরিদম ব্যবহার হয়।
2. সোশ্যাল নেটওয়ার্ক বিশ্লেষণ: সোশ্যাল মিডিয়াতে বন্ধু বা অনুসারীদের মধ্যে সংযোগ বিশ্লেষণ এবং পরিসংখ্যান নির্ধারণে BFS এবং DFS ব্যবহৃত হয়।
3. গেম থিওরি: বিভিন্ন গেমের জন্য লেভেল বা পাজল সমাধানে DFS এবং BFS কার্যকর।
4. জেনেটিক্স ও বায়োলজি: জিনের সংযোগ ও প্রোটিনের গঠন বিশ্লেষণে গ্রাফ অ্যালগরিদম ব্যবহৃত হয়।
5. ট্রাফিক এবং রুট প্ল্যানিং: গুগল ম্যাপস এবং জিপিএস ট্র্যাকিংয়ে পথ নির্ধারণে গ্রাফ অ্যালগরিদম ব্যবহার করা হয়।

গ্রাফ অ্যালগরিদম কম্পিউটার বিজ্ঞান এবং বিভিন্ন গণিতীয় সমস্যার সমাধানে অপরিহার্য। এর মাধ্যমে বিভিন্ন সংযোগ বিশ্লেষণ করা, নেটওয়ার্ক অপ্টিমাইজেশন, এবং সর্বনিম্ন পথ নির্ধারণ করা সম্ভব হয়।

Depth-First Search (DFS)

Depth-First Search (DFS) হলো একটি গ্রাফ বা ট্রি অনুসন্ধান অ্যালগরিদম, যা প্রথমে একটি শাখার শেষ পর্যন্ত অনুসন্ধান করে এবং তারপর ফিরে এসে অন্য শাখার দিকে অগ্রসর হয়। এটি মূলত Stack ডেটা স্ট্রাকচার ব্যবহার করে, যেখানে একটি নোড পরিদর্শন করার পর তার সব অবাঞ্ছিত (unvisited) সন্তান নোডগুলোকে স্ট্যাকের উপরে রাখা হয়।

DFS এর কাজের ধাপ:

1. একটি নোড নির্বাচন করে পরিদর্শন করুন এবং তার পরবর্তী (child) নোডে যান।
2. প্রতিটি নোড পরিদর্শনের সময় স্ট্যাকে রাখুন।
3. যদি কোনো নোডের সব সন্তান নোড পরিদর্শন করা হয়ে যায়, তাহলে আগের নোডে ফিরে যান।
4. এভাবে প্রতিটি নোড পরিদর্শন করুন যতক্ষণ না সমস্ত নোড পরিদর্শিত হয়।

উদাহরণ কোড (Python):

def dfs(graph, node, visited):
    if node not in visited:
        print(node, end=" ")
        visited.add(node)
        for neighbor in graph[node]:
            dfs(graph, neighbor, visited)

# গ্রাফটি
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}
visited = set()
dfs(graph, 'A', visited)

এই কোডটি A নোড থেকে শুরু করে প্রতিটি নোডে DFS অনুসরণ করে চলে। প্রতিটি নোড একবার করে পরিদর্শন করা হবে।

DFS এর ব্যবহার:

• সাইকেল ডিটেকশন
• টপোলজিক্যাল সাজানো
• গেমের বিভিন্ন স্তরের সমাধান
• পথের খোঁজ

Breadth-First Search (BFS)

Breadth-First Search (BFS) হলো একটি গ্রাফ বা ট্রি অনুসন্ধান অ্যালগরিদম, যা প্রথমে একটি নির্দিষ্ট নোড থেকে শুরু করে তার আশেপাশের নোডগুলোকে পরিদর্শন করে এবং এরপর পর্যায়ক্রমে আরো দূরের নোডগুলোতে অগ্রসর হয়। এটি Queue ডেটা স্ট্রাকচার ব্যবহার করে, যেখানে প্রথমে প্রবেশ করা নোডটি প্রথমে বের হয়।

BFS এর কাজের ধাপ:

1. একটি নোড নির্বাচন করে পরিদর্শন করুন এবং তাকে কিউতে যুক্ত করুন।
2. কিউ থেকে প্রথম নোডটি বের করে তার সমস্ত অবাঞ্ছিত শিশু নোডগুলোকে কিউতে যোগ করুন।
3. প্রতিটি নোড পরিদর্শন করার পর কিউ থেকে সরিয়ে নিন।
4. এই প্রক্রিয়া চলতে থাকে যতক্ষণ না সমস্ত নোড পরিদর্শিত হয়।

উদাহরণ কোড (Python):

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)

    while queue:
        node = queue.popleft()
        print(node, end=" ")
        for neighbor in graph[node]:
            if neighbor not in visited:
                queue.append(neighbor)
                visited.add(neighbor)

# গ্রাফটি
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}
bfs(graph, 'A')

এই কোডটি A নোড থেকে শুরু করে প্রতিটি নোডে BFS অনুসরণ করে চলে এবং পরম্পরাগতভাবে নোডগুলো পরিদর্শন করা হয়।

BFS এর ব্যবহার:

• পথ খোঁজার সমস্যা (Shortest Path Problem)
• সামাজিক নেটওয়ার্ক বিশ্লেষণ
• গেম তত্ত্ব
• ওয়েব ক্রলিং

DFS এবং BFS এর তুলনা

DFS এবং BFS উভয়ই গ্রাফ ও ট্রি অনুসন্ধানে ব্যবহৃত হয় তবে বিভিন্ন ক্ষেত্রে এদের ব্যবহার ও কার্যকারিতা ভিন্ন।

Dijkstra's অ্যালগরিদম

Dijkstra's অ্যালগরিদম একটি গ্রাফে উৎস নোড থেকে অন্যান্য নোডে সর্বনিম্ন পথ (Shortest Path) খুঁজে বের করার জন্য ব্যবহৃত হয়। এটি প্রাথমিকভাবে নন-নেগেটিভ ওয়েট সম্পন্ন গ্রাফের জন্য কার্যকর। এই অ্যালগরিদম গ্রাফের প্রতিটি নোডের সাথে উৎস নোডের দূরত্ব হিসাব করে এবং প্রতি ধাপে নিকটবর্তী নোডটি নির্বাচন করে চলতে থাকে।

Dijkstra's অ্যালগরিদমের ধাপসমূহ:

1. প্রতিটি নোডের জন্য প্রাথমিকভাবে দূরত্ব অসীম হিসেবে সেট করুন, এবং উৎস নোডের জন্য দূরত্ব ০ হিসেবে নির্ধারণ করুন।
2. একটি ভিজিটেড নোডের তালিকা তৈরি করুন এবং উৎস নোডটি যোগ করুন।
3. উৎস নোড থেকে সরাসরি সংযুক্ত নোডগুলোর জন্য সর্বনিম্ন দূরত্ব আপডেট করুন।
4. তারপর নিকটতম নোড নির্বাচন করুন এবং সেই নোড থেকে সংযুক্ত নোডগুলোর দূরত্ব আপডেট করুন।
5. প্রতিটি নোড ভিজিট হওয়া পর্যন্ত উপরের প্রক্রিয়াটি পুনরাবৃত্তি করুন।

উদাহরণ:

ধরা যাক, একটি গ্রাফ আছে যেখানে নোড এবং প্রান্তের ওয়েট রয়েছে। Dijkstra's অ্যালগরিদম ব্যবহার করে উৎস নোড থেকে প্রতিটি নোডে সর্বনিম্ন পথ বের করা হয়।

Floyd-Warshall অ্যালগরিদম

Floyd-Warshall অ্যালগরিদম গ্রাফের প্রতিটি নোড থেকে অন্য প্রতিটি নোডে সর্বনিম্ন পথ নির্ণয় করার জন্য ব্যবহৃত হয়। এটি একটি ডায়নামিক প্রোগ্রামিং ভিত্তিক পদ্ধতি যা গ্রাফের সবকটি নোডের জন্য সংক্ষিপ্ততম পথ নির্ণয় করে। এই অ্যালগরিদমটি মূলত ন্যূনতম দূরত্বের ম্যাট্রিক্স আপডেট করে এবং ধাপে ধাপে সমাধান দেয়।

Floyd-Warshall অ্যালগরিদমের ধাপসমূহ:

1. একটি দূরত্ব ম্যাট্রিক্স তৈরি করুন যেখানে প্রতিটি নোড থেকে অন্য নোড পর্যন্ত প্রাথমিক দূরত্ব দেয়া থাকবে।
2. গ্রাফের প্রতিটি নোডকে একবার করে "মধ্যবর্তী নোড" হিসেবে বিবেচনা করুন।
3. \( d[i][j] = \min(d[i][j], d[i][k] + d[k][j]) \) ব্যবহার করে প্রতিটি নোডের জন্য দূরত্ব আপডেট করুন।
4. এই পদ্ধতিতে প্রতিটি নোডের মধ্য দিয়ে যাওয়ার পথে ন্যূনতম দূরত্ব খুঁজে পাওয়া যায়।

উদাহরণ:

ধরা যাক, একটি গ্রাফ আছে যেখানে \( A \), \( B \), এবং \( C \) নোড রয়েছে। এই তিনটি নোডের মধ্যে প্রতিটি পথে চলার সর্বনিম্ন দূরত্ব নির্ধারণ করতে Floyd-Warshall অ্যালগরিদম ব্যবহার করা হবে।

Dijkstra's অ্যালগরিদম একক উৎস থেকে নোডের সর্বনিম্ন পথ খুঁজতে ব্যবহার করা হয়, যেখানে Floyd-Warshall অ্যালগরিদম প্রতিটি নোড থেকে প্রতিটি নোডে সর্বনিম্ন পথ নির্ণয় করতে সক্ষম।

Prim's অ্যালগরিদম

Prim's অ্যালগরিদম হলো একটি গ্রাফ তত্ত্বের অ্যালগরিদম, যা একটি কানেক্টেড গ্রাফের মিনিমাম স্প্যানিং ট্রি (Minimum Spanning Tree বা MST) বের করতে ব্যবহৃত হয়। MST হলো একটি উপগ্রাফ, যেখানে সমস্ত নোড কানেক্ট থাকে এবং এটির মোট প্রান্তের ওজন সবচেয়ে কম হয়।

Prim's অ্যালগরিদমটি ধীরে ধীরে নোড যোগ করে MST গঠন করে। এটি সাধারণত গ্রাফের একটি নির্দিষ্ট নোড থেকে শুরু করে এবং তার আশেপাশের প্রান্তের মধ্যে সর্বনিম্ন ওজনের প্রান্তটি নির্বাচন করে চলতে থাকে, যতক্ষণ না সমস্ত নোড কাভার হয়।

Prim's অ্যালগরিদমের ধাপসমূহ:

1. প্রথমে একটি আর্বিট্রারি নোড নির্বাচন করে সেটিকে MST-তে অন্তর্ভুক্ত করুন।
2. MST-তে থাকা নোডগুলোর সাথে যেকোনো কানেক্টেড প্রান্তের মধ্যে সর্বনিম্ন ওজনের প্রান্ত নির্বাচন করুন এবং সংশ্লিষ্ট নোডটিকে MST-তে যোগ করুন।
3. পুনরাবৃত্তি চালিয়ে যান যতক্ষণ না সমস্ত নোড MST-তে অন্তর্ভুক্ত হয়।

উদাহরণ:

ধরি, একটি গ্রাফ আছে, যেখানে নোড এবং তাদের মধ্যে প্রান্তগুলির ওজন রয়েছে। Prim's অ্যালগরিদমের সাহায্যে নিম্নতম ওজনের স্প্যানিং ট্রি তৈরি করতে গ্রাফের যেকোনো একটি নোড থেকে শুরু করে প্রক্রিয়াটি সম্পন্ন করা হয়।

Prim's অ্যালগরিদম সাধারণত O(V^2) জটিলতায় কাজ করে, যেখানে V হলো নোডের সংখ্যা।

Kruskal's অ্যালগরিদম

Kruskal's অ্যালগরিদম আরেকটি গ্রাফ তত্ত্বের অ্যালগরিদম, যা মিনিমাম স্প্যানিং ট্রি (MST) বের করতে ব্যবহৃত হয়। তবে Prim's এর থেকে এটি ভিন্ন, কারণ Kruskal's অ্যালগরিদম প্রতিটি নোড থেকে প্রান্ত যোগ না করে বরং প্রান্তগুলিকে ওজনের ক্রম অনুযায়ী সাজিয়ে সবচেয়ে কম ওজনের প্রান্ত থেকে MST গঠন শুরু করে।

Kruskal's অ্যালগরিদমের ধাপসমূহ:

1. সমস্ত প্রান্ত ওজন অনুযায়ী সাজান।
2. প্রান্তগুলো থেকে ক্রমানুসারে সর্বনিম্ন ওজনের প্রান্ত নির্বাচন করুন এবং এটি MST-তে যোগ করুন, যদি এটি কোনো সাইকেল তৈরি না করে।
3. প্রক্রিয়াটি চালিয়ে যান যতক্ষণ না সমস্ত নোড সংযুক্ত হয় এবং MST গঠন সম্পন্ন হয়।

উদাহরণ:

ধরি, একটি গ্রাফ আছে, যেখানে বিভিন্ন প্রান্ত এবং তাদের ওজন নির্ধারিত। Kruskal's অ্যালগরিদমে প্রান্তগুলোকে ওজন অনুযায়ী সাজিয়ে সবচেয়ে কম ওজনের প্রান্ত থেকে শুরু করে কাজ করা হয়।

Kruskal's অ্যালগরিদম সাধারণত O(E log E) জটিলতায় কাজ করে, যেখানে \(E\) হলো প্রান্তের সংখ্যা।

Prim's বনাম Kruskal's অ্যালগরিদম

Prim's এবং Kruskal's উভয় অ্যালগরিদমই MST বের করতে ব্যবহৃত হয়, তবে Prim's সাধারণত ঘন গ্রাফে বেশি কার্যকরী, এবং Kruskal's কম প্রান্তবিশিষ্ট গ্রাফে বেশি কার্যকরী।

গ্রাফ ট্রাভার্সাল (Graph Traversal)

গ্রাফ ট্রাভার্সাল হলো একটি প্রক্রিয়া যেখানে গ্রাফের প্রতিটি নোড বা শীর্ষ বিন্দু পরিদর্শন করা হয়। এটি গ্রাফের বিভিন্ন উপাদান এবং সম্পর্কগুলো খুঁজে বের করার জন্য গুরুত্বপূর্ণ। গ্রাফ ট্রাভার্সালে প্রধানত দুইটি পদ্ধতি ব্যবহৃত হয়:

1. ব্রেডথ-ফার্স্ট সার্চ (Breadth-First Search - BFS):

   • BFS পদ্ধতিতে প্রথমে একটি নোড থেকে শুরু করে তার সংলগ্ন নোডগুলিকে পরিদর্শন করা হয়, তারপর সেই নোডগুলোর সংলগ্ন নোডগুলিতে যাওয়া হয়। এটি কিউ (Queue) ডেটা স্ট্রাকচার ব্যবহার করে।
   • BFS সাধারণত ছোট পথ খুঁজতে এবং গ্রাফের একাংশ থেকে অন্য অংশে পৌঁছানোর সমস্যা সমাধানে ব্যবহৃত হয়।

   উদাহরণ কোড:

   from collections import deque
   
   def bfs(graph, start):
       visited = set()
       queue = deque([start])
   
       while queue:
           node = queue.popleft()
           if node not in visited:
               visited.add(node)
               print(node, end=" ")
   
               for neighbor in graph[node]:
                   if neighbor not in visited:
                       queue.append(neighbor)

2. ডেপথ-ফার্স্ট সার্চ (Depth-First Search - DFS):

   • DFS পদ্ধতিতে প্রথমে একটি নোড থেকে শুরু করে যতদূর সম্ভব ডিপ্থে চলে যাওয়া হয়, তারপর আবার উপরের স্তরে ফিরে আসা হয়। এটি স্ট্যাক (Stack) বা রিকারশন ব্যবহার করে।
   • DFS সাধারণত গ্রাফের সংযোগিতার অবস্থা চেক করতে এবং চক্র (cycle) খুঁজতে ব্যবহৃত হয়।

   উদাহরণ কোড:

   def dfs(graph, node, visited=set()):
       if node not in visited:
           visited.add(node)
           print(node, end=" ")
           for neighbor in graph[node]:
               dfs(graph, neighbor, visited)

গ্রাফের ছোট পথ খোঁজা (Shortest Path in Graph)

গ্রাফে একটি নির্দিষ্ট নোড থেকে অন্য একটি নির্দিষ্ট নোড পর্যন্ত সবচেয়ে ছোট পথ খোঁজার জন্য কয়েকটি অ্যালগরিদম রয়েছে। সাধারণত ওয়েটেড ও আনওয়েটেড গ্রাফের জন্য ভিন্ন ভিন্ন অ্যালগরিদম ব্যবহৃত হয়।

১. ডাইজস্ট্রা অ্যালগরিদম (Dijkstra's Algorithm)

• ডাইজস্ট্রা অ্যালগরিদম হলো একটি গ্রাফ ট্রাভার্সাল পদ্ধতি যা ওয়েটেড গ্রাফে ছোট পথ খোঁজার জন্য ব্যবহৃত হয়। এটি নির্দিষ্ট একটি সূচক থেকে অন্যান্য সমস্ত নোড পর্যন্ত সবচেয়ে ছোট পথ নির্ধারণ করে।
• এই অ্যালগরিদমে প্রাইওরিটি কিউ ব্যবহার করা হয়, যা প্রতি ধাপে সবচেয়ে কম ওয়েটের পথকে অগ্রাধিকার দেয়।

উদাহরণ কোড:

import heapq

def dijkstra(graph, start):
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0
    priority_queue = [(0, start)]

    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)

        if current_distance > distances[current_node]:
            continue

        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight

            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances

২. বেলম্যান-ফোর্ড অ্যালগরিদম (Bellman-Ford Algorithm)

• বেলম্যান-ফোর্ড অ্যালগরিদম ডাইজস্ট্রার মতোই ছোট পথ খোঁজে, কিন্তু এটি নেগেটিভ ওয়েট থাকা গ্রাফে কাজ করতে পারে।
• এটি প্রতিটি এজের উপর নির্দিষ্ট সংখ্যক বার ট্রাভার্সাল করে সবচেয়ে ছোট পথ নির্ধারণ করে। তবে এটি O(V*E) সময় জটিলতার, যেখানে V হলো নোড এবং E হলো এজ সংখ্যা।

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

• ফ্লয়েড-ওয়ারশাল একটি অল-পেয়ারস ছোট পথ নির্ণয়ের অ্যালগরিদম। এটি গ্রাফের সকল নোড জোড়ার মধ্যে ছোট পথ নির্ধারণ করে।
• এই অ্যালগরিদমটি ডাইনামিক প্রোগ্রামিং এর সাহায্যে কাজ করে এবং সাধারণত ছোট গ্রাফে ব্যবহার করা হয়।

উদাহরণ কোড:

def floyd_warshall(graph):
    nodes = list(graph.keys())
    distances = {node: {node2: float('infinity') for node2 in nodes} for node in nodes}

    for node in nodes:
        distances[node][node] = 0

    for node in graph:
        for neighbor, weight in graph[node].items():
            distances[node][neighbor] = weight

    for k in nodes:
        for i in nodes:
            for j in nodes:
                distances[i][j] = min(distances[i][j], distances[i][k] + distances[k][j])

    return distances

ট্রাভার্সাল এবং ছোট পথ খোঁজার ব্যবহার ক্ষেত্র

1. রুট প্ল্যানিং: জিপিএস এবং ন্যাভিগেশন সিস্টেমে ছোট পথ নির্ধারণে ব্যবহৃত হয়।
2. নেটওয়ার্ক রাউটিং: নেটওয়ার্ক প্যাকেট ট্রান্সফারের ছোট রুট খুঁজে বের করার জন্য।
3. গেম ডেভেলপমেন্ট: বিভিন্ন চরিত্র বা অবজেক্টের মুভমেন্ট এবং পথ নির্ধারণে।
4. সোশ্যাল নেটওয়ার্ক অ্যানালাইসিস: সোশ্যাল গ্রাফে সংযোগ এবং সম্পর্ক বিশ্লেষণে।

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