Contraction hierarchies
কম্পিউটার বিজ্ঞানে, সংকোচনের শ্রেণিবিন্যাসের পদ্ধতি হল একটি গ্রাফের সংক্ষিপ্ততম পথ খুঁজে বের করার জন্য একটি গতি বাড়ানোর কৌশল। সবচেয়ে স্বজ্ঞাত প্রয়োগগুলি হল গাড়ি-নেভিগেশন সিস্টেমঃ একজন ব্যবহারকারী দ্রুততম সম্ভাব্য পথ ব্যবহার করে গাড়ি চালাতে চান। এখানে অপ্টিমাইজ করা মেট্রিক হল ভ্রমণের সময়। ছেদগুলি শীর্ষ দ্বারা প্রতিনিধিত্ব করা হয়, রাস্তার বিভাগগুলি তাদের প্রান্ত দ্বারা সংযুক্ত করে। প্রান্তের ওজন রাস্তার এই অংশটি ধরে গাড়ি চালাতে যে সময় লাগে তার প্রতিনিধিত্ব করে। থেকে একটি পথ হল প্রান্তের ক্রম (রাস্তার বিভাগ); সমস্ত সম্ভাব্য পথের মধ্যে প্রান্তের ওজনের ন্যূনতম যোগফল সহ সংক্ষিপ্ততম পথ। একটি গ্রাফের সংক্ষিপ্ততম পথটি ডিজকস্ট্রার অ্যালগরিদম ব্যবহার করে গণনা করা যেতে পারে তবে, রাস্তার নেটওয়ার্কগুলি লক্ষ লক্ষ শীর্ষ নিয়ে গঠিত, এটি অবাস্তব। সংকোচন শ্রেণিবিন্যাস হল একটি গতি-বৃদ্ধি পদ্ধতি যা সড়ক নেটওয়ার্কের প্রতিনিধিত্বকারী গ্রাফের বৈশিষ্ট্যগুলি কাজে লাগানোর জন্য অনুকূলিত। প্রিপ্রসেসিং পর্যায়ে শর্টকাট তৈরি করে গতি বৃদ্ধি করা হয় যা পরে "গুরুত্বহীন" শীর্ষগুলি এড়িয়ে যাওয়ার জন্য একটি সংক্ষিপ্ততম-পথ অনুসন্ধানের সময় ব্যবহার করা হয়। এটি এই পর্যবেক্ষণের উপর ভিত্তি করে যে সড়ক নেটওয়ার্কগুলি অত্যন্ত শ্রেণিবদ্ধ। কিছু ছেদ, উদাহরণস্বরূপ হাইওয়ে জংশন, "আরও গুরুত্বপূর্ণ" এবং শ্রেণিবিন্যাসে উচ্চতর, উদাহরণস্বরূপ একটি জংশন যা একটি ডেড এন্ডে যায়। শর্টকাটগুলি দুটি গুরুত্বপূর্ণ সংযোগস্থলের মধ্যে পূর্ব-সংগণিত দূরত্ব সংরক্ষণ করতে ব্যবহার করা যেতে পারে যাতে অনুসন্ধানের সময় অ্যালগরিদমকে এই সংযোগস্থলগুলির মধ্যে সম্পূর্ণ পথ বিবেচনা করতে না হয়। সংকোচন শ্রেণিবিন্যাসগুলি জানে না যে মানুষ কোন রাস্তাগুলিকে "গুরুত্বপূর্ণ" বলে মনে করে (যেমন। হাইওয়ে), তবে এগুলি ইনপুট হিসাবে গ্রাফ সরবরাহ করা হয় এবং হিউরিস্টিক্স ব্যবহার করে শীর্ষগুলিকে গুরুত্ব দিতে সক্ষম হয়। সংকোচন শ্রেণিবিন্যাসগুলি কেবল গাড়ি-নেভিগেশন সিস্টেমে স্পিড-আপ অ্যালগরিদমগুলিতে প্রয়োগ করা হয় না, তবে ওয়েব-ভিত্তিক রুট পরিকল্পনাকারী, ট্র্যাফিক সিমুলেশন এবং লজিস্টিক অপ্টিমাইজেশনেও প্রয়োগ করা হয়। অ্যালগরিদমের বাস্তবায়নগুলি ওপেন সোর্স সফ্টওয়্যার হিসাবে সর্বজনীনভাবে উপলব্ধ। অ্যালগরিদম সংকোচন শ্রেণিবিন্যাস (সিএইচ) অ্যালগরিদম হল সংক্ষিপ্ততম পথ সমস্যার জন্য একটি দ্বি-পর্যায়ের পদ্ধতি যা একটি প্রাক প্রক্রিয়াকরণ পর্যায় এবং একটি অনুসন্ধান পর্যায় নিয়ে গঠিত। যেহেতু সড়ক নেটওয়ার্কগুলি কদাচিৎ পরিবর্তিত হয়, তাই প্রশ্নের উত্তর দেওয়ার আগে কিছু গণনা আগে থেকে গণনা করার জন্য আরও বেশি সময় (সেকেন্ড থেকে ঘন্টা) ব্যবহার করা যেতে পারে। এই পূর্ব-সংগণিত তথ্য ব্যবহার করে, অনেক প্রশ্নের উত্তর খুব কম সময় (মাইক্রোসেকেন্ড) নিয়ে দেওয়া যেতে পারে। এই গতি বাড়ানোর জন্য সিএইচ শর্টকাটগুলির উপর নির্ভর করে। একটি শর্টকাট দুটি শীর্ষকে সংযুক্ত করে এবং মূল গ্রাফের সংলগ্ন নয়। এর প্রান্তের ওজন হল সংক্ষিপ্ততম পথের প্রান্তের ওজনের সমষ্টি। একটি মহাসড়ক দ্বারা সংযুক্ত দুটি বড় শহরের কথা বিবেচনা করুন। এই দুটি শহরের মধ্যে, ছোট গ্রাম এবং শহরতলির দিকে যাওয়ার জন্য প্রচুর সংযোগস্থল রয়েছে। বেশিরভাগ চালক এক শহর থেকে অন্য শহরে যেতে চান-সম্ভবত একটি বৃহত্তর পথের অংশ হিসাবে-এবং পথে প্রস্থানের একটিও নিতে চান না। এই রাস্তার বিন্যাসের প্রতিনিধিত্বকারী গ্রাফে, প্রতিটি ছেদকে একটি নোড দ্বারা প্রতিনিধিত্ব করা হয় এবং পার্শ্ববর্তী ছেদগুলির মধ্যে প্রান্ত তৈরি করা হয়। এই দুটি শহরের মধ্যে দূরত্ব গণনা করার জন্য, অ্যালগরিদমকে তাদের দৈর্ঘ্য যোগ করে পথের সমস্ত প্রান্ত অতিক্রম করতে হবে। এই দূরত্বটি একবার প্রাক-গণনা করা এবং দুটি বড় শহরের মধ্যে তৈরি একটি অতিরিক্ত প্রান্তে সংরক্ষণ করা প্রতিটি সময় এই মহাসড়কটিকে একটি প্রশ্নের মধ্যে মূল্যায়ন করতে হবে। এই অতিরিক্ত প্রান্তটিকে "শর্টকাট" বলা হয় এবং বাস্তব জগতে এর কোনও প্রতিরূপ নেই। সংকোচন শ্রেণিবিন্যাস অ্যালগরিদমের রাস্তার ধরন সম্পর্কে কোনও জ্ঞান নেই তবে শুধুমাত্র ইনপুট হিসাবে গ্রাফ ব্যবহার করে কোন শর্টকাটগুলি তৈরি করতে হবে তা নির্ধারণ করতে সক্ষম। প্রাকপ্রক্রিয়াকরণ পর্যায় সিএইচ অ্যালগরিদম অনুসন্ধানের স্থান হ্রাস করার জন্য প্রাকপ্রক্রিয়াকরণ পর্যায়ে তৈরি শর্টকাটগুলির উপর নির্ভর করে-অর্থাৎ অনুসন্ধানের সময় সিএইচ-কে কতগুলি শীর্ষ দেখতে হবে। এটি অর্জনের জন্য, পুনরাবৃত্তিমূলক শীর্ষ সংকোচন সঞ্চালিত হয়। একটি শীর্ষবিন্দু সঙ্কুচিত হওয়ার সময় এটি সাময়িকভাবে গ্রাফ থেকে সরানো হয় এবং প্রতিটি জোড়া পার্শ্ববর্তী শীর্ষগুলির মধ্যে একটি শর্টকাট তৈরি করা হয় যদি থেকে সংক্ষিপ্ততম পথটি থাকে। এবং এর মধ্যে সংক্ষিপ্ততম পথটি রয়েছে কিনা তা নির্ধারণের প্রক্রিয়াকে সাক্ষী অনুসন্ধান বলা হয়। উদাহরণস্বরূপ, শুধুমাত্র এখনও চুক্তিবদ্ধ নয় এমন নোড ব্যবহার করে ফরওয়ার্ড সার্চ ব্যবহার করার একটি পথ গণনা করে এটি সম্পাদন করা যেতে পারে। নোড অর্ডার ইনপুট গ্রাফের শীর্ষগুলি এমনভাবে সংকুচিত করতে হবে যা সংকোচনের মাধ্যমে গ্রাফে যোগ করা প্রান্তের সংখ্যাকে কমিয়ে দেয়। যেহেতু সর্বোত্তম নোড অর্ডারিং এনপি-সম্পূর্ণ, তাই হিউরিস্টিক্স ব্যবহার করা হয়। নীচে-উপরে এবং উপরে-নিচে হিউরিস্টিক্স রয়েছে। একদিকে, গণনামূলকভাবে সস্তা বটম-আপ হিউরিস্টিক্স একটি লোভী পদ্ধতিতে শীর্ষগুলি সঙ্কুচিত করার ক্রম নির্ধারণ করে; এর অর্থ হল ক্রমটি আগে থেকে জানা যায় না বরং পূর্ববর্তী সংকোচন সম্পন্ন হওয়ার পরে সংকোচনের জন্য পরবর্তী নোডটি নির্বাচন করা হয়। অন্যদিকে টপ-ডাউন হিউরিস্টিক্স প্রথম নোড সংকুচিত হওয়ার আগে পুরো নোডের ক্রমটি প্রাক-গণনা করে। এটি আরও ভাল ফলাফল দেয় তবে আরও প্রাক প্রক্রিয়াকরণের সময় প্রয়োজন। বটম-আপ হিউরিস্টিক্সে, সংকোচনের জন্য পরবর্তী শীর্ষ নির্বাচন করতে কারণগুলির একটি সংমিশ্রণ ব্যবহার করা হয়। যেহেতু শর্টকাটগুলির সংখ্যা প্রাথমিক ফ্যাক্টর যা প্রি-প্রসেসিং এবং কোয়েরি রানটাইম নির্ধারণ করে, তাই আমরা এটিকে যতটা সম্ভব ছোট রাখতে চাই। সংকোচনের জন্য পরবর্তী নোড নির্বাচন করার জন্য সবচেয়ে গুরুত্বপূর্ণ শব্দটি হল একটি নোড সংকুচিত করার সময় যোগ করা প্রান্তের মোট সংখ্যা। এটি সংজ্ঞায়িত করা হয় যে শর্টকাটগুলির সংখ্যা কোথায় তৈরি করা হবে যদি সংকুচিত করা হয় এবং প্রান্তের সংখ্যা যেখানে ঘটে। শুধুমাত্র এই মানদণ্ডটি ব্যবহার করে, একটি রৈখিক পথের ফলে একটি রৈখিক শ্রেণিবিন্যাস (অনেক স্তর) তৈরি হবে এবং কোনও শর্টকাট তৈরি হবে না। ইতিমধ্যে সংকুচিত নিকটবর্তী শীর্ষগুলির সংখ্যা বিবেচনা করে, একটি অভিন্ন সংকোচন এবং একটি সমতল শ্রেণিবিন্যাস (কম স্তর) অর্জন করা হয়। উদাহরণস্বরূপ, প্রতিটি নোডের জন্য একটি কাউন্টার বজায় রেখে এটি করা যেতে পারে যা প্রতিবার প্রতিবেশী শীর্ষবিন্দু সংকুচিত হওয়ার সময় বৃদ্ধি করা হয়। তারপরে উচ্চতর কাউন্টারযুক্ত নোডের তুলনায় নিম্ন কাউন্টারযুক্ত নোডগুলি পছন্দ করা হয়। অন্যদিকে, টপ-ডাউন হিউরিস্টিক্স আরও ভাল ফলাফল দেয় তবে আরও প্রাক প্রক্রিয়াকরণের সময় প্রয়োজন। তারা কয়েকটি সংক্ষিপ্ততম পথের জন্য প্রয়োজনীয় শীর্ষগুলির তুলনায় অনেক সংক্ষিপ্ততম পথের অংশগুলিকে আরও গুরুত্বপূর্ণ হিসাবে শ্রেণীবদ্ধ করে। নেস্টেড বিচ্ছিন্নকরণ ব্যবহার করে এটি আনুমানিক করা যেতে পারে। একটি নেস্টেড বিচ্ছিন্নকরণ গণনা করার জন্য, একটি পুনরাবৃত্তিমূলকভাবে একটি গ্রাফকে দুটি অংশে বিভক্ত করে, যা পরে দুটি অংশে বিভক্ত করা হয় ইত্যাদি। অর্থাৎ, নোডের একটি উপসেট খুঁজে বের করুন যা গ্রাফ থেকে সরানো হলে প্রায় সমান আকারের দুটি বিচ্ছিন্ন অংশে বিভক্ত হয়। সমস্ত নোডকে শেষ পর্যন্ত নোড অর্ডারে রাখুন এবং তারপরে পুনরাবৃত্তিমূলকভাবে নেস্টেড বিচ্ছিন্নতা গণনা করুন এবং, অন্তর্দৃষ্টিটি হ 'ল গ্রাফের অর্ধেক থেকে গ্রাফের অন্য অর্ধেক পর্যন্ত সমস্ত প্রশ্নের জন্য ছোট বিভাজকের মধ্য দিয়ে যেতে হবে এবং তাই এই বিভাজকের নোডগুলি অত্যন্ত গুরুত্বপূর্ণ। নেস্টেড বিচ্ছিন্নকরণগুলি তাদের ছোট বিভাজকের কারণে সড়ক নেটওয়ার্কে দক্ষতার সাথে গণনা করা যেতে পারে। প্রশ্ন পর্যায় প্রশ্ন পর্যায়ে, প্রারম্ভিক নোড থেকে শুরু করে একটি দ্বিমুখী অনুসন্ধান করা হয় এবং মূল গ্রাফের লক্ষ্য নোডটি প্রাক প্রক্রিয়াকরণ পর্যায়ে তৈরি শর্টকাট দ্বারা বর্ধিত করা হয়। এবং এর মধ্যে সংক্ষিপ্ততম পথের সবচেয়ে গুরুত্বপূর্ণ শীর্ষটি হয় বা নিজেরাই বা এবং উভয়ের চেয়ে বেশি গুরুত্বপূর্ণ হবে। অতএব, মূল গ্রাফ এবং হোল্ডের সংক্ষিপ্ততম পথে মিনিমাইজিং ভার্টেক্স রয়েছে। এটি, কিভাবে শর্টকাট তৈরি করা হয় তার সংমিশ্রণে, এর অর্থ হল যে সামনের এবং পিছনের অনুসন্ধান উভয়কেই কেবল শ্রেণিবিন্যাসে আরও গুরুত্বপূর্ণ নোডের (উপরের দিকে) দিকে নিয়ে যাওয়ার প্রান্তগুলি শিথিল করতে হবে যা অনুসন্ধানের স্থানটিকে ছোট রাখে। সমস্ত আপ-(ডাউন-আপ)-ডাউন পথে, অভ্যন্তরীণ (ডাউন-আপ) বাদ দেওয়া যেতে পারে, কারণ প্রাক প্রক্রিয়াকরণ পর্যায়ে একটি শর্টকাট তৈরি করা হয়েছে। পথ পুনরুদ্ধার একটি সিএইচ প্রশ্ন, যেমন উপরে বর্ণিত হয়েছে, সময় বা দূরত্ব প্রদান করে কিন্তু প্রকৃত পথ নয়। সংক্ষিপ্ততম পথের প্রান্তের (রাস্তা) তালিকা পেতে, নেওয়া শর্টকাটগুলি আনপ্যাক করতে হবে। প্রতিটি শর্টকাট হল দুটি প্রান্তের সংহতকরণঃ হয় মূল গ্রাফের দুটি প্রান্ত, অথবা দুটি শর্টকাট, অথবা একটি মূল প্রান্ত এবং একটি শর্টকাট। সংকোচনের সময় প্রতিটি শর্টকাটের মাঝের শীর্ষটি সংরক্ষণ করা সংক্ষিপ্ততম পথের রৈখিক-সময় পুনরাবৃত্তিমূলক আনপ্যাকিংকে সক্ষম করে। কাস্টমাইজড সংকোচন শ্রেণিবিন্যাস যদি প্রান্তের ওজনগুলি নেটওয়ার্ক টপোলজির তুলনায় প্রায়শই পরিবর্তিত হয়, তবে প্রাক প্রক্রিয়াকরণ এবং অনুসন্ধান পর্যায়ের মধ্যে একটি কাস্টমাইজেশন পর্যায় অন্তর্ভুক্ত করে সিএইচকে তিন-পর্যায়ের পদ্ধতিতে প্রসারিত করা যেতে পারে। এটি উদাহরণস্বরূপ স্বল্পতম দূরত্ব এবং স্বল্পতম সময়ের মধ্যে পরিবর্তন করতে বা বর্তমান ট্রাফিক তথ্যের পাশাপাশি নির্দিষ্ট ধরনের রাস্তা (ফেরি, মহাসড়ক) এড়ানোর মতো ব্যবহারকারীর পছন্দগুলি অন্তর্ভুক্ত করতে ব্যবহার করা যেতে পারে। প্রাক প্রক্রিয়াকরণ পর্যায়ে, বেশিরভাগ রানটাইম নোডগুলি সংকুচিত হওয়ার ক্রম গণনা করতে ব্যয় করা হয়। প্রাক প্রক্রিয়াকরণ পর্যায়ে সংকোচন ক্রিয়াকলাপের এই ক্রমটি পরে কাস্টমাইজেশন পর্যায়ে যখন প্রয়োজন হয় তখন সংরক্ষণ করা যেতে পারে। প্রতিবার মেট্রিকটি কাস্টমাইজ করা হলে, কাস্টম মেট্রিক ব্যবহার করে সঞ্চিত ক্রমে সংকোচনগুলি দক্ষতার সাথে প্রয়োগ করা যেতে পারে। উপরন্তু, নতুন প্রান্তের ওজনের উপর নির্ভর করে কিছু শর্টকাট পুনরায় গণনা করার প্রয়োজন হতে পারে। এটি কাজ করার জন্য, সংকোচন ক্রমটি মেট্রিক-স্বাধীন নেস্টেড বিভাজন ব্যবহার করে গণনা করতে হবে। উপরে বর্ণিত এক্সটেনশন এবং অ্যাপ্লিকেশন সিএইচএস একটি প্রারম্ভিক নোড থেকে একটি লক্ষ্য নোড পর্যন্ত সংক্ষিপ্ততম পথের জন্য অনুসন্ধান করে। এটিকে এক-থেকে-এক সংক্ষিপ্ততম পথ বলা হয় এবং উদাহরণস্বরূপ গাড়ি-নেভিগেশন সিস্টেমে এটি ব্যবহৃত হয়। অন্যান্য প্রয়োগগুলির মধ্যে রয়েছে রাস্তার অংশগুলিতে জিপিএস ট্রেসগুলি মেলানো এবং ট্র্যাফিক সিমুলেটরগুলির গতি বাড়ানো যা একটি নেটওয়ার্কের সমস্ত চালকদের দ্বারা নেওয়া সম্ভাব্য রুটগুলি বিবেচনা করতে হবে। পথের পূর্বাভাসে একটি যানবাহন তার বর্তমান এবং অতীত অবস্থানগুলি তার প্রারম্ভিক বিন্দু থেকে যে কোনও সম্ভাব্য লক্ষ্যে যাওয়ার সংক্ষিপ্ততম পথের সাথে কতটা একমত তা গণনা করে অনুমান করার চেষ্টা করে। সিএইচএস ব্যবহার করে এটি দক্ষতার সাথে করা যেতে পারে। এক-থেকে-অনেক পরিস্থিতিতে, একটি প্রারম্ভিক নোড এবং লক্ষ্য নোডের একটি সেট দেওয়া হয় এবং সকলের জন্য দূরত্ব গণনা করতে হয়। এক-থেকে-অনেক প্রশ্নের জন্য সবচেয়ে বিশিষ্ট অ্যাপ্লিকেশন হল পয়েন্ট-অফ-ইন্টারেস্ট সার্চ। সাধারণ উদাহরণগুলির মধ্যে রয়েছে নিকটতম গ্যাস স্টেশন, রেস্তোরাঁ বা ডাকঘর খুঁজে বের করার জন্য ভৌগলিক দূরত্বের পরিবর্তে প্রকৃত ভ্রমণের সময়কে মেট্রিক হিসাবে ব্যবহার করা। অনেক থেকে অনেক সংক্ষিপ্ততম পথের দৃশ্যে, প্রারম্ভিক নোডের একটি সেট এবং লক্ষ্য নোডের একটি সেট দেওয়া হয় এবং সকলের জন্য দূরত্ব গণনা করতে হয়। এটি উদাহরণস্বরূপ লজিস্টিক অ্যাপ্লিকেশনগুলিতে ব্যবহৃত হয়। সিএইচএস নিম্নলিখিত পদ্ধতিতে অনেক-থেকে-অনেক প্রশ্নের মধ্যে প্রসারিত করা যেতে পারে। প্রথমে, প্রত্যেকটি থেকে পিছনের দিকে উপরের দিকে অনুসন্ধান করুন। এই অনুসন্ধানের সময় স্ক্যান করা প্রতিটি শীর্ষের জন্য, একটি বালতিতে একটি দোকান। তারপরে, প্রতিটি খালি বালতি পরীক্ষা করে, সংশ্লিষ্ট শীর্ষের উপরের পথটি কোনও সর্বোত্তম দূরত্বের উন্নতি করে কিনা তা পরীক্ষা করে, প্রতিটি থেকে একটি সামনের দিকে অনুসন্ধান চালানো হয়। অর্থাৎ, যদি থাকে। কিছু প্রয়োগের জন্য এমনকি এক-থেকে-সমস্ত গণনার প্রয়োজন হয়, অর্থাৎ, একটি উৎস শীর্ষ থেকে গ্রাফের অন্যান্য সমস্ত শীর্ষে দূরত্ব খুঁজে বের করা। যেহেতু ডিজকস্ট্রার অ্যালগরিদম প্রতিটি প্রান্তে ঠিক একবার যায় এবং তাই রৈখিক সময়ে চলে এটি তাত্ত্বিকভাবে সর্বোত্তম। যাইহোক, ডিজকস্ট্রার অ্যালগরিদমটি সমান্তরাল করা কঠিন এবং এর খারাপ অবস্থানের কারণে ক্যাশে-সর্বোত্তম নয়। সিএইচএস আরও ক্যাশে-সর্বোত্তম বাস্তবায়নের জন্য ব্যবহার করা যেতে পারে। এর জন্য, শর্টকাট-সমৃদ্ধ গ্রাফের সমস্ত নোডের উপর একটি নিম্নমুখী স্ক্যানের পরে একটি সামনের দিকে অনুসন্ধান করা হয়। পরবর্তী অপারেশনটি মেমরির মাধ্যমে রৈখিক পদ্ধতিতে স্ক্যান করে, কারণ নোডগুলি গুরুত্বের ক্রম হ্রাস করে প্রক্রিয়াজাত করা হয় এবং তাই সেই অনুযায়ী মেমরিতে স্থাপন করা যেতে পারে। লক্ষ্য করুন, এটি সম্ভব কারণ দ্বিতীয় পর্যায়ে নোডগুলি যে ক্রমে প্রক্রিয়াজাত করা হয় তা উৎস নোড থেকে স্বাধীন। উৎপাদনে, গাড়ি-নেভিগেশন সিস্টেমগুলি পূর্বাভাস ট্রাফিক তথ্য ব্যবহার করে দ্রুততম ভ্রমণ রুট গণনা করতে এবং বিকল্প রুট প্রদর্শন করতে সক্ষম হওয়া উচিত। উভয়ই সিএইচএস ব্যবহার করে করা যেতে পারে। প্রথমটিকে সময়-নির্ভর নেটওয়ার্কগুলির সাথে রাউটিং বলা হয় যেখানে একটি প্রদত্ত প্রান্তের ভ্রমণের সময় আর স্থির থাকে না বরং প্রান্তে প্রবেশ করার সময় দিনের সময়ের একটি ফাংশন। বিকল্প পথগুলি মসৃণ-চেহারার হতে হবে, সংক্ষিপ্ততম পথের থেকে উল্লেখযোগ্যভাবে আলাদা তবে উল্লেখযোগ্যভাবে দীর্ঘ নয়। সিএইচএস একই সময়ে একাধিক মেট্রিক অপ্টিমাইজ করার জন্য প্রসারিত করা যেতে পারে; এটিকে বহু-মানদণ্ডের রুট পরিকল্পনা বলা হয়। উদাহরণস্বরূপ, ভ্রমণের খরচ এবং সময় উভয়ই কমানো যেতে পারে। আরেকটি উদাহরণ হল বৈদ্যুতিক যানবাহন যার জন্য উপলব্ধ ব্যাটারি চার্জ বৈধ পথগুলিকে সীমাবদ্ধ করে কারণ ব্যাটারি খালি নাও চলতে পারে। তত্ত্ব সংকোচন শ্রেণিবিন্যাসের প্রাক প্রক্রিয়াকরণ এবং অনুসন্ধান কর্মক্ষমতার উপর বেশ কয়েকটি সীমা প্রতিষ্ঠিত হয়েছে। নিম্নে গ্রাফের শীর্ষগুলির সংখ্যা, প্রান্তের সংখ্যা, মহাসড়কের মাত্রা, গ্রাফের ব্যাস, গাছের গভীরতা এবং গাছের প্রস্থ ধরা যাক। সংকোচন শ্রেণিবিন্যাস কর্মক্ষমতার প্রথম বিশ্লেষণ আংশিকভাবে মহাসড়কের মাত্রা নামে পরিচিত একটি পরিমাণের উপর নির্ভর করে। যদিও এই পরিমাণের সংজ্ঞাটি প্রযুক্তিগত, স্বজ্ঞাতভাবে একটি গ্রাফের একটি ছোট মহাসড়কের মাত্রা থাকে যদি প্রত্যেকটির জন্য শীর্ষগুলির একটি বিরল সেট থাকে যাতে দৈর্ঘ্যের প্রতিটি সংক্ষিপ্ততম পথে থেকে একটি শীর্ষ অন্তর্ভুক্ত থাকে। মহাসড়কের মাত্রার সঠিক মান গণনা করা এনপি-হার্ড এবং ডাব্লু [1]-হার্ড, তবে গ্রিডের জন্য এটি হাইওয়ের মাত্রা হিসাবে পরিচিত। কাস্টমাইজেবল কন্ট্রাকশন হায়ারার্কি লাইনে একটি বিকল্প বিশ্লেষণ উপস্থাপন করা হয়েছিল। অনুসন্ধানের চলমান সময়গুলি দ্বারা সীমাবদ্ধ করা যেতে পারে। যেহেতু গাছের গভীরতা গাছ-প্রস্থের পরিপ্রেক্ষিতে সীমাবদ্ধ করা যেতে পারে, তাই এটি একটি বৈধ উপরের সীমানাও। প্রধান উৎস হল তবে সবচেয়ে খারাপ ক্ষেত্রে চলমান সময়ের পরিণতি আরও ভালভাবে বিস্তারিত করা হয়েছে। প্রাকপ্রক্রিয়াকরণ কর্মক্ষমতা প্রশ্ন কর্মক্ষমতা রেফারেন্স বাহ্যিক লিঙ্ক ওপেন সোর্স বাস্তবায়ন https://www.graphhopper.com https://github.com/ifsttar/Tempus https://github.com/RoutingKit/RoutingKit http://project-osrm.org http://www.opentripplanner.org গ্রাফ অ্যালগরিদম অনুসন্ধান অ্যালগরিদম রাউটিং অ্যালগরিদম