Shortest Path Recovery

প্রবলেমে যে সুডোকোডটি দেওয়া আছে সেটি বেলম্যান-ফোর্ড অ্যালগোরিদমের সুডোকোড। বেলম্যান-ফোর্ড অ্যালগোরিদমটি যদি n-1 বার চালানো হয়, তবে গ্রাফে শর্টেস্ট পাথ থাকলে তার সবগুলোই অ্যালগোরিদমটি বের করে ফেলতে পারবে। যেহেতু হারিয়ে যাওয়া গ্রাফটির এজগুলোর পরম মান ১০০০ এর মধ্যে, তাই গ্রাফের যে কোন শর্টেস্ট পাথের সর্বোচ্চ কত কস্ট হতে পারে সেটি সহজেই বের করা সম্ভব। এখানে উল্লেখ্য যে, কোন গ্রাফে যদি n টি নোড থাকে, তা হলে গ্রাফটির শর্টেস্ট পাথে সর্বোচ্চ n-1 টি এজ থাকতে পারে।

এছাড়াও বেলম্যান-ফোর্ডের সাহায্য গ্রাফের নেগেটিভ সাইকেলের অস্তিত্বও টের পাওয়া যায়। যদি n তম বারও অ্যালগোরিদমটি গ্রাফের শর্টেস্ট পাথ আপডেটের চেষ্টা করে, তা হলে বুঝতে হবে গ্রাফটিতে অন্তত একটি হলেও নেগেটিভ সাইকেল আছে। আমাদের প্রবলেমে যেহেতু মূল গ্রাফটি দেওয়া নেই, তাই এখানে কিছু সুক্ষ্ম কেস তৈরী হতে পারে, যা ১০০ পয়েন্ট পাবার সময় মাথায় রাখতে হবে। বলে রাখা ভালো যে, আসল গ্রাফটিতে কিন্তু সেলফ-লুপও থাকতে পারে।