Dijkstra และ Bellman-Ford หาเส้นทางที่สั้นที่สุดได้อย่างไร

Question

Accepted Answer

ทั้งคู่หา **เส้นทางที่สั้นที่สุดจากแหล่งที่มา** ในกราฟที่มีน้ำหนัก **Dijkstra** เร็วกว่า แต่ต้องการน้ำหนัก **ไม่ติดลบ** ส่วน **Bellman-Ford** ช้ากว่า แต่ดำเนินการกับขอบ **ติดลบ** ได้ และตรวจหาวัฏจักรติดลบ

## Dijkstra (โลภ + min-heap)

ขยายโหนดที่ใกล้ที่สุดที่ยังไม่ได้เยี่ยมชมซ้ำแล้วซ้ำเล่า และผ่อนคลายเพื่อนบ้านของโหนดดังกล่าว

```python
import heapq

def dijkstra(graph, src):
    dist = {n: float('inf') for n in graph}
    dist[src] = 0
    pq = [(0, src)]                    # (distance, node)
    while pq:
        d, u = heapq.heappop(pq)       # closest first
        if d > dist[u]:
            continue
        for v, w in graph[u]:
            if d + w < dist[v]:        # relax edge
                dist[v] = d + w
                heapq.heappush(pq, (dist[v], v))
    return dist
```

## Bellman-Ford (การผ่อนคลายแบบ DP)

ผ่อนคลาย **ขอบทั้งหมด** V-1 ครั้ง การผ่อนคลายเพิ่มเติมหมายถึงวัฏจักรติดลบ

## การเปรียบเทียบ

| | Dijkstra | Bellman-Ford |
|---|---------|--------------||
| น้ำหนัก | ไม่ติดลบ | ใดๆ (รวมติดลบ) |
| เวลา | O((V+E) log V) | O(V·E) |
| วัฏจักรติดลบ | n/a | ตรวจหาได้ |

## เมื่อใดที่จะใช้ / ข้อผิดพลาด

ใช้ **Dijkstra** โดยค่าเริ่มต้นสำหรับน้ำหนักไม่ติดลบ (แผนที่ เครือข่าย) ใช้ **Bellman-Ford** เมื่อมีขอบติดลบ (เช่น การเก็งกำไร) Dijkstra ล้มเหลวเงียบ ๆ บนน้ำหนักติดลบ — อันตรายแบบดั้งเดิม

## ทำไมถึงสำคัญ

อัลกอริธึมเส้นทางที่สั้นที่สุดขับเคลื่อนการกำหนดเส้นทาง การนำทาง โปรโตคอลเครือข่าย และการวิเคราะห์ต้นทุนการพึ่งพา

การรู้ข้อจำกัดของน้ำหนักไม่ติดลบใน Dijkstra ช่วยป้องกันคำตอบที่ไม่ถูกต้องในช่องข้อมูล

แนวคิดการผ่อนคลายเชื่อมโยงวิธีการโลภและการคิดแบบ DP ซึ่งทำให้เป็นหัวข้อที่หลากหลายในระดับสูง