একটি একক শর্টেস্ট পাথ দেওয়ার বদলে, ইয়েনস k-শর্টেস্ট পাথ অ্যালগরিদম k সংখ্যক শর্টেস্ট পাথ দেয় যাতে আমরা দ্বিতীয় শর্টেস্ট পাথ, তৃতীয় শর্টেস্ট পাথ ইত্যাদি পেতে পারি।
একটি পরিস্থিতি বিবেচনা করুন যেখানে আমাদের স্থান A থেকে স্থান B-এ যেতে হবে এবং স্থান A এবং B-এর মধ্যে একাধিক রুট উপলব্ধ, কিন্তু আমাদের শর্টেস্ট পাথ খুঁজে বের করতে হবে এবং সেই পথগুলো উপেক্ষা করতে হবে যা টাইম কমপ্লেক্সিটির দৃষ্টিতে কম বিবেচিত হয়েছে গন্তব্যে পৌঁছাতে।
একটি উদাহরণ দিয়ে বুঝি-
দिए गए উদাহরণটিকে একটি ব্রিজ হিসেবে বিবেচনা করুন যার শিখর B। যদি কেউ A থেকে C-এ ব্রিজ পার করতে চায়, তবে কেউ শিখরে যেতে চাবে না ব্রিজ পার করার জন্য। তাহলে A থেকে C-এ যেতে কিছুটা লম্বা পথ হবে।
শর্টেস্ট পাথ পাওয়ার একাধিক উপায় আছে। কিন্তু আমাদের (k-1) পর্যন্ত শর্টেস্ট পাথ খুঁজে বের করতে হবে।
k-শর্টেস্ট পাথের জন্য অ্যালগরিদম
query= "" MATCH(start: place{id:source}),*end: Place {Id:destination}) Call algo.kshortestPaths.stream(start,end,10, "distance") Yield nodeIDs, path costs, index Return index. [node in algo.getNodeByID(nodeId[1…..-1]) | node.id] aS, Reduce (acc=0.0, cost in costs | acc+cost ) as total cost "" params= {"source": Alex,Destination: "US"} With driver.selection() as session: Row session.run(query, params) df = pd.DataFrame[dict(record) for record in rows]) pd.set_option('max_colwidth', 100) display(df)