อัลกอริทึมในการหา cycle ที่สั้นที่สุดมีดังต่อไปนี้

รัน Floyd's algorithm บนกราฟ และสมมติให้ output ของมันอยู่ในอะเรย์
สำหรับ edge $Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } } Error Too many requests (f061ab2) If you report this error to the Wikimedia System Administrators, please include the details below. Request served via cp5021 cp5021, Varnish XID 457834568 Upstream caches: cp5021 int Error: 429, Too many requests (f061ab2) at Fri, 23 Jan 2026 19:55:37 GMT Sensitive client information IP address: 158.108.32.49$ แต่ละ edge ใน ให้คำนวณค่า $Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } } Error Too many requests (f061ab2) If you report this error to the Wikimedia System Administrators, please include the details below. Request served via cp5021 cp5021, Varnish XID 404512257 Upstream caches: cp5021 int Error: 429, Too many requests (f061ab2) at Fri, 23 Jan 2026 19:55:41 GMT Sensitive client information IP address: 158.108.32.49$ โดยที่ คือความยาวของ edge แล้วจำค่า ที่ต่ำสุดเอาไว้
ถ้าค่าที่ต่ำที่สุดในข้อ 2 เป็น ก็ให้ตอบว่าไม่มี cycle มิเช่นนั้นให้คืนมันเป็นคำตอบ

เราสามารถแสดงว่าคำตอบของอัลกอริทึมข้างบนคืนมาเป็นความยาวของ cycle ที่สั้นสุด ได้ดังต่อไปนี้

กรณีที่ 1: ถ้ากราฟไม่มี cycle เราจะได้ว่าสำหรับทุกๆ edge $Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } }$

Error

Too many requests (f061ab2)

(u,v)\,

จะไม่มี path จาก ไปยัง

u\,

ดังนั้น เสมอ ด้วยเหตุนี้ค่า ที่ต่ำที่สุดจึงมีค่าเท่ากับ และอัลกอริทึมข้างบนจะตอบว่ากราฟไม่มี cycle ได้อย่างถูกต้อง

กรณีที่ 2 ถ้ากราฟมี cycle เราจะได้ว่ามี edge อย่างน้อยหนึ่ง edge ที่ทำให้ $Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } }$

Error

Too many requests (f061ab2)

M[u,v]+\ell _{(u,v)}\,

มีค่าน้อยกว่า เราจะต้องแสดงว่าค่า ที่น้อยที่สุดคือความยาวของ cycle ที่สั้นที่สุด

อันดับแรก ให้พิจารณา edge ใดๆ เราได้ว่า คือความยาวของ shortest path จาก ไปยัง $u\,$ ด้วยเหตุนี้ จึงเป็นความยาวของ cycle ที่สั้นที่สุดที่มี edge $Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } }$

Error

Too many requests (f061ab2)

(u,v)\,

(เราสามารถแสดงว่าข้อความสุดท้ายนี้เป็นจริงได้โดยการสมมติให้เกิดข้อขัดแย้งว่า ไม่ใช่ความยาวของ cycle ที่สั้นที่สุดที่มี edge แต่เราจะได้ว่า cycle นั้นจะต้องมี path จาก ไปยัง และไม่มี path จาก v ไป u ที่มีความยาวน้อยกว่า

Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } } Error Too many requests (f061ab2) If you report this error to the Wikimedia System Administrators, please include the details below. Request served via cp5021 cp5021, Varnish XID 444573141 Upstream caches: cp5021 int Error: 429, Too many requests (f061ab2) at Fri, 23 Jan 2026 19:55:38 GMT Sensitive client information IP address: 158.108.32.49

แล้ว ทำให้เกิดข้อขัดแย้งขึ้น)

อันดับที่สอง เนื่องจาก cycle ที่สั้นที่สุดจะต้องผ่าน edge อย่างน้อย 1 edge เราจึงได้ว่าการนำความยาว cycle ที่สั้นที่สุดที่ผ่าน edge แต่ละ edge มาเปรียบเทียบกัน เพื่อหาความยาวที่น้อยที่สุดจะทำให้เราได้ความยาวของ cycle ที่สั้นที่สุดเสมอ

ด้วยเหตุนี้เราจึงสามารถสรุปได้ว่า ถ้ากราฟมี cycle แล้ว อัลกอริทึมข้างบนจะตอบความยาวของ cycle ที่สั้นที่สุดมาเสมอ

เราเห็นได้ชัดว่าการทำงานในขั้นตอนที่ 1 ของอัลกอริทึมข้างบนใช้เวลา $O(|V|^{3})\,$ และการทำงานขั้นที่สองใช้เวลา $Wikimedia Error * { margin: 0; padding: 0; } body { background: #fff; font: 15px/1.6 sans-serif; color: #333; } .content { margin: 7% auto 0; padding: 2em 1em 1em; max-width: 640px; display: flex; flex-direction: row; flex-wrap: wrap; } .footer { clear: both; margin-top: 14%; border-top: 1px solid #e5e5e5; background: #f9f9f9; padding: 2em 0; font-size: 0.8em; text-align: center; } img { margin: 0 2em 2em 0; } a img { border: 0; } h1 { margin-top: 1em; font-size: 1.2em; } .content-text { flex: 1; } p { margin: 0.7em 0 1em 0; } a { color: #0645ad; text-decoration: none; } a:hover { text-decoration: underline; } code { font-family: sans-serif; } summary { font-weight: bold; cursor: pointer; } details[open] { background: #970302; color: #dfdedd; } .text-muted { color: #777; } @media (prefers-color-scheme: dark) { a { color: #9e9eff; } body { background: transparent; color: #ddd; } .footer { border-top: 1px solid #444; background: #060606; } #logo { filter: invert(1) hue-rotate(180deg); } .text-muted { color: #888; } }$

Error

Too many requests (f061ab2)

O(|E|)=O(|V^{2}|)\,

ดังนั้นอัลกอริทึมข้างบนจึงทำงานได้ในเวลา

O(|V|^{3})\,

418531 ภาคต้น 2552/โจทย์ปัญหาการโปรแกรมพลวัต II/เฉลยข้อ 3

Error

Error

Error

Error

รายการเลือกการนำทาง

เครื่องมือส่วนตัว

เนมสเปซ

สิ่งที่แตกต่าง

ดู

เพิ่มเติม

ค้นหา

การนำทาง

เครื่องมือ