የመስመር ላይ የግራፍ ቲዎሪ ትንተና መሳሪያ

የመሳሪያው ባህሪያት

ይህ የመስመር ላይ መሳሪያ ያልተመራ ግራፍ ይቀበላል፣ ጠርዞችን በstart,end,weight ቅርጸት ይጠቀማል። ክብደቱ ካልተሰጠ ወደ 1 ይቀነሳል። እስከ 1000 ጠርዞች እና እስከ 500 የተለያዩ አንጓዎች ይደገፋሉ። የDijkstra ስልተ-ቀመር ጥቅም ላይ ይውላል፣ ስለዚህ አሉታዊ ክብደቶች ውድቅ ይደረጋሉ፣ ዜሮ ክብደት ደግሞ ይፈቀዳል።

የተጠቃሚ ችግር እና ምሳሌ

ተጠቃሚዎች ብዙውን ጊዜ በአውታረ መረብ ውስጥ አጭሩ መንገድ ማግኘት ይፈልጋሉ። ለምሳሌ ጠርዞቹን ያስገቡ፡

A,B,2
B,C,3
A,C,10

ከA ወደ C ሲፈልጉ ውጤቱ ርቀት 5 እና መንገድ A → B → C ይሆናል። ይህ የሚያሳየው ቀጥተኛው መንገድ ርዝመቱ 10 ቢሆንም በB በኩል መሄድ አጭር እንደሆነ ነው።

ውስንነቶች

መሳሪያው የሚደግፈው ያልተመሩ ግራፎችን ብቻ ነው፣ ትይዩ ጠርዞች ይፈቀዳሉ። የተመሩ ግራፎች፣ መጋጠሚያ እይታ፣ ማዕከላዊነት፣ ዝቅተኛ የዛፍ ስፋት ወይም አሉታዊ-ጠርዝ ስልተ-ቀመሮች አይደገፉም። ውጤቱ አንድ ቅድመ-ተከታይ መንገድ ብቻ ያሳያል፣ እኩል አጫጭር መንገዶችን አያሳይም።

የተለመዱ ጥያቄዎች

ጥያቄ 1፡ አሉታዊ ክብደት ያላቸውን ጠርዞች ማስገባት እችላለሁ?

አይ፣ የDijkstra ስልተ-ቀመር አሉታዊ ክብደቶችን አይደግፍም፣ ስለዚህ እንደዚህ ያሉ ጠርዞች ውድቅ ይደረጋሉ። ዜሮ ክብደት ግን ይፈቀዳል።

ጥያቄ 2፡ የመነሻ እና መድረሻ አንጓዎች በጠርዝ ዝርዝሩ ውስጥ ካልተገኙ ምን ይሆናል?

መሳሪያው ስህተት ያሳያል ወይም እነዚያ አንጓዎች በግራፉ ውስጥ እንዲካተቱ ይጠይቃል። የመነሻ እና መድረሻ አንጓዎች በጠርዝ ዝርዝሩ ውስጥ መታየት አለባቸው።

ጥያቄ 3፡ ውጤቱ ምን ያካትታል?

ውጤቱ አጭሩ ርቀት፣ አንድ ቅድመ-ተከታይ መንገድ እና አጠቃላይ የአንጓዎች ብዛት ያሳያል። ግንኙነት ከሌለ ግልጽ የሆነ የግንኙነት እጦት መልእክት ይታያል።

የተጠቃሚ ተግባር ዝርዝር

• ጠርዞችን በትክክለኛው ቅርጸት ያስገቡ
• የመነሻ እና መድረሻ አንጓዎችን ይምረጡ
• የመተንተን ቁልፍን ይጫኑ
• ውጤቱን ይተርጉሙ