destination used to convey a defaul

destination used to convey a default route. In RIP, the Bellman-Ford algorithms make each router
periodically broadcast its routing tables to all its neighbors. Then a router knowing its neighbors’
tables can decide to which destination neighbor to forward a packet.
OSPF is a routing protocol developed for Internet Protocol (IP) networks by the Interior Gateway
Protocol (IGP) Working Group of the Internet Engineering Task Force (IETF). OSPF was
created because in the mid-1980s, RIP was increasingly incapable of serving large, heterogeneous
internetworks. Like most link-state algorithms, OSPF uses a graph-theoretic model of network
topology to compute shortest paths. Each router periodically broadcasts information about the
status of its connections. OSPF floods information about adjacencies to all routers in the network
where each router locally computes the shortest paths by running Dijkstra’s algorithm.
4.2 SPT-based approximations
Besides their applications to network routing problems, the shortest-paths tree algorithms could
also serve as good approximations for some NP-hard problems. For example, we will later show
that a shortest-paths tree rooted at some vertex is a 2-approximation of the minimum routing
cost spanning tree (MRCT) problem, which is known to be NP-hard. In fact, several SPT-based
approximations will be studied in the next chapters.
5 Summary
We have introduced two most basic algorithms for constructing a shortest-paths tree for a given
directed or undirected weighted graph. Both of them use the technique of relaxation, progressively
decreasing a shortest-path estimate ±[v] for each vertex v. The relaxation causes the shortest-path
estimates to descend monotonically toward the actual shortest-path weights. Dijkstra’s algorithm
relaxes each edge exactly once (twice in the case of undirected graphs) if all the edge weights are
positive. On the other hand, the Bellman-Ford algorithm relaxes each edge n¡1 times, so that the
effect of a negative edge can be propagated properly. If the shortest-path estimates do not stabilize
after n¡1 passes, then there must exist a negative cycle in the graph, and the algorithm indicates
that no solution exists.

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

ปลายทางที่ใช้ในการถ่ายทอดการผลิตเริ่มต้น ฉีก อัลกอริทึมบริการฟอร์ดทำเราเตอร์แต่ละออกอากาศของตารางสายงานการผลิตเป็นระยะ ๆ เพื่อบ้านของ จากนั้นเราเตอร์รู้ของเพื่อนบ้านตารางสามารถเลือกเพื่อนบ้านปลายทางที่ส่งต่อแพคเก็ตOSPF เป็นโพรโทคอสายงานการผลิตที่พัฒนา โดยเกตเวย์ภายในเครือข่ายอินเทอร์เน็ตโพรโทคอล (IP)โพรโทคอล (IGP) กลุ่มทำงานของแรงงานวิศวกรรมอินเทอร์เน็ต (IETF) OSPF ถูกสร้างเนื่องในกลางไฟต์ RIP หมันมากขึ้นของการให้บริการขนาดใหญ่ บริการinternetworks เช่นส่วนใหญ่เชื่อมโยงรัฐอัลกอริทึม OSPF ใช้รูปแบบกราฟ theoretic ของเครือข่ายโทโพโลยีจะคำนวณเส้นทางที่สั้นที่สุด แต่ละเราเตอร์กระจายข้อมูลเป็นระยะ ๆ เกี่ยวกับการสถานะของการเชื่อมต่อ ข้อมูลน้ำท่วม OSPF เกี่ยวกับ adjacencies ไปยังเราเตอร์ทั้งหมดในเครือข่ายที่เราเตอร์แต่ละเครื่องคำนวณเส้นทางที่สั้นที่สุด โดยใช้วิธีของไดค์4.2 SPT ใช้เพียงการประมาณนอกจากไปประยุกต์ใช้เครือข่ายปัญหาเส้นทาง เส้นทางที่สั้นที่สุดทรีอัลกอริทึมสามารถนอกจากนี้ยัง ทำหน้าที่เป็นเพียงการประมาณสำหรับปัญหา NP หนักดี ตัว เราจะในภายหลังแสดงว่าเส้นทางที่สั้นที่สุดต้นไม้รากที่บางจุดประมาณ 2 ของสายงานการผลิตต่ำสุดต้นทุนรัฐภูมิ (MRCT) ปัญหา ซึ่งเป็นที่รู้จักเป็น NP ยาก ในความเป็นจริง หลายใช้ SPTเพียงการประมาณจะได้ศึกษาในบทต่อไปสรุป 5เรามีแนะนำสองอัลกอริทึมพื้นฐานสำหรับการสร้างแผนภูมิเป็นเส้นทางที่สั้นที่สุดสำหรับการกำหนดโดยตรง หรือ undirected ถ่วงน้ำหนักกราฟ ทั้งสองอย่างใช้เทคนิคการผ่อนคลาย ความก้าวหน้าลดการ±ประเมินเส้นทางสั้นที่สุด [v] สำหรับแต่ละจุดยอด v พักผ่อนทำให้สั้นที่สุดเส้นทางประเมิน monotonically ล่องไปทางเส้นทางที่สั้นที่สุดน้ำหนักจริง วิธีของไดค์ก็ขอบแต่ละครั้งแน่นอน (สองกรณีกราฟ undirected) ถ้าน้ำหนักขอบทั้งหมดบวก บนมืออื่น ๆ อัลกอริทึมบริการฟอร์ดก็ครั้งละขอบ n¡1 เพื่อให้การผลกระทบของการขอบลบสามารถเผยแพร่ได้อย่างถูกต้อง ถ้าไม่มีมุ่งประเมินเส้นทางสั้นที่สุดหลังจาก n¡1 ผ่าน แล้ว ต้องมีวงจรลบในกราฟ และอัลกอริทึมระบุว่า แก้ปัญหาไม่มีอยู่

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

ปลายทางที่ใช้ในการถ่ายทอดเส้นทางเริ่มต้น ใน RIP,
ขั้นตอนวิธียามฟอร์ดทำให้เราเตอร์แต่ละระยะออกอากาศตารางเส้นทางของเพื่อนบ้านทั้งหมด จากนั้นเราเตอร์รู้เพื่อนบ้าน
'ตารางสามารถตัดสินใจที่เพื่อนบ้านปลายทางที่จะส่งต่อแพ็คเก็ต.
OSPF เป็นโปรโตคอลการกำหนดเส้นทางการพัฒนาสำหรับ Internet Protocol (IP) เครือข่ายโดยมหาดไทยเกตเวย์
Protocol (IGP) คณะทำงานของ Internet Engineering Task Force (IETF ) OSPF
ถูกสร้างขึ้นเพราะในช่วงกลางทศวรรษ1980, RIP มีความสามารถมากขึ้นในการให้บริการขนาดใหญ่ที่แตกต่างกัน
internetworks ชอบมากที่สุดขั้นตอนวิธีการเชื่อมโยงของรัฐ OSPF
ใช้รูปแบบของกราฟทฤษฎีเครือข่ายโครงสร้างในการคำนวณเส้นทางที่สั้นที่สุด
เราเตอร์แต่ละระยะออกอากาศข้อมูลเกี่ยวกับสถานะการเชื่อมต่อของ OSPF น้ำท่วมข้อมูลเกี่ยวกับ adjacencies
เราเตอร์ทั้งหมดในเครือข่ายที่แต่ละเราเตอร์ในประเทศคำนวณเส้นทางที่สั้นที่สุดโดยใช้อัลกอริทึมของDijkstra.
4.2 ใกล้เคียง SPT-based นอกจากนี้การใช้งานของพวกเขาไปยังเครือข่ายปัญหาเส้นทางเส้นทางที่สั้นที่สุดขั้นตอนวิธีการที่ต้นไม้จะยังทำหน้าที่ใกล้เคียงที่ดีสำหรับปัญหา NP-ยาก ตัวอย่างเช่นเราจะมาแสดงให้เห็นว่าเส้นทางที่สั้นที่สุด-ต้นไม้ที่หยั่งรากบางส่วนที่จุดสุดยอดเป็น 2 ประมาณของเส้นทางขั้นต่ำค่าใช้จ่ายซึ่งประกอบไปด้วยต้นไม้(MRCT) ปัญหาซึ่งเป็นที่รู้จักกัน NP-ยาก ในความเป็นจริงหลาย SPT-based ใกล้เคียงจะได้รับการศึกษาในบทต่อไป. 5 สรุปเราได้แนะนำสองขั้นตอนวิธีพื้นฐานที่สุดในการสร้างต้นไม้ที่สั้นที่สุดสำหรับเส้นทางที่กำหนดกำกับหรือundirected กราฟถ่วงน้ำหนัก ทั้งสองของพวกเขาใช้เทคนิคของการพักผ่อนที่มีความก้าวหน้าการลดประมาณการเส้นทางที่สั้นที่สุด± [วี] สำหรับแต่ละจุดยอด v. ทำให้เกิดการผ่อนคลายที่สั้นที่สุดเส้นทางประมาณการลงmonotonically ต่อน้ำหนักที่สั้นที่สุดเส้นทางที่เกิดขึ้นจริง อัลกอริทึมของ Dijkstra ผ่อนคลายขอบแต่ละครั้งว่า (สองในกรณีของกราฟ undirected) ที่หากมีน้ำหนักขอบเป็นบวก บนมืออื่น ๆ , อัลกอริทึมยามผ่อนคลายฟอร์ดครั้งn¡1แต่ละเส้นเพื่อให้ผลของขอบเชิงลบสามารถแพร่กระจายได้อย่างถูกต้อง หากประมาณการเส้นทางที่สั้นที่สุดไม่ได้มีเสถียรภาพหลังจากn¡1ผ่านไปแล้วจะต้องอยู่รอบเชิงลบในกราฟและขั้นตอนวิธีการแสดงให้เห็นว่าไม่มีวิธีแก้ปัญหา

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

ปลายทางใช้สื่อเริ่มต้นเส้นทาง ในการตัด , พนักงานฟอร์ดขั้นตอนวิธีให้แต่ละระยะของเส้นทางตารางเราเตอร์
ออกอากาศไปยังประเทศเพื่อนบ้านทั้งหมด แล้วเราเตอร์รู้จักเพื่อนบ้าน '
ตารางสามารถตัดสินใจซึ่งปลายทางเพื่อนบ้านเพื่อส่งต่อแพ็กเก็ต .
OSPF โปรโตคอลเส้นทางพัฒนาเป็นอินเทอร์เน็ต โปรโตคอล ( IP ) เครือข่ายโดย
ประตูภายในโพรโทคอล ( IGP ) กลุ่มงานของอินเทอร์เน็ตในงานวิศวกรรม ( IETF ) OSPF คือ
สร้างเพราะในช่วงกลางทศวรรษที่ 1980 , ริปได้มากขึ้น สามารถให้บริการขนาดใหญ่แตกต่างกัน
นเตอร์เน็ตเวิร์ค . ชอบของรัฐเชื่อมโยงมากที่สุด , OSPF ใช้กราฟทฤษฎีแบบจำลองของโครงสร้างเครือข่าย
เพื่อคำนวณหาเส้นทางที่สั้นที่สุด แต่ละเราเตอร์เป็นระยะ ๆ เผยแพร่ข้อมูลเกี่ยวกับ
สถานะการเชื่อมต่อของข้อมูลเกี่ยวกับ adjacencies OSPF น้ำท่วมเพื่อเราเตอร์ในเครือข่ายที่เราเตอร์ภายในแต่ละ
คำนวณเส้นทางที่สั้นที่สุด โดยการใช้ขั้นตอนวิธีของไดค์สตรา .
4.2 ระบบตามการ
นอกจากการใช้งานของเครือข่ายเส้นทางปัญหา เส้นทางสั้นที่สุดต้นไม้อัลกอริทึมอาจ
ยังเป็นการดีสำหรับบางคนคือ ปัญหาหนัก ตัวอย่างเช่น เราจะต่อมาโชว์
ที่เป็นเส้นทางสั้นที่สุด ต้นไม้รากในบางจุดยอดเป็น 2-approximation ของขั้นต่ำเส้นทาง
ต้นทุนต้นไม้ทอดข้าม ( mrct ) ปัญหาซึ่งเป็นที่รู้จักกันเป็นปัญหาหนัก ในความเป็นจริง , SPT หลายตาม
การจะเรียนในบทถัดไป สรุปเราได้แนะนำ
5
2 พื้นฐานขั้นตอนวิธีสำหรับการสร้างเส้นทางสั้นที่สุดต้นไม้ให้
กำกับหรือ undirected แบบกราฟทั้งสองของพวกเขาใช้เทคนิคการผ่อนคลายความก้าวหน้า
ลดเส้นทางที่สั้นที่สุดประมาณ± [ V ] สำหรับแต่ละจุดยอด V เพื่อให้เส้นทางที่สั้นที่สุดจาก monotonically
มาต่อจริงเส้นทางสั้นที่สุด หนัก ขั้นตอนวิธีของไดค์สตรา
ลดขอบเดียว ( สองครั้งในกรณีของกราฟ Undirected ) ถ้าน้ำหนักทั้งหมดขอบเป็น
บวก บนมืออื่น ๆพนักงานฟอร์ดขั้นตอนวิธีใช้ขอบ N ¡ 1 ครั้ง เพื่อที่ผลของขอบเชิงลบสามารถขยายพันธุ์ได้อย่างถูกต้อง ถ้าสั้นประมาณเส้นทางไม่มั่นคง
หลังจาก N ¡ 1 ผ่านไปก็ต้องมีวงจรเชิงลบในกราฟ ขั้นตอนวิธีการบ่งชี้ว่าไม่มีโซลูชั่น

อยู่