কনটেন্টে যান

Graphs — শর্ত মেনে ডেলিভারির পথ বানান

কিছু delivery শেষ করার আগে অন্য delivery শেষ করা দরকার। আবার শহরের রাস্তাগুলো একমুখী এবং প্রতিটির travel cost আলাদা। প্রথমে বৈধ delivery order বানাবেন, তারপর সেই order-এর প্রতিটি যাত্রার shortest path বের করবেন। একটি ধাপের output পরের ধাপের input হবে।

Microsoft কোর্সের সংযোগ: Module 3-এর graph ধারণা ও traversal প্রস্তুতি; Module 5-এর Dijkstra ও priority queue এখানে সরাসরি ব্যবহার হবে। A* এই lab-এ নেই।

১. আগে পড়বেন ও অনুশীলন করবেন

ক্রম উপকরণ যা বুঝে আসবেন
১ Graph ধারণা, চিত্র, BFS Vertex, directed edge, adjacency list, reachability
২ Topological sort, Course Schedule II Indegree ও prerequisite cycle
৩ Shortest path, Network Delay Time Nonnegative weight-এ Dijkstra কেন চলে
৪ Shortest Routes I Relaxation, stale heap entry ও unreachable vertex

২ নম্বরের একটি DAG-তে হাতে indegree কমান। ৩ নম্বরের একটি weighted graph-এ distance ও parent পাশাপাশি লিখুন। তারপর lab-এ আসুন।

২. সুনির্দিষ্ট সমস্যা

delivery_plan(n, roads, deliveries, dependencies, start=0) লিখুন।

  • Station-এর ID 0 থেকে n-1। roads-এর (u, v, cost) কেবল u → v রাস্তা; reverse রাস্তা নিজে থেকে নেই।
  • deliveries হলো যেসব station-এ একবার delivery করতে হবে তাদের distinct ID। start-এও delivery থাকতে পারে।
  • dependencies-এর (a, b) মানে delivery a শেষ হওয়ার পরে delivery b করতে হবে। দুটিই delivery list-এ থাকবে। Duplicate dependency-কে একবার ধরুন।
  • প্রতিবার eligible delivery-র মধ্যে সবচেয়ে ছোট station ID বেছে একটি সম্পূর্ণ topological order তৈরি করুন। Dependency cycle হলে ValueError।
  • সেই order মেনে বর্তমান station থেকে পরের delivery station-এর shortest path নিন। Delivery শেষে current station বদলাবে। কোনো leg unreachable হলে ValueError।
  • Order, প্রতি leg-এর path/cost এবং total cost দিন। সমান খরচের একাধিক shortest path হলে যেকোনোটি গ্রহণযোগ্য।

সীমা: 1 ≤ n ≤ 200, সর্বোচ্চ 5,000 road, সর্বোচ্চ 40 delivery, cost পূর্ণসংখ্যা 0..10⁶। Parallel road ও self-loop থাকতে পারে। Negative weight, invalid vertex বা duplicate delivery ID গ্রহণযোগ্য নয়। ফাঁকা delivery list বৈধ।

গুরুত্বপূর্ণ নিয়ম: কোনো future delivery station দিয়ে শুধু পথ অতিক্রম করলে delivery সম্পন্ন হবে না। Service হবে শুধুমাত্র সেই delivery-র turn-এ। এই নির্দিষ্ট order-এর প্রতিটি leg optimal; সব সম্ভাব্য delivery order-এর মধ্যে global minimum tour খোঁজা হচ্ছে না।

Python
roads = [(0, 1, 2), (0, 2, 5), (1, 2, 1), (2, 3, 2), (1, 3, 8)]
delivery_plan(4, roads, [3, 1, 2], [(1, 3), (2, 3)])

flowchart LR
    s["0 · start"] -->|2| a["1"]
    s -->|5| b["2"]
    a -->|1| b
    a -->|8| c["3"]
    b -->|2| c
Leg Path Cost সিদ্ধান্ত
0 → 1 [0, 1] 2 1 ও 2 eligible; ছোট ID 1 আগে
1 → 2 [1, 2] 1 3-এর জন্য 2-ও শেষ করতে হবে
2 → 3 [2, 3] 2 দুই prerequisite শেষ
Python
{
    "order": [1, 2, 3],
    "legs": [
        {"from": 0, "to": 1, "path": [0, 1], "cost": 2},
        {"from": 1, "to": 2, "path": [1, 2], "cost": 1},
        {"from": 2, "to": 3, "path": [2, 3], "cost": 2},
    ],
    "total_cost": 5,
}

৩. চারটি guided milestone

A — দুটি graph আলাদা করে লিখুন

Road graph-এ weighted adjacency list বানান। Dependency graph-এ delivery ID-এর outgoing set ও indegree বানান। এরা একই ধরনের edge নয়।

Invariant: dependency duplicate হলেও indegree একবার বাড়বে। Checkpoint: example-এ delivery 3-এর indegree 2; road 1 → 3 থাকার কারণে dependency তৈরি হয় না।

B — Kahn algorithm-এ order

Indegree zero delivery-গুলো min-heap-এ রাখুন। Smallest ID pop করে answer-এ দিন; তার dependency edge সরিয়ে নতুন zero-indegree vertex heap-এ দিন।

Hint: সাধারণ queue-ও topological order দেয়, কিন্তু আমাদের smallest-ID tie-break মেনে চলতে heap দরকার। Invariant: ready heap-এর কোনো delivery-র unfinished prerequisite নেই।

Checkpoint: order [1, 2, 3]। (3, 1) dependency যোগ করলে সব delivery বের হবে না; তখন cycle error।

C — এক leg-এর Dijkstra ও path

Source-এর distance 0, অন্যদের infinity। Heap থেকে (distance, vertex) নিন। প্রতিটি neighbor-এর জন্য new = distance + weight; ছোট হলে distance, parent ও heap update করুন।

Invariant: parent বদলাবে শুধু strict improvement-এ। Heap-এর পুরোনো value বর্তমান best distance-এর সমান না হলে সেটি skip করুন। এতে zero-weight edge-এ equal-cost parent cycle তৈরি করবেন না।

Checkpoint: source 0 থেকে station 3-এর best distance 5, parent chain 3 ← 2 ← 1 ← 0। এটিকে reverse করলে path হয়।

D — Order ধরে leg জুড়ুন

Current station দিয়ে Dijkstra চালিয়ে পরের delivery-র path নিন; cost যোগ করুন, current বদলান। Output শুধু vertex list নয়: প্রত্যেক consecutive pair-এর সত্যিকারের road ও total cost মিলতে হবে।

Checkpoint: source-এর নিজের delivery হলে path [source], cost 0; unreachable হলে partial plan-কে successful result হিসেবে ফেরত দেবেন না।

৪. সমাধান মিলিয়ে দেখুন

কেন এই সমাধান কাজ করে

Kahn-এর ready set-এ ঠিক এখন সম্পন্ন করা যায় এমন delivery থাকে। Minimum ID নেওয়ার ফলে চাওয়া deterministic order পাওয়া যায়। সব delivery বের না হলে graph-এ cycle আছে।

Nonnegative road cost-এর জন্য Dijkstra minimum unsettled distance-কে নিরাপদে expand করতে পারে। Parent কেবল distance কমলে বদলালে path সেই cost-এর একটি বাস্তব route দেয়। Path reconstruction ও cost summation একই shortest-path result ব্যবহার করে।

Python solution · unit test।

৫. Test ও complexity

Repository root থেকে চালান; download করলে solution ও test practice/ folder-এ রাখুন।

Bash
python -m unittest discover -s practice -p 'test_graphs_lab.py' -v

৯টি test method-এ example, empty/start delivery, duplicate prerequisite, cycle, directed unreachable route, zero weight, parallel road ও stale heap entry আছে। Topological tie-break সব permutation-এর সঙ্গে মেলানো হয়। ৫০টি seeded random map-এর shortest cost আলাদা Floyd–Warshall oracle দিয়ে যাচাই হয়; ফেরত path-এর edge cost-ও যোগ করে পরীক্ষা হয়।

V station, E road, D delivery, P distinct prerequisite হলে topology O(P + D log D)। Parallel edge-সহ heap-based Dijkstra প্রতি leg-এ O(V + E log(E+1)); মোট O(P + D log D + D(V + E log(E+1)))। Graph, heap ও path report মিলিয়ে O(V + E + P + DV) space-এর upper bound।

৬. Coverage ও বাকি pattern

এখানে অনুশীলন আলাদা করে করবেন
Directed adjacency ও weighted path Grid BFS, flood fill, connected components
Dependency DAG, cycle detection Bipartite test, DFS edge classification
Dijkstra, relaxation, parent path Negative-weight shortest path, A* heuristic
Priority queue ও deterministic order Cheapest flight with k stops: state-এ stop count লাগে

সব graph problem-এর map ব্যবহার করে বাকি pattern করুন।