0Pricing
DSA Interview Prep · บทเรียน

Floyd-Warshall: เส้นทางสั้นที่สุดระหว่างทุกคู่

เติมเมทริกซ์ระยะทางระหว่างทุกคู่ด้วยอัลกอริทึม Floyd-Warshall แบบลูปซ้อนสามชั้น และนำไปหาจำนวนการกระโดดน้อยที่สุดระหว่างโหนดทุกคู่

Floyd-Warshall: เส้นทางสั้นที่สุดระหว่างทุกคู่ เป็นบทเรียน DSA Interview Prep ฟรีบน CoddyKit นี่คือบทเรียนที่ 3 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน DSA Interview Prep และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส DSA Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน

เส้นทางสั้นที่สุดระหว่างทุกคู่โหนด

ฟลอยด์–วอร์แชลล์ คำนวณเส้นทางสั้นที่สุดระหว่างโหนดทุกคู่ในกราฟที่มีน้ำหนัก รวมถึงกราฟที่มีเส้นเชื่อมติดลบ แต่ไม่รวมกราฟที่มีวงจรติดลบ การเรียกใช้ดิกซ์ตราจากต้นทางแต่ละโหนดมีความซับซ้อน O(V × (V+E) log V) ส่วนฟลอยด์–วอร์แชลล์ใช้เวลา O(V³) โดยไม่ขึ้นกับความหนาแน่นของเส้นเชื่อม สำหรับกราฟแบบหนาแน่นที่มี V ≤ 500 ฟลอยด์–วอร์แชลล์มักเขียนได้ง่ายกว่าและมีความเร็วใกล้เคียงกัน

แนวคิดหลัก: โหนดระหว่างทาง

แนวคิดของฟลอยด์–วอร์แชลล์คือ dp[i][j][k] = เส้นทางสั้นที่สุดจาก i ไปยัง j โดยใช้เฉพาะโหนดใน {0, 1, ..., k} เป็นโหนดระหว่างทาง เส้นทางสั้นที่สุดอาจใช้โหนด k เป็นโหนดระหว่างทาง หรือไม่ใช้ก็ได้ หากใช้: dp[i][j][k] = dp[i][k][k-1] + dp[k][j][k-1] หากไม่ใช้: dp[i][j][k] = dp[i][j][k-1] เนื่องจากมิติที่สามดำเนินไปข้างหน้าเพียงทิศทางเดียว จึงสามารถตัดออกได้ และปรับปรุงค่าในที่เดิม

การกำหนดค่าเริ่มต้นให้เมทริกซ์ระยะทาง

เริ่มต้นด้วยเมทริกซ์ขนาด V×V: dist[i][i] = 0 (ระยะทางจากโหนดไปยังตัวเองเป็นศูนย์), dist[i][j] = weight สำหรับเส้นเชื่อมโดยตรง และ dist[i][j] = inf สำหรับคู่ที่ไม่มีเส้นเชื่อม จากนั้นวนผ่านโหนดระหว่างทางทั้งหมด k และปรับปรุงคู่ (i, j) ลูปภายนอกที่วนผ่าน k ต้องอยู่ก่อน เพื่อให้เราสร้างเส้นทางผ่านชุดโหนดระหว่างทางที่อนุญาตซึ่งเพิ่มขึ้นทีละขั้นได้อย่างถูกต้อง

def floyd_warshall(V, edges):
    INF = float('inf')
    dist = [[INF]*V for _ in range(V)]
    for i in range(V):
        dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = w  # directed graph
    
    for k in range(V):       # intermediate node
        for i in range(V):
            for j in range(V):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    
    return dist

การใช้งานฉบับสมบูรณ์พร้อมตัวอย่าง

มาลองติดตามการทำงานของฟลอยด์–วอร์แชลล์บนกราฟที่มี 4 โหนดกัน หลังจากประมวลผลโหนดระหว่างทางแต่ละโหนด เมทริกซ์จะถูกเติมด้วยเส้นทางที่สั้นลงซึ่งผ่านโหนดนั้น อัลกอริทึมนี้รองรับการเดินทางผ่านหลายเส้นเชื่อมได้ตามธรรมชาติ โดยค่อย ๆ สร้างเส้นทางสั้นที่สุดขึ้นทีละขั้น

def floyd_warshall(V, edges):
    INF = float('inf')
    dist = [[INF]*V for _ in range(V)]
    for i in range(V):
        dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = w
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if dist[i][k] != INF and dist[k][j] != INF:
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist

V = 4
edges = [(0,1,3),(0,2,7),(1,2,1),(1,3,5),(2,3,2)]
dist = floyd_warshall(V, edges)
for row in dist:
    print([x if x != float('inf') else 'INF' for x in row])

การตรวจจับวงจรติดลบ

หลังจากเรียกใช้ฟลอยด์–วอร์แชลล์แล้ว ให้ตรวจสอบเส้นทแยงมุมหลัก: หากมี dist[i][i] < 0 แสดงว่ามีวงจรติดลบที่ผ่านโหนด i สาเหตุคือวงจรติดลบทำให้สามารถเดินทางจาก i กลับมายัง i ด้วยต้นทุนติดลบได้ หากไม่มีวงจรติดลบ ค่าทุกตัวบนเส้นทแยงมุมจะยังคงเป็น 0

def has_negative_cycle_fw(V, edges):
    dist = floyd_warshall(V, edges)
    for i in range(V):
        if dist[i][i] < 0:
            return True  # negative cycle through node i
    return False

# Negative cycle: 0->1->2->0 with weights 1,-3,1 (sum=-1)
edges_neg = [(0,1,1),(1,2,-3),(2,0,1)]
print(has_negative_cycle_fw(3, edges_neg))  # True

การสร้างเส้นทางขึ้นใหม่

หากต้องการสร้างเส้นทางจริงจาก i ไปยัง j ขึ้นใหม่ ให้เก็บเมทริกซ์ next[i][j] ไว้ โดยเริ่มต้นกำหนด next[i][j] = j สำหรับเส้นเชื่อมโดยตรง เมื่อปรับปรุงผ่านโหนดระหว่างทาง k ให้กำหนด next[i][j] = next[i][k] การกู้คืนเส้นทางทำได้โดยเริ่มที่ i แล้วตามตัวชี้ next จนถึง j วิธีนี้ใช้พื้นที่เพิ่ม O(V²) และใช้เวลา O(V) ต่อการสร้างเส้นทางหนึ่งเส้นขึ้นใหม่

def fw_with_path(V, edges):
    INF = float('inf')
    dist = [[INF]*V for _ in range(V)]
    nxt = [[None]*V for _ in range(V)]
    for i in range(V): dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = w; nxt[u][v] = v
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
                    nxt[i][j] = nxt[i][k]
    return dist, nxt

def get_path(nxt, i, j):
    if nxt[i][j] is None: return []
    path = [i]
    while i != j:
        i = nxt[i][j]; path.append(i)
    return path

การปิดแบบสกรรม

รูปแบบที่ง่ายกว่าคือการปิดแบบสกรรม ซึ่งตอบคำถามว่า “โหนด j สามารถเข้าถึงได้จากโหนด i หรือไม่” สำหรับทุกคู่โหนด ให้แทนที่ระยะทางด้วยค่าบูลีน: reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j]) นี่คือฟลอยด์–วอร์แชลล์ที่ใช้บูลีน OR แทนการบวกและการหาค่าต่ำสุด กำหนดค่าเริ่มต้นให้ reach[i][i] = True และกำหนด reach[i][j] = True สำหรับเส้นเชื่อมโดยตรง

def transitive_closure(V, edges):
    reach = [[False]*V for _ in range(V)]
    for i in range(V):
        reach[i][i] = True
    for u, v, _ in edges:
        reach[u][v] = True
    for k in range(V):
        for i in range(V):
            for j in range(V):
                reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j])
    return reach

edges = [(0,1,1),(1,2,1)]
R = transitive_closure(3, edges)
print(R[0][2])  # True (0 can reach 2 via 0->1->2)

ความซับซ้อนและกรณีที่ควรใช้

ฟลอยด์–วอร์แชลล์: เวลา O(V³) และพื้นที่ O(V²) สำหรับกราฟแบบหนาแน่น (E ≈ V²) ที่มี V ≤ 300 วิธีนี้เร็วกว่าการเรียกใช้ดิกซ์ตรา V ครั้ง ซึ่งในกรณีนั้นมีความซับซ้อน O(V³) เช่นกัน สำหรับกราฟแบบเบาบางที่มี V = 1000 และ E = 3000 การเรียกใช้ดิกซ์ตรา V ครั้งมีต้นทุน O(V×E×log V) ≈ 33M ขณะที่ฟลอยด์–วอร์แชลล์มีต้นทุน O(V³) = 10⁹ ดังนั้นดิกซ์ตราจึงชนะ ควรทราบว่าแต่ละอัลกอริทึมเหมาะกับกรณีใด

จำนวนก้าวขั้นต่ำระหว่างทุกคู่

กำหนดน้ำหนักของเส้นเชื่อมทั้งหมดเป็น 1 (หรือใช้เมทริกซ์การเชื่อมโยงแบบบูลีนร่วมกับฟลอยด์–วอร์แชลล์ โดยใช้การบวกแทนการหาค่าต่ำสุด): dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) วิธีนี้คำนวณจำนวนก้าวขั้นต่ำระหว่างทุกคู่ ซึ่งเป็นผลลัพธ์ BFS ระหว่างทุกคู่ แต่คำนวณด้วยการประมวลผลฟลอยด์–วอร์แชลล์แบบ O(V³) เพียงครั้งเดียว

def min_hops_all_pairs(V, adj_list):
    INF = float('inf')
    dist = [[INF]*V for _ in range(V)]
    for i in range(V):
        dist[i][i] = 0
        for j in adj_list[i]:
            dist[i][j] = 1
    for k in range(V):
        for i in range(V):
            for j in range(V):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist

adj = [[1,2],[2],[3],[],[]]
print(min_hops_all_pairs(5, adj)[0])  # [0, 1, 1, 2, INF]

บริบทการสัมภาษณ์งาน: เมื่อผู้สัมภาษณ์ถามเกี่ยวกับฟลอยด์–วอร์แชลล์

ฟลอยด์–วอร์แชลล์มักปรากฏในการสัมภาษณ์งานในโจทย์ที่เกี่ยวกับ: (1) ระยะทางระหว่างทุกคู่บนกราฟขนาดเล็ก (2) การตรวจสอบว่ามีวงจรที่มีน้ำหนักรวมติดลบอยู่หรือไม่ (3) การคำนวณเส้นทางสั้นที่สุดในปัญหาการส่งต่อข้อจำกัด และ (4) โจทย์ที่ระบุให้ใช้วิธีแก้ปัญหา O(V³) โดยตรง เมื่อ V ≤ 200 ควรกล่าวถึงโครงสร้างลูปสามชั้นและข้อกำหนดว่าต้องไม่มีวงจรที่มีน้ำหนักรวมติดลบเพื่อให้ผลลัพธ์ถูกต้องเสมอ

กราฟไม่มีทิศทางกับฟลอยด์–วอร์แชลล์

สำหรับกราฟไม่มีทิศทาง ให้เพิ่มเส้นเชื่อมทั้งสองทิศทางสำหรับแต่ละเส้นเชื่อม: dist[u][v] = dist[v][u] = weight ส่วนที่เหลือของอัลกอริทึมเหมือนเดิม เมทริกซ์ผลลัพธ์จะสมมาตร: dist[i][j] == dist[j][i] สำหรับทุกคู่ ขณะกำหนดค่าเริ่มต้น โปรดระวังอย่ากำหนดเส้นเชื่อมแบบมีทิศทางโดยไม่ตั้งใจ เพราะต้องเพิ่มเส้นเชื่อมไม่มีทิศทางลงในเมทริกซ์เริ่มต้นทั้งสองทิศทางก่อนเรียกใช้ลูปสามชั้น

def fw_undirected(V, edges):
    INF = float('inf')
    dist = [[INF]*V for _ in range(V)]
    for i in range(V): dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = w
        dist[v][u] = w  # both directions for undirected
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

ตรวจสอบความเข้าใจ

ทดสอบความเข้าใจแนวคิดโครงสร้างข้อมูลและอัลกอริทึม — การเตรียมตัวสัมภาษณ์การเขียนโปรแกรมจากบทเรียนนี้

ทบทวนบทเรียน

ในบทเรียนนี้ คุณได้เรียนรู้ว่า ฟลอยด์–วอร์แชลล์คำนวณเส้นทางสั้นที่สุดระหว่างทุกคู่ด้วยลูปซ้อนกันสามชั้นและความสัมพันธ์เวียนเกิด dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) ตรวจจับวงจรที่มีน้ำหนักรวมติดลบได้โดยตรวจสอบว่า dist[i][i] < 0 หรือไม่หลังการประมวลผลเสร็จสิ้น และ อัลกอริทึมนี้ใช้เวลา O(V³) และพื้นที่ O(V²) บทถัดไป เราจะกลับมาดูการประยุกต์ใช้เส้นทางสั้นที่สุดด้วยปัญหาเวลาหน่วงของเครือข่ายและเทคนิคการสร้างเส้นทางกลับคืน

คำถามที่พบบ่อย

บทเรียน “Floyd-Warshall: เส้นทางสั้นที่สุดระหว่างทุกคู่” ฟรีหรือไม่

ใช่ — ข้อความเต็มของ “Floyd-Warshall: เส้นทางสั้นที่สุดระหว่างทุกคู่” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส DSA Interview Prep ให้อัปเกรดเป็น CoddyKit PRO คอร์ส DSA Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน

คุณจะเรียนรู้อะไรในบทเรียน “Floyd-Warshall: เส้นทางสั้นที่สุดระหว่างทุกคู่”

เติมเมทริกซ์ระยะทางระหว่างทุกคู่ด้วยอัลกอริทึม Floyd-Warshall แบบลูปซ้อนสามชั้น และนำไปหาจำนวนการกระโดดน้อยที่สุดระหว่างโหนดทุกคู่ คุณปฏิบัติ DSA Interview Prep ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน

คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน DSA Interview Prep หรือไม่

ไม่จำเป็นต้องมีประสบการณ์มาก่อน DSA Interview Prep บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 3 จากทั้งหมด 4 บทเรียน

บทเรียน “Floyd-Warshall: เส้นทางสั้นที่สุดระหว่างทุกคู่” ใช้เวลานานแค่ไหน

บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย

ฉันเขียนและรันโค้ดในบทเรียน DSA Interview Prep นี้ได้ไหม

ได้ บทเรียน DSA Interview Prep ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ

บทเรียนทั้งหมดในหลักสูตรนี้

  1. อัลกอริทึมของ Dijkstra กับคิวลำดับความสำคัญ
  2. Bellman-Ford และวงจรน้ำหนักลบ
  3. Floyd-Warshall: เส้นทางสั้นที่สุดระหว่างทุกคู่
  4. เวลาหน่วงของเครือข่ายและการสร้างเส้นทางกลับคืน
← กลับไปที่ DSA Interview Prep