Contraction hierarchies
કોમ્પ્યુટર વિજ્ઞાનમાં, સંકોચન પદાનુક્રમની પદ્ધતિ એ આલેખમાં સૌથી ટૂંકો માર્ગ શોધવા માટેની ઝડપ વધારવાની તકનીક છે. સૌથી વધુ સાહજિક એપ્લિકેશન્સ કાર-નેવિગેશન સિસ્ટમ્સ છેઃ વપરાશકર્તા શક્ય તેટલા ઝડપી માર્ગનો ઉપયોગ કરીને વાહન ચલાવવા માંગે છે. અહીં ઓપ્ટિમાઇઝ કરેલ મેટ્રિક એ મુસાફરીનો સમય છે. આંતરછેદો શિરોબિંદુઓ દ્વારા રજૂ થાય છે, રસ્તાના વિભાગો તેમને ધાર દ્વારા જોડે છે. ધારનું વજન રસ્તાના આ ભાગમાં વાહન ચલાવવામાં લાગતા સમયનું પ્રતિનિધિત્વ કરે છે. થી તરફનો માર્ગ એ કિનારીઓનો ક્રમ (રસ્તાના વિભાગો) છે; સૌથી ટૂંકો માર્ગ એ છે કે જેમાં તમામ સંભવિત માર્ગોમાં કિનારી વજનનો ઓછામાં ઓછો સરવાળો હોય. આલેખમાં સૌથી ટૂંકો માર્ગ ડિજ્ક્સ્ટ્રાના અલ્ગોરિધમનો ઉપયોગ કરીને ગણતરી કરી શકાય છે, પરંતુ રોડ નેટવર્કમાં લાખો શિરોબિંદુઓ હોય છે તે જોતાં, આ અવ્યવહારુ છે. સંકોચન પદાનુક્રમ એ સ્પીડ-અપ પદ્ધતિ છે જે માર્ગ નેટવર્કનું પ્રતિનિધિત્વ કરતા આલેખના ગુણધર્મોનો ઉપયોગ કરવા માટે અનુકૂળ છે. સ્પીડ-અપ પ્રીપ્રોસેસિંગ તબક્કામાં શોર્ટકટ્સ બનાવીને પ્રાપ્ત થાય છે જેનો ઉપયોગ પછી "બિનમહત્વપૂર્ણ" શિરોબિંદુઓને છોડવા માટે ટૂંકી-પાથ ક્વેરી દરમિયાન થાય છે. આ અવલોકન પર આધારિત છે કે માર્ગ નેટવર્ક અત્યંત અધિક્રમિક છે. કેટલાક આંતરછેદો, ઉદાહરણ તરીકે ધોરીમાર્ગ જંકશન, "વધુ મહત્વપૂર્ણ" છે અને ઉદાહરણ તરીકે અંતિમ અંત તરફ દોરી જતા જંકશન કરતાં પદાનુક્રમમાં ઊંચા છે. શોર્ટકટ્સનો ઉપયોગ બે મહત્વપૂર્ણ જંકશન વચ્ચેના પૂર્વગણતરી કરેલ અંતરને બચાવવા માટે થઈ શકે છે, જેમ કે અલ્ગોરિધમને ક્વેરી સમયે આ જંકશન વચ્ચેના સંપૂર્ણ માર્ગને ધ્યાનમાં લેવાની જરૂર નથી. સંકોચન પદાનુક્રમોને ખબર નથી કે મનુષ્ય કયા રસ્તાઓને "મહત્વપૂર્ણ" માને છે (દા. ત. ધોરીમાર્ગો), પરંતુ તેઓ ઇનપુટ તરીકે આલેખ સાથે પ્રદાન કરવામાં આવે છે અને હ્યુરિસ્ટિક્સનો ઉપયોગ કરીને શિરોબિંદુઓને મહત્વ સોંપવામાં સક્ષમ છે. સંકોચન પદાનુક્રમ માત્ર કાર-નેવિગેશન પ્રણાલીઓમાં સ્પીડ-અપ અલ્ગોરિધમ્સ પર જ નહીં પરંતુ વેબ-આધારિત રૂટ પ્લાનર્સ, ટ્રાફિક સિમ્યુલેશન અને લોજિસ્ટિક્સ ઓપ્ટિમાઇઝેશનમાં પણ લાગુ કરવામાં આવે છે. અલ્ગોરિધમનો અમલ ઓપન સોર્સ સોફ્ટવેર તરીકે જાહેરમાં ઉપલબ્ધ છે. અલ્ગોરિધમ સંકોચન પદાનુક્રમ (CH) અલ્ગોરિધમ એ પ્રીપ્રોસેસિંગ તબક્કો અને ક્વેરી તબક્કાનો સમાવેશ કરતી ટૂંકી પાથ સમસ્યા માટે બે તબક્કાનો અભિગમ છે. જેમ જેમ માર્ગ નેટવર્ક અવારનવાર બદલાતું રહે છે, તેમ તેમ પ્રશ્નોના જવાબ આપતા પહેલા કેટલીક ગણતરીઓ અગાઉથી કરવા માટે વધુ સમય (સેકન્ડથી કલાક) નો ઉપયોગ કરી શકાય છે. આ પૂર્વગણતરીકૃત માહિતીનો ઉપયોગ કરીને, ઘણા પ્રશ્નોના જવાબ ખૂબ જ ઓછા સમય (માઇક્રોસેકન્ડ્સ) માં આપી શકાય છે. આ ઝડપ વધારવા માટે CHs શોર્ટકટ્સ પર આધાર રાખે છે. એક શોર્ટકટ બે શિરોબિંદુઓને જોડે છે અને મૂળ આલેખમાં અડીને નથી. તેની ધારનું વજન એ ટૂંકા માર્ગ પરના ધાર વજનનો સરવાળો છે. ધોરીમાર્ગ દ્વારા જોડાયેલા બે મોટા શહેરોનો વિચાર કરો. આ બે શહેરો વચ્ચે, નાના ગામો અને ઉપનગરો તરફ દોરી જતા ઘણા જંકશન છે. મોટાભાગના ડ્રાઇવરો એક શહેરથી બીજા શહેરમાં જવા માંગે છે-કદાચ મોટા માર્ગના ભાગ રૂપે-અને રસ્તામાં બહાર નીકળતા માર્ગોમાંથી એક પણ લેવા માંગતા નથી. આ રોડ લેઆઉટને રજૂ કરતા આલેખમાં, દરેક આંતરછેદને નોડ દ્વારા રજૂ કરવામાં આવે છે અને ધાર પડોશી આંતરછેદો વચ્ચે બનાવવામાં આવે છે. આ બે શહેરો વચ્ચેના અંતરની ગણતરી કરવા માટે, અલ્ગોરિધમે રસ્તાની તમામ ધારને પાર કરવી પડશે, તેમની લંબાઈ વધારવી પડશે. એકવાર આ અંતરની પૂર્વ ગણતરી કરવાથી અને તેને બે મોટા શહેરો વચ્ચે બનાવેલી વધારાની ધારમાં સંગ્રહિત કરવાથી દરેક વખતે જ્યારે આ ધોરીમાર્ગનું મૂલ્યાંકન ક્વેરીમાં કરવું પડે ત્યારે ગણતરીની બચત થશે. આ વધારાની ધારને "શોર્ટકટ" કહેવામાં આવે છે અને વાસ્તવિક દુનિયામાં તેનો કોઈ સમકક્ષ નથી. સંકોચન પદાનુક્રમના અલ્ગોરિધમને રસ્તાના પ્રકારો વિશે કોઈ જાણકારી નથી પરંતુ ઇનપુટ તરીકે એકલા ગ્રાફનો ઉપયોગ કરીને કયા શોર્ટકટ્સ બનાવવાના છે તે નક્કી કરવામાં સક્ષમ છે. પ્રીપ્રોસેસિંગ તબક્કો CH અલ્ગોરિધમ શોધની જગ્યા ઘટાડવા માટે પ્રીપ્રોસેસિંગ તબક્કામાં બનાવેલા શોર્ટકટ્સ પર આધાર રાખે છે-એટલે કે ક્વેરી સમયે CH એ જોવાના શિરોબિંદુઓની સંખ્યા. આ હાંસલ કરવા માટે, પુનરાવર્તિત શિરોબિંદુ સંકોચન કરવામાં આવે છે. જ્યારે શિરોબિંદુ સંકોચાય છે ત્યારે તેને અસ્થાયી રૂપે આલેખમાંથી દૂર કરવામાં આવે છે, અને પડોશી શિરોબિંદુઓની દરેક જોડી વચ્ચે એક શોર્ટકટ બનાવવામાં આવે છે જો તે સૌથી ટૂંકો માર્ગ ધરાવે છે. અને વચ્ચેનો સૌથી ટૂંકો માર્ગ છે કે નહીં તે નક્કી કરવાની પ્રક્રિયાને સાક્ષી શોધ કહેવામાં આવે છે. તે ઉદાહરણ તરીકે માત્ર હજુ સુધી સંકુચિત નોડ્સનો ઉપયોગ કરીને ફોરવર્ડ સર્ચનો ઉપયોગ કરીને પાથની ગણતરી કરીને કરી શકાય છે. નોડ ક્રમ ઇનપુટ ગ્રાફના શિરોબિંદુઓને એવી રીતે સંકુચિત કરવા પડે છે કે જે સંકોચન દ્વારા ગ્રાફમાં ઉમેરવામાં આવેલી ધારની સંખ્યાને ઘટાડે. શ્રેષ્ઠ નોડ ક્રમ NP-પૂર્ણ હોવાથી, હ્યુરિસ્ટિક્સનો ઉપયોગ થાય છે. બોટમ-અપ અને ટોપ-ડાઉન હ્યુરિસ્ટિક્સ અસ્તિત્વ ધરાવે છે. એક તરફ, કોમ્પ્યુટેશનલ રીતે સસ્તું બોટમ-અપ હ્યુરિસ્ટિક્સ લોભી રીતે શિરોબિંદુઓને સંકોચાય તે ક્રમ નક્કી કરે છે; આનો અર્થ એ છે કે ક્રમ અગાઉથી જાણી શકાતો નથી પરંતુ અગાઉના સંકોચન પૂર્ણ થયા પછી સંકોચન માટે આગામી નોડ પસંદ કરવામાં આવે છે. બીજી તરફ ટોપ-ડાઉન હ્યુરિસ્ટિક્સ પ્રથમ નોડ સંકુચિત થાય તે પહેલાં સમગ્ર નોડ ક્રમની પૂર્વ ગણતરી કરે છે. આ વધુ સારા પરિણામો આપે છે પરંતુ વધુ પ્રીપ્રોસેસિંગ સમયની જરૂર છે. બોટમ-અપ હ્યુરિસ્ટિક્સમાં, સંકોચન માટે આગામી શિરોબિંદુ પસંદ કરવા માટે પરિબળોના સંયોજનનો ઉપયોગ કરવામાં આવે છે. શૉર્ટકટ્સની સંખ્યા એ પ્રાથમિક પરિબળ છે જે પ્રીપ્રોસેસિંગ અને ક્વેરી રનટાઇમ નક્કી કરે છે, તેથી અમે તેને શક્ય તેટલું નાનું રાખવા માંગીએ છીએ. સંકોચન માટે આગામી નોડ પસંદ કરવા માટે સૌથી મહત્વપૂર્ણ શબ્દ એ છે કે નોડનો સંકોચન કરતી વખતે ઉમેરવામાં આવેલી ધારની ચોખ્ખી સંખ્યા. આને વ્યાખ્યાયિત કરવામાં આવે છે કે જો સંકુચિત થવું હોય તો બનાવવામાં આવતા શોર્ટકટ્સની સંખ્યા ક્યાં છે અને તે કિનારીઓની સંખ્યા છે. એકલા આ માપદંડનો ઉપયોગ કરીને, એક રેખીય માર્ગ રેખીય પદાનુક્રમ (ઘણા સ્તરો) માં પરિણમશે અને કોઈ શોર્ટકટ બનાવવામાં આવશે નહીં. પહેલેથી જ સંકોચાયેલા નજીકના શિરોબિંદુઓની સંખ્યાને ધ્યાનમાં લઈને, એક સમાન સંકોચન અને સપાટ પદાનુક્રમ (ઓછા સ્તરો) પ્રાપ્ત થાય છે. આ, ઉદાહરણ તરીકે, દરેક નોડ માટે કાઉન્ટર જાળવીને કરી શકાય છે જે દરેક વખતે પડોશી શિરોબિંદુ સંકુચિત થાય ત્યારે વધારવામાં આવે છે. પછી નીચલા કાઉન્ટર્સવાળા નોડ્સને ઉચ્ચ કાઉન્ટર્સવાળા નોડ્સ કરતાં પસંદ કરવામાં આવે છે. બીજી બાજુ, ટોપ-ડાઉન હ્યુરિસ્ટિક્સ વધુ સારા પરિણામો આપે છે પરંતુ વધુ પ્રીપ્રોસેસિંગ સમયની જરૂર છે. તેઓ એવા શિરોબિંદુઓને વર્ગીકૃત કરે છે જે ઘણા ટૂંકા પાથનો ભાગ છે જે ફક્ત થોડા ટૂંકા પાથ માટે જરૂરી હોય તેના કરતા વધુ મહત્વપૂર્ણ છે. નેસ્ટેડ વિચ્છેદનનો ઉપયોગ કરીને આનો અંદાજ લગાવી શકાય છે. નેસ્ટેડ વિચ્છેદનની ગણતરી કરવા માટે, એક પુનરાવર્તિત રીતે આલેખને બે ભાગોમાં વિભાજિત કરે છે, જે પછી પોતે બે ભાગોમાં વિભાજિત થાય છે અને તેથી વધુ. એટલે કે, નોડ્સનો સબસેટ શોધો જે જ્યારે ગ્રાફમાંથી દૂર કરવામાં આવે ત્યારે લગભગ સમાન કદના બે વિચ્છેદિત ટુકડાઓમાં અલગ પડે છે. બધા ગાંઠોને નોડ ક્રમમાં છેલ્લા સ્થાને મૂકો અને પછી અને માટે નેસ્ટેડ વિચ્છેદનની પુનરાવર્તિત ગણતરી કરો, અંતઃપ્રેરણા એ છે કે ગ્રાફના અડધાથી ગ્રાફના બીજા અડધા સુધીના તમામ પ્રશ્નોને નાના વિભાજકમાંથી પસાર થવાની જરૂર છે અને તેથી આ વિભાજકમાં ગાંઠો ઉચ્ચ મહત્વ ધરાવે છે. નેસ્ટેડ વિચ્છેદનની ગણતરી તેમના નાના વિભાજકને કારણે રોડ નેટવર્ક પર અસરકારક રીતે કરી શકાય છે. ક્વેરી તબક્કો ક્વેરી તબક્કામાં, પ્રારંભિક નોડથી શરૂ કરીને દ્વિદિશાત્મક શોધ કરવામાં આવે છે અને મૂળ ગ્રાફ પરના લક્ષ્ય નોડને પ્રીપ્રોસેસિંગ તબક્કામાં બનાવેલા શોર્ટકટ્સ દ્વારા વધારવામાં આવે છે. અને વચ્ચેના સૌથી ટૂંકા માર્ગ પરનું સૌથી મહત્વપૂર્ણ શિરોબિંદુ કાં તો અથવા પોતાને અથવા બંને અને કરતાં વધુ મહત્વપૂર્ણ હશે. તેથી, વર્ટેક્સ મિનિમાઇઝિંગ મૂળ ગ્રાફમાં સૌથી ટૂંકા માર્ગ પર છે અને ધરાવે છે. આ, શોર્ટકટ્સ કેવી રીતે બનાવવામાં આવે છે તેની સાથે સંયોજનમાં, તેનો અર્થ એ છે કે આગળ અને પાછળની શોધ બંનેને માત્ર પદાનુક્રમમાં વધુ મહત્વપૂર્ણ નોડ્સ (ઉપરની તરફ) તરફ દોરી જતી ધારને આરામ કરવાની જરૂર છે જે શોધ જગ્યાને નાની રાખે છે. બધા અપ-(ડાઉન-અપ)-ડાઉન પાથમાં, આંતરિક (ડાઉન-અપ) ને અવગણી શકાય છે, કારણ કે પ્રીપ્રોસેસિંગ તબક્કામાં શોર્ટકટ બનાવવામાં આવ્યો છે. પાથ પુનઃપ્રાપ્તિ એ સીએચ ક્વેરી, ઉપર વર્ણવ્યા મુજબ, સમય અથવા અંતર આપે છે પરંતુ વાસ્તવિક પાથ નહીં. ટૂંકા માર્ગ પર ધાર (રસ્તાઓ) ની સૂચિ મેળવવા માટે, લેવામાં આવેલા શોર્ટકટ્સને ખોલવા પડે છે. દરેક શોર્ટકટ એ બે ધારોનું સંયોજન છેઃ મૂળ આલેખની બે ધાર, અથવા બે શોર્ટકટ, અથવા એક મૂળ ધાર અને એક શોર્ટકટ. સંકોચન દરમિયાન દરેક શોર્ટકટના મધ્ય શિરોબિંદુને સંગ્રહિત કરવાથી ટૂંકા માર્ગના રેખીય-સમય પુનરાવર્તિત અનપેકિંગને સક્ષમ બનાવે છે. કસ્ટમાઇઝ્ડ સંકોચન પદાનુક્રમ જો ધારનું વજન નેટવર્ક ટોપોલોજી કરતાં વધુ વખત બદલવામાં આવે છે, તો પ્રીપ્રોસેસિંગ અને ક્વેરી તબક્કા વચ્ચે કસ્ટમાઇઝેશન તબક્કાનો સમાવેશ કરીને સીએચને ત્રણ તબક્કાના અભિગમ સુધી વિસ્તૃત કરી શકાય છે. આનો ઉપયોગ ઉદાહરણ તરીકે ટૂંકા અંતર અને ટૂંકા સમય વચ્ચે સ્વિચ કરવા માટે અથવા વર્તમાન ટ્રાફિક માહિતી તેમજ ચોક્કસ પ્રકારના રસ્તાઓ (ફેરી, ધોરીમાર્ગો) ટાળવા જેવી વપરાશકર્તા પસંદગીઓ શામેલ કરવા માટે થઈ શકે છે. પ્રીપ્રોસેસિંગ તબક્કામાં, મોટાભાગનો રનટાઇમ તે ક્રમની ગણતરી કરવા માટે ખર્ચવામાં આવે છે જેમાં નોડ્સ સંકુચિત થાય છે. પ્રીપ્રોસેસિંગ તબક્કામાં સંકોચન કામગીરીનો આ ક્રમ કસ્ટમાઇઝેશન તબક્કામાં જ્યારે પછીથી જરૂરી હોય ત્યારે સાચવી શકાય છે. દરેક વખતે મેટ્રિકને કસ્ટમાઇઝ કરવામાં આવે ત્યારે, કસ્ટમ મેટ્રિકનો ઉપયોગ કરીને સંગ્રહિત ક્રમમાં સંકોચનને અસરકારક રીતે લાગુ કરી શકાય છે. વધુમાં, નવા ધાર વજનના આધારે કેટલાક શોર્ટકટ્સની ફરીથી ગણતરી કરવી જરૂરી બની શકે છે. આ કામ કરવા માટે, સંકોચન ક્રમની ગણતરી મેટ્રિક-સ્વતંત્ર નેસ્ટેડ વિચ્છેદનનો ઉપયોગ કરીને કરવી પડશે. ઉપર વર્ણવ્યા મુજબ એક્સ્ટેન્શન્સ અને એપ્લિકેશન્સ CHs એક પ્રારંભિક નોડથી એક લક્ષ્ય નોડ સુધીના ટૂંકા માર્ગની શોધ કરે છે. આને વન-ટુ-વન ટૂંકો માર્ગ કહેવામાં આવે છે અને ઉદાહરણ તરીકે કાર-નેવિગેશન સિસ્ટમમાં તેનો ઉપયોગ થાય છે. અન્ય એપ્લિકેશનોમાં રસ્તાના સેગમેન્ટ્સમાં જીપીએસ ટ્રેસ મેળવવાનો અને ટ્રાફિક સિમ્યુલેટરને ઝડપી બનાવવાનો સમાવેશ થાય છે, જેને નેટવર્કમાં તમામ ડ્રાઇવરો દ્વારા લેવામાં આવતા સંભવિત માર્ગોને ધ્યાનમાં લેવા પડે છે. માર્ગની આગાહીમાં કોઈ વ્યક્તિ તેની વર્તમાન અને ભૂતકાળની સ્થિતિ તેના પ્રારંભિક બિંદુથી કોઈપણ સંભવિત લક્ષ્ય સુધીના ટૂંકા માર્ગ સાથે કેટલી સારી રીતે સંમત થાય છે તેની ગણતરી કરીને વાહન સંભવિત રીતે ક્યાં જઈ રહ્યું છે તેનો અંદાજ કાઢવાનો પ્રયાસ કરે છે. આ સીએચએસનો ઉપયોગ કરીને અસરકારક રીતે કરી શકાય છે. એક-થી-ઘણા દૃશ્યોમાં, પ્રારંભિક નોડ અને લક્ષ્ય નોડનો સમૂહ આપવામાં આવે છે અને બધા માટે અંતરની ગણતરી કરવી પડે છે. એક-થી-ઘણા પ્રશ્નો માટે સૌથી અગ્રણી એપ્લિકેશન પોઇન્ટ-ઓફ-ઇન્ટરેસ્ટ સર્ચ છે. લાક્ષણિક ઉદાહરણોમાં મેટ્રિક તરીકે ભૌગોલિક અંતરને બદલે વાસ્તવિક મુસાફરીના સમયનો ઉપયોગ કરીને નજીકના ગેસ સ્ટેશન, રેસ્ટોરન્ટ અથવા પોસ્ટ ઓફિસ શોધવાનો સમાવેશ થાય છે. ઘણાથી ઘણા ટૂંકા પાથ દૃશ્યમાં, પ્રારંભિક નોડ્સનો સમૂહ અને લક્ષ્ય નોડ્સનો સમૂહ આપવામાં આવે છે અને બધા માટે અંતરની ગણતરી કરવી પડે છે. આનો ઉપયોગ ઉદાહરણ તરીકે લોજિસ્ટિક કાર્યક્રમોમાં થાય છે. CHs ને નીચેની રીતે ઘણા-થી-ઘણા પ્રશ્નો સુધી વિસ્તૃત કરી શકાય છે. પ્રથમ, દરેકમાંથી પાછળની તરફ ઉપરની તરફ શોધ કરો. આ શોધ દરમિયાન સ્કેન કરેલા દરેક શિરોબિંદુ માટે, એક ડોલમાં સંગ્રહ કરે છે. પછી, દરેક ખાલી ન હોય તેવી દરેક ડોલની તપાસ કરીને દરેકમાંથી આગળ ઉપરની તરફ શોધ કરવામાં આવે છે, કે શું અનુરૂપ શિરોબિંદુ પરનો માર્ગ કોઈપણ શ્રેષ્ઠ અંતરમાં સુધારો કરે છે કે કેમ. એટલે કે, જો કોઈ હોય તો. કેટલીક એપ્લિકેશનોને વન-ટુ-ઓલ ગણતરીઓની પણ જરૂર પડે છે, એટલે કે, ગ્રાફમાં સ્રોત શિરોબિંદુથી અન્ય તમામ શિરોબિંદુઓ સુધીનું અંતર શોધવું. ડિજ્ક્સ્ટ્રા અલ્ગોરિધમ દરેક ધારની બરાબર એક વાર મુલાકાત લે છે અને તેથી તે રેખીય સમયમાં ચાલે છે, તે સૈદ્ધાંતિક રીતે શ્રેષ્ઠ છે. જોકે, ડિજ્ક્સ્ટ્રા અલ્ગોરિધમને સમાંતર બનાવવું મુશ્કેલ છે અને તેના ખરાબ સ્થાનને કારણે તે કેશ-ઓપ્ટિમલ નથી. સીએચએસનો ઉપયોગ વધુ કેશ-શ્રેષ્ઠ અમલીકરણ માટે થઈ શકે છે. આ માટે, શોર્ટકટ-સમૃદ્ધ આલેખમાં તમામ નોડ્સ પર નીચે તરફ સ્કેન કરીને આગળ ઉપરની તરફ શોધ કરવામાં આવે છે. પછીની કામગીરી મેમરી દ્વારા રેખીય રીતે સ્કેન કરે છે, કારણ કે ગાંઠોને મહત્વના ઘટતા ક્રમમાં પ્રક્રિયા કરવામાં આવે છે અને તેથી તે મુજબ મેમરીમાં મૂકી શકાય છે. નોંધ લો કે આ શક્ય છે કારણ કે બીજા તબક્કામાં નોડ્સ પર જે ક્રમમાં પ્રક્રિયા કરવામાં આવે છે તે સ્રોત નોડથી સ્વતંત્ર છે. ઉત્પાદનમાં, કાર-નેવિગેશન પ્રણાલીઓ અનુમાનિત ટ્રાફિક માહિતીનો ઉપયોગ કરીને સૌથી ઝડપી મુસાફરી માર્ગોની ગણતરી કરવામાં અને વૈકલ્પિક માર્ગો પ્રદર્શિત કરવામાં સક્ષમ હોવી જોઈએ. બંને સીએચએસનો ઉપયોગ કરીને કરી શકાય છે. પહેલાને સમય-આધારિત નેટવર્ક સાથે રૂટીંગ કહેવામાં આવે છે જ્યાં આપેલ ધારનો મુસાફરીનો સમય હવે સ્થિર રહેતો નથી, પરંતુ ધારમાં પ્રવેશ કરતી વખતે દિવસના સમયનું કાર્ય હોય છે. વૈકલ્પિક માર્ગો સરળ દેખાતા હોવા જોઈએ, ટૂંકા માર્ગથી નોંધપાત્ર રીતે અલગ હોવા જોઈએ પરંતુ નોંધપાત્ર રીતે લાંબા ન હોવા જોઈએ. સીએચએસને એક જ સમયે બહુવિધ મેટ્રિક્સને શ્રેષ્ઠ બનાવવા માટે વિસ્તૃત કરી શકાય છે; આને બહુ-માપદંડ માર્ગ આયોજન કહેવામાં આવે છે. ઉદાહરણ તરીકે, મુસાફરીનો ખર્ચ અને સમય બંને ઘટાડી શકાય છે. બીજું ઉદાહરણ ઇલેક્ટ્રિક વાહનો છે જેના માટે ઉપલબ્ધ બેટરી ચાર્જ માન્ય માર્ગોને અવરોધે છે કારણ કે બેટરી ખાલી ન ચાલે. સિદ્ધાંત સંકોચન પદાનુક્રમના પ્રીપ્રોસેસિંગ અને ક્વેરી પ્રદર્શન પર સંખ્યાબંધ સીમાઓ સ્થાપિત કરવામાં આવી છે. નીચેના આલેખમાં શિરોબિંદુઓની સંખ્યા, ધારની સંખ્યા, ધોરીમાર્ગનું પરિમાણ, આલેખનો વ્યાસ, વૃક્ષની ઊંડાઈ છે અને વૃક્ષની પહોળાઈ છે. સંકોચન પદાનુક્રમના પ્રદર્શનનું પ્રથમ વિશ્લેષણ અંશતઃ ધોરીમાર્ગ પરિમાણ તરીકે ઓળખાતા જથ્થા પર આધાર રાખે છે. જ્યારે આ જથ્થાની વ્યાખ્યા તકનીકી છે, ત્યારે સહજ ભાવે આલેખમાં ધોરીમાર્ગનું એક નાનું પરિમાણ હોય છે જો દરેક માટે શિરોબિંદુઓનો એક વિરલ સમૂહ હોય જેમ કે લંબાઈના દરેક ટૂંકા માર્ગમાં એક શિરોબિંદુ શામેલ હોય. ધોરીમાર્ગ પરિમાણના ચોક્કસ મૂલ્યની ગણતરી કરવી એ એન. પી.-હાર્ડ અને ડબલ્યુ [1]-હાર્ડ છે, પરંતુ ગ્રીડ માટે તે જાણીતું છે કે ધોરીમાર્ગ પરિમાણ. કસ્ટમાઇઝેબલ કોન્ટ્રાકશન હાયરાર્કી લાઇન ઓફ વર્કમાં વૈકલ્પિક વિશ્લેષણ રજૂ કરવામાં આવ્યું હતું. ક્વેરી રનિંગ ટાઈમ્સ દ્વારા મર્યાદિત કરી શકાય છે. જેમ કે વૃક્ષની ઊંડાઈને વૃક્ષની પહોળાઈની દ્રષ્ટિએ બંધાવી શકાય છે, તે પણ માન્ય ઉપલા બાઉન્ડ છે. મુખ્ય સ્રોત એ છે કે સૌથી ખરાબ કેસ ચાલી રહેલા સમયના પરિણામો વધુ સારી રીતે વિગતવાર છે. પૂર્વપ્રક્રિયા પ્રદર્શન પ્રશ્ન પ્રદર્શન સંદર્ભો બાહ્ય કડીઓ ઓપન સોર્સ અમલીકરણ https://www.graphhopper.com https://github.com/ifsttar/Tempus https://github.com/RoutingKit/RoutingKit http://project-osrm.org http://www.opentripplanner.org ગ્રાફ અલ્ગોરિધમ્સ શોધ અલ્ગોરિધમ્સ રૂટીંગ અલ્ગોરિધમ્સ