মডিউল ২_৫ঃ পাথ প্রিন্টিং

আমরা BFS এর মাধ্যমে শর্টেস্ট পাথ বের করা যায় জেনেছি। লেভেল এর মাধ্যমে এটাও জেনেছি শর্টেস্ট দূরত্ব কত হতে পারে। কিন্ত আমরা পাথটা এখনও বের করে দেখেনি যে কোন রাস্তা দিয়ে গেলে আমরা সোর্স থেকে ডেস্টিনেশনে শর্টেস্ট পাথ হবে।

উপরের গ্রাফ এর দিকে খেয়াল করি। এখানে ধর সোর্স হচ্ছে ০ আর ডেস্টিনেশন হচ্ছে ৫। আমরা ০->১->২->৫ এই রাস্তা দিয়ে গেলে লেভেল হবে ৩। ০->১->৩->৪->৫ এই রাস্তা দিয়ে গেলেও লেভেল হবে ৪। তাহলে এখানে আমি চাই আমারে ০->১->২->৫ এই রাস্তাটা দিক।

এটা আমরা খুব সহজেই করতে পারি প্যারেন্ট এ্যারেকে ট্র্যাক রেখে।

একটা প্যারেন্ট এ্যারে থাকবে যার কাজ হচ্ছে প্রত্যেকটা নোড এর প্যারেন্টকে ট্র্যাক রাখা। ইনিশিয়ালি সব নোড এর প্যারেন্ট থাকবে -১।

০->-১

১->-১

২->-১

৩->-১

৪->-১

৫->-১

তারপর আমরা যখন এর লেভেল চেইঞ্জ করব তখনই সেই নোড যে নোড থেকে এসছে তাকে তার প্যারেন্ট হিসেবে আপডেট করে দেব। সোর্স এর প্যারেন্ট সব সময় -১ হবে।

প্রথমে ০ থেকে ১ এ যাবে তাই ১ এর প্যারেন্ট হবে ০। ১ থেকে আমরা ২ ও ৩ এ যাবো। তাই ২ ও ৩ এর প্যারেন্ট হবে ১। ২ থেকেও ৪ এ যাওয়া যায় ৩ থেকেও ৪ এ যাওয়া যায়। সেই ক্ষেত্রে আমরা ইনপুট এ যাকে আগে দেব সে হবে ৪ এর প্যারেন্ট। আমাদের এখানে বোঝার সুবিধার জন্য ধরে নিলাম ৪ এর প্যারেন্ট ২। ২ থেকে ৫ এও যাওয়া যায় তাই ৫ এর ও প্যারেন্ট হবে ২।

০->-১

১->০

২->১

৩->১

৪->২

৫->২

এখন আমরা ডেস্টিনেশন নোড অর্থাৎ ৫ কে নেব তাকে একটি ভেক্টরে রাখব। তারপর তার প্যারেন্ট ২ এর কাছে যাব। ২ কে ভেক্টরে রাখব। ২ এর প্যারেন্ট এর কাছে যাব যা হচ্ছে ১। ১ কে ভেক্টরে রাখব ও ১ এর প্যারেন্ট এর কাছে যাব যা হচ্ছে ০। ০ কে ভেক্টরে রাখব এবং তার প্যারেন্ট যেহেতু -১ তখন এই আমরা কাজ শেষ করব।

এবার যদি ভেক্টরটি দেখি তাহলে পাব ৫->২->১->০। এই ভেক্টরকে রিভারস করে দিলেই আমরা আমাদের পাথ ০->১->২->৫। পেয়ে যাব।