A roadnetwork can be considered as

A roadnetwork can be considered as a graph with positive weights. The nodes represent road crossings and an edge is a road between two crossings. The weight of an edge is either the length of the associated road segment or the time needed to get from one end to the other. Using directed edges it is also possible to model one-way streets. Such graphs are special in the sense that some edges are more important than others for long distance travel (i.e. highways). This property has been formalized using the notion of highway dimension. There are a great number of algorithms that exploit this property and are therefore able to compute the shortest path a lot quicker than would be possible on general graphs.
All of these algorithms work in two phases. In the first phase, the graph is preprocessed without knowing the source or target node. This phase may take several days for realistic data and some techniques. The second phase is the query phase. In this phase, source and target node are known. The running time of the second phase is generally less than a second. The idea is that the road network is static, so the preprocessing phase can be done once and used for a large number of queries on the same road network.
The algorithm with the fastest known query time is called hub labeling and is able to compute shortest path on the road networks of Europe or the USA in a fraction of a microsecond. Other techniques that have been used are:

ผลลัพธ์ (ไทย) 1:

roadnetwork ถือได้ว่าเป็นกราฟที่มีน้ำหนักในเชิงบวก โหนดแทนแยกถนนและขอบถนนระหว่างสองแยก น้ำหนักของขอบเป็นทั้งความยาวของส่วนถนนที่เกี่ยวข้องหรือเวลาที่จำเป็นในการได้รับจากปลายด้านหนึ่งไปยังอีก ใช้ขอบกำกับก็ยังเป็นไปได้ที่จะสร้างแบบจำลองทางเดียวถนนกราฟดังกล่าวมีความพิเศษในแง่ที่ว่าขอบบางส่วนที่มีความสำคัญมากขึ้นกว่าคนอื่น ๆ ในการเดินทางระยะไกล (เช่นทางหลวง) สถานที่ให้บริการนี​​้ได้รับการกรงเล็บใช้ความคิดของมิติทางหลวง มีจำนวนมากของขั้นตอนวิธีการที่ใช้ประโยชน์จากสถานที่ให้บริการนี​​้และดังนั้นจึงสามารถที่จะคำนวณเส้นทางที่สั้นมากได้เร็วกว่าที่จะเป็นไปได้บนกราฟทั่วไป.
ทุกขั้นตอนวิธีการเหล่านี้ทำงานในสองขั้นตอน ในระยะแรกกราฟจะประมวลผลล่วงหน้าโดยไม่ทราบแหล่งที่มาหรือโหนดเป้​​าหมาย ขั้นตอนนี้อาจใช้เวลาหลายวันเพื่อให้ข้อมูลที่เป็นจริงและเทคนิคบางอย่าง ขั้นตอนที่สองคือขั้นตอนการค้นหา ในขั้นตอนนี้แหล่งที่มาและเป้าหมายของโหนดเป็นที่รู้จักกัน เวลาทำงานของขั้นตอนที่สองคือโดยทั่วไปน้อยกว่าที่สองความคิดที่ว่าเครือข่ายถนนเป็นแบบคงที่เพื่อให้ขั้นตอนการ preprocessing สามารถทำได้เพียงครั้งเดียวและใช้สำหรับการเป็นจำนวนมากของการค้นหาบนเครือข่ายถนนเดียวกัน.
ขั้นตอนวิธีการที่มีเวลาแบบสอบถามที่รู้จักกันเร็วที่สุดจะเรียกว่าการติดฉลากศูนย์กลางและสามารถที่จะคำนวณ เส้นทางที่สั้นที่สุดบนเครือข่ายถนนของยุโรปหรือสหรัฐอเมริกาในส่วนของมิลลิ เทคนิคอื่น ๆ ที่มีการใช้มีดังนี้:

ผลลัพธ์ (ไทย) 2:

Roadnetwork สามารถถือได้ว่าเป็นกราฟที่มีน้ำหนักเป็นบวก โหนแสดงข้ามถนน และขอบเป็นถนนระหว่างสองข้าม น้ำหนักของขอบมีความยาวของถนนเชื่อมโยงเซกเมนต์หรือเวลาที่ต้องการได้จากปลายด้านหนึ่งไปยังอีกหนึ่ง ใช้ขอบโดยตรงยังสามารถได้แบบถนนทางเดียว กราฟดังกล่าวเป็นพิเศษในแง่ที่ว่า บางอยู่สำคัญกว่าผู้อื่นในระยะยาวเดินทาง (เช่นทางหลวง) แห่งนี้ได้ถูก formalized ใช้แนวคิดของมิติทางหลวง มีจำนวนมากของอัลกอริทึมที่ใช้คุณสมบัตินี้ และดังนั้นสามารถคำนวณเส้นทางสั้นที่สุดเร็วมากกว่าจะได้กราฟทั่วไป
อัลกอริทึมเหล่านี้ทั้งหมดทำงานในระยะที่สอง ในระยะแรก กราฟคือ preprocessed โดยไม่ทราบต้นทางหรือปลายทางโหนด ขั้นตอนนี้อาจใช้เวลาหลายวันในข้อมูลจริงและเทคนิคบางอย่าง ระยะที่สองเป็นขั้นตอนการสอบถาม ในโหนดนี้ระยะ ต้นทาง และปลายทางเป็นที่รู้จักกัน เวลาทำงานของขั้นตอนที่สองคือโดยทั่วไปน้อยกว่าที่สอง ความคิดคือเครือข่ายถนนคง ขั้นตอนการประมวลผลเบื้องต้นสามารถทำครั้งเดียว และใช้สำหรับแบบสอบถามบนแบบเดียวกับถนนเครือข่ายเป็นจำนวนมาก
อัลกอริทึม ด้วยเวลาเร็วที่สุดรู้จักถามเรียกว่าฮับติดฉลาก และสามารถคำนวณเส้นทางที่สั้นที่สุดบนเครือข่ายถนนของยุโรปหรืออเมริกาในเศษเสี้ยวของ microsecond เทคนิคที่ใช้อยู่:

ผลลัพธ์ (ไทย) 3:

roadnetwork ที่สามารถได้รับการพิจารณาให้เป็นกราฟที่พร้อมด้วยเครื่องยกน้ำหนักในเชิงบวก โหนดที่เป็นจุดข้ามแดนและถนนที่เป็นถนนสายระหว่างสองจุดข้ามแดน น้ำหนักของขอบที่มีทั้งความยาวของส่วนถนนที่เกี่ยวข้องหรือเวลาที่จำเป็นต้องใช้ในการได้รับจากปลายด้านหนึ่งเพื่อไปยังอีกแห่งหนึ่งได้ การใช้ขอบโดยตรงนอกจากนี้ยังเป็นไปได้ที่จะรุ่นถนนสายหนึ่ง - แบบเที่ยวเดียวกราฟนั้นเป็นแบบพิเศษในความรู้สึกที่ขอบบางอย่างมีความสำคัญมากขึ้นกว่าที่อื่นสำหรับการเดินทางระยะไกล(เช่นทางหลวง) ที่พักแห่งนี้ได้รับการจัดทำอย่างเป็นทางการโดยใช้ความคิดของทางหลวงสายอุปกรณ์เสริม มีหมายเลขที่ดีเยี่ยมในอัลกอริธึมที่ใช้ประโยชน์จากที่พักแห่งนี้และดังนั้นจึงสามารถคำนวณเส้นทางที่สั้นมากมากกว่าจะสามารถเป็นไปได้ในกราฟโดยทั่วไป
อัลกอริธึมทั้งหมดนี้ทำงานในสองขั้นตอนคือ ในช่วงแรกของกราฟที่ได้จะ preprocessed โดยไม่รู้ว่าโหนดเป้าหมายหรือแหล่งที่มา ขั้นตอนนี้อาจต้องใช้เวลาหลายวันสำหรับข้อมูลที่ดูสมจริงและเทคนิคบางอย่าง ขั้นตอนที่สองคือการสอบถามขั้นตอนที่ ในขั้นตอนนี้โหนดเป้าหมายและแหล่งที่เป็นที่รู้จักกันดี เวลาการทำงานในระยะที่สองโดยทั่วไปแล้วจะน้อยกว่าที่สองที่คิดว่าเครือข่ายถนนที่เป็นแบบคงที่,ให้ preprocessing ขั้นตอนสามารถทำได้ครั้งเดียวและใช้สำหรับจำนวนมากมีการค้นหาในที่เดียวกันกับเครือข่ายถนน.
ที่พร้อมด้วยอัลกอริธึมที่เร็วที่สุดในการค้นหาเป็นเวลาเรียกว่าศูนย์กลางการติดฉลากและสามารถที่จะคำนวณเส้นทางสั้นที่สุดบนเครือข่ายถนนของยุโรปหรือสหรัฐอเมริกาในส่วนของที่ microsecond . เทคนิคอื่นๆที่ได้รับการใช้งาน: