(23 এপ্রিল 2025 (ভি 1) এ জমা দেওয়া হয়েছে, সর্বশেষ সংশোধিত 30 জুলাই 2025 (এই সংস্করণ, ভি 2))
রেন ডুয়ান এবং অন্যান্য 4 জন লেখক দ্বারা নির্দেশিত একক উত্সের সংক্ষিপ্ততম পথগুলির জন্য বাছাই বাধা ভাঙা শিরোনামে কাগজের একটি পিডিএফ দেখুন
পিডিএফ এইচটিএমএল দেখুন (পরীক্ষামূলক)
বিমূর্ত:আমরা তুলনা-যুক্ত মডেলটিতে বাস্তব অ-নেতিবাচক প্রান্তের ওজন সহ নির্দেশিত গ্রাফগুলিতে একক উত্সের সংক্ষিপ্ততম পাথ (এসএসএসপি) এর জন্য একটি নির্ধারক $ o (এম \ লগ^{2/3} n) $-সময় অ্যালগরিদম দিই। স্পার্স গ্রাফগুলিতে ডিজকস্ট্রার অ্যালগরিদমের সময় আবদ্ধ $ o (এম+এন \ লগ এন) ভাঙ্গার এটিই প্রথম ফলাফল, এটি দেখায় যে এসএসএসপির পক্ষে ডিজকস্ট্রার অ্যালগরিদম অনুকূল নয়।
জমা ইতিহাস
থেকে: রান ডুয়ান (ইমেল দেখুন)
(ভি 1)
বুধ, 23 এপ্রিল 2025 18:26:39 ইউটিসি (35 কেবি)
(ভি 2)
বুধ, 30 জুলাই 2025 11:02:48 ইউটিসি (49 কেবি)
