As long as all the edge weights are

As long as all the edge weights are nonnegative, the shortest-paths tree is well defined. Un- fortunately, things get somewhat complicated in the presence of negative edge weights. For an undirected graph, a long path gets “shorter” when we repeatedly add an edge with negative weight to it. In this situation, a shortest path that contains an edge with negative weight is not well de- fined since a lesser-weight path can always be found by going back and forth on the negative-weight edge. Consider the graph in Figure 4. In this graph, edge (d, e) is of negative weight. Since, for an undirected graph, an edge can be traversed in both directions, a path that repeatedly uses (d, e) will reduce its length. However, for a directed graph, as long as there exists no negative-weight cycle reachable from the source, the shortest-path weights are well defined. Thus when talking about the

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

ตราบเท่าที่น้ำหนักขอบทั้งหมดที่มี nonnegative ต้นเส้นทางที่สั้นที่สุดเป็นที่กำหนดไว้ สหประชาชาติ - โชคดี สิ่งที่ได้ค่อนข้างซับซ้อนในต่อหน้าของน้ำหนักลบขอบ สำหรับกราฟที่ undirected เส้นยาวจะ "สั้น" เมื่อเราเพิ่มขอบ ด้วยน้ำหนักที่ลบนั้นซ้ำ ๆ ในสถานการณ์นี้ เส้นทางสั้นที่สุดที่ประกอบด้วยขอบ ด้วยน้ำหนักที่ลบไม่ได้ดีเด-ปรับเนื่องจากไม่พบเส้นน้ำหนักน้อยกว่า โดยไปและกลับบนขอบลบน้ำหนักเสมอ พิจารณากราฟในรูปที่ 4 กราฟนี้ ขอบ (d, e) เป็นน้ำหนักที่เป็นค่าลบ ตั้งแต่ สำหรับกราฟการ undirected ขอบสามารถจะไม่เหมือนกันในทั้งสองทิศทาง เส้นทางที่ซ้ำๆ ใช้ (d, e) จะลดความยาว อย่างไรก็ตาม สำหรับกราฟโดยตรง เป็นนานที่มีอยู่รอบน้ำหนักลบไม่สามารถเข้าถึงจากแหล่ง น้ำหนักเส้นทางสั้นที่สุดดีไว้ ดังนั้นเมื่อพูดถึงการ

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

ตราบใดที่ทุกน้ำหนักขอบเป็นค่าลบต้นไม้เส้นทางที่สั้นที่สุดจะถูกกำหนดไว้อย่างดี ยกเลิกโชคดีที่ได้รับสิ่งที่ค่อนข้างซับซ้อนในการปรากฏตัวของน้ำหนักขอบเชิงลบ สำหรับ undirected กราฟเป็นเส้นทางที่ยาวได้รับ "สั้น" เมื่อเราซ้ำ ๆ เพิ่มขอบที่มีน้ำหนักเชิงลบไป ในสถานการณ์เช่นนี้เป็นเส้นทางที่สั้นที่สุดที่มีขอบที่มีน้ำหนักเชิงลบไม่ได้ดี de- ปรับตั้งแต่เส้นทางน้ำหนักน้อยสามารถพบได้เสมอโดยจะกลับมาบนขอบน้ำหนักเชิงลบ พิจารณากราฟในรูปที่ 4 ในกราฟนี้ขอบ (D, E) เป็นเชิงลบของน้ำหนัก ตั้งแต่สำหรับ undirected กราฟ, ขอบสามารถสำรวจทั้งสองทิศทางเส้นทางที่ใช้ซ้ำ (D, E) จะลดความยาวของมัน แต่สำหรับกราฟตราบใดที่มีอยู่รอบเชิงลบไม่มีน้ำหนักเข้าถึงได้จากแหล่งที่มาของน้ำหนักเส้นทางที่สั้นที่สุดจะถูกกำหนดไว้อย่างดี ดังนั้นเมื่อพูดคุยเกี่ยวกับ

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

ตราบใดที่น้ำหนักทั้งหมดขอบเป็น nonnegative , เส้นทางสั้นที่สุด ต้นไม้ที่กำหนดไว้อย่างดี สหประชาชาติ - โชคดี สิ่งที่ได้รับค่อนข้างซับซ้อนในการปรากฏตัวของน้ำหนักขอบเชิงลบ สำหรับกราฟไม่ระบุทิศทาง เส้นทางที่ยาวได้ " สั้น " เมื่อเราซ้ำๆเพิ่มขอบที่มีน้ำหนักติดลบได้ ในสถานการณ์นี้เส้นทางที่สั้นที่สุดที่มีขอบกับน้ำหนักเชิงลบจะไม่ de - ปรับเนื่องจากเส้นทางที่น้ำหนักน้อยจะสามารถพบได้โดยไป ๆมา ๆบนขอบน้ำหนักเชิงลบ พิจารณากราฟในรูปที่ 4 ในกราฟนี้ ขอบ ( D , E ) มีน้ำหนักเชิงลบ เนื่องจาก , สำหรับกราฟไม่ระบุทิศทาง , ขอบสามารถ traversed ในทั้งสองทิศทาง เส้นทางที่ใช้ซ้ำๆ ( D , E ) จะลดความยาวของอย่างไรก็ตาม สำหรับกราฟทิศทาง ตราบเท่าที่มีอยู่ไม่ลบน้ำหนักรอบได้จากแหล่งที่มาอันสั้นน้ำหนักเส้นทางถูกกำหนดไว้อย่างดี ดังนั้นเมื่อพูดถึง