একটি নির্দেশিত গ্রাফে (digraph), প্রান্তগুলির একটি দিক রয়েছে (A → B ≠ B → A)। একটি ওজনযুক্ত গ্রাফে, প্রতিটি প্রান্ত একটি সংখ্যাত্মক খরচ বহন করে (দূরত্ব, সময়, ক্ষমতা)। উভয়ের সমন্বয় বাস্তব সিস্টেম মডেল করে যেখানে সম্পর্কগুলি এক-দিকমুখী এবং একটি খরচ রয়েছে।
Weighted directed graph:
A --5--> B
A --2--> C
C --1--> B
Adjacency list with weights:
A: [(B,5), (C,2)]
B: []
C: [(B,1)]
graph = {
'A': [('B', 5), ('C', 2)], # directed, weighted edges
'B': [],
'C': [('B', 1)],
}
# Shortest A->B is A->C->B = 2 + 1 = 3, not the direct edge 5.
| ডোমেইন | শীর্ষবিন্দু | ওজনযুক্ত নির্দেশিত প্রান্ত |
|---|---|---|
| মানচিত্র / জিপিএস | সংযোগস্থল | এক-দিকমুখী রাস্তা + ভ্রমণ সময় |
| নেটওয়ার্ক | রাউটার | লিঙ্ক + বিলম্ব/ব্যান্ডউইথ |
| কাজের সময়সূচী | কাজ | নির্ভরতা + সময়কাল |
| অর্থ | মুদ্রা | বিনিময় হার |
| লক্ষ্য | অ্যালগরিদম | জটিলতা |
|---|---|---|
| সংক্ষিপ্ততম পথ (অ-নেতিবাচক ওজন) | Dijkstra | O((V+E) log V) |
| সংক্ষিপ্ততম পথ (নেতিবাচক প্রান্ত) | Bellman-Ford | O(VE) |
| নির্ভরতা সহ ক্রম | Topological sort | O(V+E) |
| চক্র সনাক্ত করা / পৌঁছানোযোগ্যতা | DFS | O(V+E) |
দিক এবং ওজন হল যা একটি বিমূর্ত গ্রাফকে রুটিং, সময়সূচী এবং নির্ভরতা সমস্যার একটি বিশ্বস্ত মডেলে পরিণত করে যা বাস্তব অ্যাপ্লিকেশনগুলি চালিত করে।
অ্যালগরিদম পছন্দটি এই বৈশিষ্ট্যগুলির উপর নির্ভর করে — উদাহরণস্বরূপ, নেতিবাচক ওজনগুলি Dijkstra বাদ দেয় এবং Bellman-Ford প্রয়োজন করে।
বিস্তারিত উত্তরসহ IT ইন্টারভিউ প্রশ্নের একটি লাইব্রেরি — জুনিয়র থেকে সিনিয়র পর্যন্ত।
দান করুন