የመስመር ላይ የግራፍ ቲዎሪ ትንተና መሳሪያ
እስከ 500 አንጓዎች ያሉትን ግራፎች ይቀበላል፣ የDijkstra ስልተ-ቀመር በመጠቀም አጭሩ መንገድ ያሰላል። ምሳሌ፡ A,B,2; B,C,3; A,C,10 ከA ወደ C ርቀት 5 ይሰጣል። ሂደቱ በአሳሽዎ ውስጥ ይከናወናል።
መጠቀም ይጀምሩ
የመሳሪያው ባህሪያት
ይህ የመስመር ላይ መሳሪያ ያልተመራ ግራፍ ይቀበላል፣ ጠርዞችን በ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፡ ውጤቱ ምን ያካትታል?
ውጤቱ አጭሩ ርቀት፣ አንድ ቅድመ-ተከታይ መንገድ እና አጠቃላይ የአንጓዎች ብዛት ያሳያል። ግንኙነት ከሌለ ግልጽ የሆነ የግንኙነት እጦት መልእክት ይታያል።
የተጠቃሚ ተግባር ዝርዝር
- ጠርዞችን በትክክለኛው ቅርጸት ያስገቡ
- የመነሻ እና መድረሻ አንጓዎችን ይምረጡ
- የመተንተን ቁልፍን ይጫኑ
- ውጤቱን ይተርጉሙ
መስኮችን በASCII ኮማ ይለዩ፣ በክብደት ውስጥም የአስርዮሽ ነጥብ ይጠቀሙ። A,B ክብደት 1 ነው፤ A,B, ያለ ክብደት ግን አሁን 0 ተብሎ ይነበባል፣ ስለዚህ ክብደቱን በግልጽ ይጻፉ። ባዶ መስመሮች ይዘለላሉ። ስሞች ትልቅና ትንሽ ፊደል ይለያሉ፤ የውጭ ክፍተት ብቻ ይወገዳል፣ ኮማም አይፈቀድም። መነሻና መድረሻ አንድ ከሆኑ ርቀቱ 0 እና መንገዱ ያ አንጓ ነው። በዝርዝሩ ያሉ ሁሉም አንጓዎች ይቆጠራሉ። የቁጥር ድምር ሊጠጋ ይችላል፤ መንገዱ ቢኖርም ርቀቱ ከውስን ክልል ከበለጠ የቁጥር ስህተት ይታያል።
ሂደቱ በአሳሽዎ ውስጥ ይከናወናል።