กราฟถ่วงน้ำหนักและกราฟแบบมีทิศทางคืออะไร และปัญหาใดที่พวกมันสร้างแบบจำลอง

Question

Accepted Answer

ในกราฟ**แบบมีทิศทาง** (digraph) ขอบมี**ทิศทาง** (`A → B` ≠ `B → A`) ในกราฟ**ถ่วงน้ำหนัก** ขอบแต่ละเส้นมี**ต้นทุนตัวเลข** (ระยะทาง เวลา ความจุ) การรวมกันของทั้งสองจำลองระบบจริงโดยที่ความสัมพันธ์เป็นทางเดียวและมีต้นทุน

## การแทนค่า

```text
Weighted directed graph:
  A --5--> B
  A --2--> C
  C --1--> B
Adjacency list with weights:
  A: [(B,5), (C,2)]
  B: []
  C: [(B,1)]
```

```python
graph = {
    'A': [('B', 5), ('C', 2)],   # directed, weighted edges
    'B': [],
    'C': [('B', 1)],
}
# Shortest A->B is A->C->B = 2 + 1 = 3, not the direct edge 5.
```

## สิ่งที่พวกมันสร้างแบบจำลอง

| โดเมน | จุดยอด | ขอบถ่วงน้ำหนักแบบมีทิศทาง |
|---|---|---|
| แผนที่ / GPS | สี่แยก | ถนนทางเดียว + เวลาการเดินทาง |
| เครือข่าย | เราเตอร์ | ลิงก์ + เวลาแฝง/แบนด์วิดท์ |
| การตั้งตารางงาน | งาน | การพึ่งพา + ระยะเวลา |
| การเงิน | สกุลเงิน | อัตราแลกเปลี่ยน |

## อัลกอริทึมหลัก

| วัตถุประสงค์ | อัลกอริทึม | ความซับซ้อน |
|---|---|---|
| เส้นทางที่สั้นที่สุด (น้ำหนักไม่เป็นลบ) | Dijkstra | O((V+E) log V) |
| เส้นทางที่สั้นที่สุด (ขอบลบ) | Bellman-Ford | O(VE) |
| การเรียงลำดับที่มีการพึ่งพา | การเรียงลำดับโทโพโลยี | O(V+E) |
| ตรวจจับรอบ / ความสามารถในการเข้าถึง | DFS | O(V+E) |

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

ทิศทางและน้ำหนักคือสิ่งที่เปลี่ยนกราฟที่เป็นนามธรรมให้เป็นแบบจำลองที่น่าเชื่อถือสำหรับปัญหาการกำหนดเส้นทาง การตั้งตารางเวลา และการพึ่งพาที่ขับเคลื่อนแอปพลิเคชันจริง

การเลือกอัลกอริทึมขึ้นอยู่กับคุณสมบัติเหล่านี้ — ตัวอย่างเช่น น้ำหนักลบตัดทิ้ง Dijkstra และต้องการ Bellman-Ford

โดเมน	จุดยอด	ขอบถ่วงน้ำหนักแบบมีทิศทาง
แผนที่ / GPS	สี่แยก	ถนนทางเดียว + เวลาการเดินทาง
เครือข่าย	เราเตอร์	ลิงก์ + เวลาแฝง/แบนด์วิดท์
การตั้งตารางงาน	งาน	การพึ่งพา + ระยะเวลา
การเงิน	สกุลเงิน	อัตราแลกเปลี่ยน

วัตถุประสงค์	อัลกอริทึม	ความซับซ้อน
เส้นทางที่สั้นที่สุด (น้ำหนักไม่เป็นลบ)	Dijkstra	O((V+E) log V)
เส้นทางที่สั้นที่สุด (ขอบลบ)	Bellman-Ford	O(VE)
การเรียงลำดับที่มีการพึ่งพา	การเรียงลำดับโทโพโลยี	O(V+E)
ตรวจจับรอบ / ความสามารถในการเข้าถึง	DFS	O(V+E)