---
# System prepended metadata

title: กราฟ (Graph)

---

# 1. การแทนค่ากราฟ

การแทนค่ากราฟเป็นแนวคิดพื้นฐานในวิทยาการคอมพิวเตอร์ กราฟ $G$ นิยามว่าเป็นคู่ $(V, E)$ โดยที่:
- $V$ คือเซตของจุด (vertices)
- $E$ คือเซตของขอบ (edges)

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

> **หมายเหตุ:** 
> โจทย์ส่วนใหญ่กำหนด index เป็นเลข 1 ถึง n แต่ตามปกติแล้ว array หรือ vector ขนาด n จะรองรับได้แค่เลข 0 ถึง n-1 เท่านั้น มีวิธีแก้ปัญหาสองแบบคือ
> - เมื่อ input ต้องการให้จัดการกับข้อมูล ณ ตำแหน่ง x ก็ให้เลื่อนมาจัดการกับตำแหน่ง x-1 ใน array จริง ๆ แทน
> - กำหนดขนาดของ array เป็น n+1 เพื่อที่จะได้ใช้ตำแหน่ง n ได้ ส่วนตำแหน่ง 0 เราจะไม่พิจารณาเลย


## 1.1 เมทริกซ์ความสัมพันธ์ (Adjacency Matrix)

### นิยาม
เมทริกซ์ความสัมพันธ์สำหรับกราฟที่มี $N$ จุด คือเมทริกซ์ขนาด $N \times N$ โดยที่แต่ละองค์ประกอบ $a_{ij}$ แสดงถึงการมีอยู่ของขอบจากจุด $i$ ไปยังจุด $j$ โดยมีเงื่อนไขดังนี้:
- $a_{ij} = 1$ ถ้ามีขอบจาก $i$ ไป $j$
- $a_{ij} = 0$ หากไม่มีขอบ

ในกราฟที่ไม่มีทิศทาง เมทริกซ์จะเป็นแบบสมมาตร คือ $a_{ij} = a_{ji}$


#### ตัวอย่าง

![Screenshot 2025-03-15 at 19.17.30](https://hackmd.io/_uploads/B1oble7nkl.png)


สำหรับกราฟที่มีจุด $V = \{1, 2, 3, 4\}$ และขอบ $E = \{(1,2), (2,3), (2,4),(3,4), (4,1)\}$ เมทริกซ์ความสัมพันธ์จะเป็น:

![Screenshot 2025-03-15 at 19.19.27](https://hackmd.io/_uploads/BkEvxlX3kg.png)

โดยเมทริกซ์สามารถสร้างได้ด้วย

```cpp
int adj[5][5];
adj[1][2] = 1;
adj[2][3] = 1;
adj[2][4] = 1;
adj[3][4] = 1;
adj[4][1] = 1;
```

### การแทนค่ากราฟแบบมีน้ำหนัก (Weighted Graph Representation)

ในกราฟที่มีน้ำหนัก (weighted graph) การแทนค่าด้วยเมทริกซ์ความสัมพันธ์ สามารถปรับขยายได้โดยให้เมทริกซ์บรรจุน้ำหนักของขอบ (edge weight) ในตำแหน่งที่มีขอบอยู่ แทนที่จะเป็นเพียงค่า 1 หรือ 0 ดังนี้:

- ถ้ามีขอบจาก $v_i$ ไปยัง $v_j$ ที่มีน้ำหนัก $w$ ให้กำหนดค่า $a_{ij} = w$
- ถ้าไม่มีขอบระหว่าง $v_i$ กับ $v_j$ ให้กำหนดค่า $a_{ij} = \infty$ (หรือใช้ค่าพิเศษอื่น ๆ แทนการไม่มีขอบ)
- สำหรับกราฟที่ไม่มีทิศทาง เมทริกซ์จะมีความสมมาตร คือ $a_{ij} = a_{ji}$ และโดยทั่วไปจะกำหนดให้ $a_{ii} = 0$ สำหรับทุก $i$ เพราะระยะทางจากจุดหนึ่งไปยังตัวมันเองเท่ากับ 0


พิจารณากราฟที่มีจุดและมีขอบดังนี้:

![Screenshot 2025-03-15 at 19.27.44](https://hackmd.io/_uploads/rJWUfeQhyl.png)


เมทริกซ์ความสัมพันธ์สำหรับกราฟนี้จะเป็น:

![Screenshot 2025-03-15 at 19.25.50](https://hackmd.io/_uploads/B1m1flXnJx.png)

โดยเมทริกซ์สามารถสร้างได้ด้วย

```cpp
int adj[5][5];
adj[1][2] = 5;
adj[2][3] = 7;
adj[2][4] = 6;
adj[3][4] = 5;
adj[4][1] = 2;
```

### ข้อดีและข้อเสีย
- **ข้อดี:**
  - เข้าใจง่ายและเหมาะสำหรับการตรวจสอบการมีอยู่ของขอบระหว่างจุดสองจุดในเวลา $O(1)$
- **ข้อเสีย:**
  - ใช้พื้นที่ $O(N^2)$ ซึ่งไม่เหมาะกับกราฟที่มีจุดจำนวนมากแต่มีขอบน้อย (sparse graph)

---

## 1.2 รายชื่อเพื่อนบ้าน (Adjacency List)

### นิยาม
การแทนค่าด้วยรายชื่อเพื่อนบ้านคือการเก็บข้อมูลของแต่ละจุด $v$ โดยมีลิสต์ที่บรรจุจุดที่เชื่อมต่อกับ $v$ โดยสามารถสร้างได้ด้วย

```cpp
vector<int> adj[N];
```

#### ตัวอย่าง

![Screenshot 2025-03-15 at 19.38.42](https://hackmd.io/_uploads/Bk81Sl73ye.png)


สำหรับกราฟเดียวกัน $V = \{1, 2, 3, 4\}$ และขอบ $E = \{(1,2), (2,3), (2,4),(3,4), (4,1)\}$ รายชื่อเพื่อนบ้านจะเป็น:
- $L(1) = \{2\}$
- $L(2) = \{3, 4\}$
- $L(3) = \{4\}$
- $L(4) = \{1\}$

**ตัวอย่างโค้ดในภาษา C++:**
```cpp
vector<int> adj[5]; // สำหรับ 4 จุด ไม่สนใจจุดยอด 0
adj[1].push_back(2);
adj[2].push_back(3);
adj[2].push_back(4);
adj[3].push_back(4);
adj[4].push_back(1);
```

หากประมวลผลกราฟที่ไม่มีทิศทางจะต้องใส่เพื่อนบ้านทั้งสองทิศทาง เช่น หากมีขอบ $(1, 2)$

```cpp
adj[1].push_back(2);
adj[2].push_back(1);
```

### การแทนค่ากราฟแบบมีน้ำหนัก

การแทนค่ากราฟแบบมีน้ำหนักสามารถทำได้โดยเก็บค่าเพื่อนบ้านเป็น `pair<int, int>` ซึ่งแสดงถึงเพือนบ้านและน้ำหนัก

```cpp
vector<pair<int,int>> adj[N];
```

#### ตัวอย่าง

![Screenshot 2025-03-15 at 19.27.44](https://hackmd.io/_uploads/ByDiLg7hke.png)

สามารถสร้างได้โดย

```cpp
vector<pair<int,int>> adj[5];
adj[1].push_back({2,5});
adj[2].push_back({3,7});
adj[2].push_back({4,6});
adj[3].push_back({4,5});
adj[4].push_back({1,2});
```

### การเข้ถึงเพื่อนบ้านทำได้ง่ายโดย

```cpp
for (auto u : adj[s]) {
    // process node u
}
```

### ข้อดีและข้อเสีย
- **ข้อดี:**
  - ใช้พื้นที่ $O(N + M)$ เมื่อ $M$ คือจำนวนขอบ
  - เหมาะสำหรับการเข้าถึงเพื่อนบ้านของจุดหนึ่ง ๆ ได้อย่างรวดเร็ว
- **ข้อเสีย:**
  - การตรวจสอบว่ามีขอบระหว่างจุด $u$ กับ $v$ อาจต้องใช้เวลา $O(\text{degree}(u))$ ในกรณีที่แย่ที่สุด

---

## 1.3 รายชื่อขอบ (Edge List)

### นิยาม
รายชื่อขอบคือการแทนค่ากราฟโดยการเก็บรายการของขอบแต่ละอัน ซึ่งแต่ละขอบจะถูกแทนด้วย:
- คู่ $(u, v)$ สำหรับกราฟที่ไม่มีน้ำหนัก
- หรือทริปเปิล $(u, v, w)$ สำหรับกราฟที่มีน้ำหนัก

#### ตัวอย่าง

![Screenshot 2025-03-15 at 19.38.42](https://hackmd.io/_uploads/Bk81Sl73ye.png)

```cpp
vector<pair<int,int>> edges;
edges.push_back({1,2});
edges.push_back({2,3});
edges.push_back({2,4});
edges.push_back({3,4});
edges.push_back({4,1});
```

#### ตัวอย่าง

![Screenshot 2025-03-15 at 19.27.44](https://hackmd.io/_uploads/ByDiLg7hke.png)

สามารถสร้างได้โดย

```cpp
vector<tuple<int,int,int>> edges;
edges.push_back({1,2,5});
edges.push_back({2,3,7});
edges.push_back({2,4,6});
edges.push_back({3,4,5});
edges.push_back({4,1,2});
```


### ข้อดีและข้อเสีย
- **ข้อดี:**
  - การแทนค่าเรียบง่ายและตรงไปตรงมา
  - เหมาะสำหรับอัลกอริทึมที่ต้องเรียงลำดับขอบ เช่น Kruskal’s MST
- **ข้อเสีย:**
  - ไม่เหมาะสำหรับการตรวจสอบว่ามีขอบระหว่างจุดสองจุดในเวลาเร็ว
  - การเข้าถึงเพื่อนบ้านของจุดหนึ่งต้องสแกนรายชื่อขอบทั้งหมด

## สรุป

การเลือกวิธีการแทนค่ากราฟขึ้นอยู่กับลักษณะของกราฟและปัญหาที่ต้องแก้:
- **เมทริกซ์ความสัมพันธ์** เหมาะสำหรับกราฟที่หนาแน่นและต้องการตรวจสอบขอบได้ในเวลา $O(1)$
- **รายชื่อเพื่อนบ้าน** เหมาะสำหรับกราฟที่มีขอบน้อย (sparse graph) ด้วยการใช้พื้นที่ $O(N + M)$
- **รายชื่อขอบ** มีความเรียบง่ายและเหมาะสำหรับอัลกอริทึมที่ต้องประมวลผลขอบทั้งหมด เช่น Kruskal’s MST
- https://visualgo.net/en/graphds

---

# 2. Graph Traversal

อัลกอริทึมกราฟพื้นฐานที่สำคัญสองแบบ ได้แก่ การค้นหาด้วยความลึก (Depth-First Search, DFS) และการค้นหาด้วยความกว้าง (Breadth-First Search, BFS) โดยทั้งสองอัลกอริทึมจะได้รับจุดเริ่มต้นในกราฟ และทำการเยี่ยมชมทุกโหนดที่สามารถเข้าถึงได้จากจุดเริ่มต้นนั้น ความแตกต่างระหว่างอัลกอริทึมทั้งสองอยู่ที่ลำดับในการเยี่ยมชมโหนดแต่ละตัว

## 2.1 การค้นหาด้วยความลึกก่อน (Depth-First Search, DFS)

การค้นหาด้วยความลึกก่อน (Depth-first search, DFS) เป็นเทคนิคการท่องกราฟที่ตรงไปตรงมา โดยอัลกอริทึมจะเริ่มต้นจากโหนดเริ่มต้นหนึ่ง แล้วดำเนินการไปยังโหนดอื่น ๆ ที่สามารถเข้าถึงได้จากโหนดเริ่มต้นผ่านทางขอบของกราฟ

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

### การเขียน DFS
การค้นหาด้วยความลึกก่อน สามารถเขียนได้อย่างสะดวกโดยใช้การเรียกซ้ำ (recursive) โดยจะเริ่มต้นการค้นหาด้วยความลึกจากโหนดที่กำหนด

```cpp=
vector<int> adj[N];
bool visited[N]; //ตั้งค่าเริ่มต้นเป็น false 

void dfs(int s) {
    if (visited[s]) return;
    visited[s] = true;
    // process node s
    for (auto u: adj[s]) {
        dfs(u);
    }
}
```

## 2.1 การค้นหาด้วยความกว้างก่อน (Breadth-First Search,BFS)

การค้นหาด้วยความกว้างก่อน (Breadth-first search, BFS) จะเข้าถึงโหนดต่าง ๆ ตามลำดับที่เพิ่มขึ้นของระยะห่างจากโหนดเริ่มต้น ด้วยเหตุนี้เราสามารถคำนวณระยะห่างจากโหนดเริ่มต้นไปยังโหนดอื่น ๆ ด้วยการใช้ BFS

### การเขียน BFS
โดยทั่วไปแล้วเราจะใช้คิวในการจัดการโหนดที่ยังรอการประมวลผล สำหรับ BFS ซึ่งในแต่ละขั้นตอนจะประมวลผลโหนดที่อยู่ด้านหน้าของคิว จากนั้นจึงเพิ่มโหนดที่ยังไม่เยี่ยมชมที่อยู่ติดกันลงไปในท้ายคิว

```cpp=
queue<int> q;
bool visited[N];
int distance[N];

visited[x] = true;
distance[x] = 0;
q.push(x);
while (!q.empty()) {
    int s = q.front(); q.pop();
    // process node s
    for (auto u : adj[s]) {
        if (visited[u]) continue;
        visited[u] = true;
        distance[u] = distance[s]+1;
        q.push(u);
    }
}
```

## 2.3 การประยุกต์ใช้งาน Graph Traversal

### 2.3.1 การตรวจับ Cycle ใน Undirected Graph ด้วย DFS
ในการตรวจจับ Cycle ในกราฟที่ไม่มีทิศทางโดยใช้ DFS จะทำการเข้าถึงโหนดตามเส้นทางหนึ่งอย่างต่อเนื่องจนกว่าจะไม่สามารถค้นพบโหนดใหม่ได้ ระหว่างทางจะบันทึกโหนดที่เยี่ยมชมแล้วไว้ในอาร์เรย์ visited เพื่อป้องกันการประมวลผลซ้ำ อีกทั้งยังต้องบันทึกข้อมูลของโหนดพ่อแม่ (parent) สำหรับแต่ละโหนดในเส้นทาง เพื่อให้สามารถแยกแยะระหว่างการกลับมาผ่าน edge เดิม (ซึ่งไม่ถือว่าเป็น cycle) กับการพบโหนดที่เคยเยี่ยมชมในเส้นทาง DFS ปัจจุบัน (ซึ่งหมายความว่ามี cycle เกิดขึ้น) 

![Screenshot 2025-03-15 at 23.20.26](https://hackmd.io/_uploads/rJLkKQXn1e.png)

**ข้อสังเกต**
- การเก็บข้อมูล parent:
เนื่องจากในกราฟไม่มีทิศทาง โหนด $u$ อาจเชื่อมกับโหนด $v$ และในระหว่างการ DFS อาจมีการเดินทางจาก $u$ ไป $v$ แล้วกลับจาก $v$ ไป $u$ ผ่าน edge เดิมได้ ดังนั้นจึงต้องบันทึกข้อมูล parent เพื่อไม่ให้เกิดการนับซ้ำ
- การตรวจสอบทุกส่วนของกราฟ:
เนื่องจากกราฟอาจประกอบด้วยหลายส่วน (disconnected components) จึงต้องทำการเรียก DFS สำหรับโหนดที่ยังไม่ถูกเยี่ยมชม เพื่อให้แน่ใจว่าได้ตรวจจับ cycle ครบทุกส่วนของกราฟ

**ตัวอย่างโปรแกรม**
```cpp=
// กำหนดขนาดสูงสุดของกราฟ
const int N = 1001;
bool visited[N]; // อาร์เรย์สำหรับบันทึกว่าโหนดถูกเยี่ยมชมแล้วหรือไม่

// ฟังก์ชัน DFS สำหรับตรวจจับ cycle
// u คือโหนดปัจจุบัน, p คือ parent ของ u ในเส้นทาง DFS
bool dfs(int u, int p) {
    // ถ้าโหนด u ถูกเยี่ยมชมแล้วในเส้นทาง DFS ปัจจุบัน
    // หมายความว่าได้เจอ cycle แล้ว
    if (visited[u])
        return true;
    
    visited[u] = true;
    
    // วนรอบโหนดที่อยู่ติดกับ u
    for (int v : G[u]) {
        // ข้ามโหนดที่เป็น parent ของ u เพื่อป้องกันการนับ edge เดิมซ้ำ
        if (v == p)
            continue;
        // ถ้า DFS จากโหนด v พบ cycle ให้ return true ทันที
        if (dfs(v, u))
            return true;
    }
    
    return false; // หากวนรอบทุกโหนดแล้วไม่พบ cycle
}

// ใน main function:
bool found_cycle = false;
for (int u = 1; u <= n; ++u) {
    // ตรวจสอบทุกโหนดในกราฟ เพราะกราฟอาจไม่เชื่อมต่อกันทั้งหมด
    if (!visited[u]) {
        if (dfs(u, -1)) { // ใช้ -1 เป็น parent ของโหนดเริ่มต้น
            found_cycle = true;
            break;
        }
    }
}

if (found_cycle)
    cout << "มี cycle" << "\n";
else
    cout << "ไม่มี cycle" << "\n";
```

### 2.3.2 การตรวจับ Cycle ใน Directed Graph ด้วย DFS
การตรวจจับ cycle ในกราฟที่มีทิศทางด้วย DFS จำเป็นต้องใช้ตัวแปรสีแทนการใช้แค่ visited array เนื่องจากปัญหาการประมวลผลที่เกิดจากการเยี่ยมชมในรอบของ DFS ที่ต่างกัน โดยจะกำหนดสถานะของแต่ละโหนดด้วยสีดังนี้:
- สีขาว (color 0): โหนดยังไม่ได้ถูกเยี่ยมชมเลย
- สีเทา (color 1): โหนดถูกเยี่ยมชมแล้วและกำลังอยู่ในกระบวนการ DFS (อยู่ใน recursion stack)
- สีดำ (color 2): โหนดถูกเยี่ยมชมแล้วและได้ทำการประมวลผลลูกของมันครบถ้วนแล้ว

**กระบวนการทำงาน**
- ในตอนแรก ทุกโหนดจะถูกกำหนดเป็นสีขาว (ค่าเริ่มต้นเป็น 0)
- เมื่อเริ่มต้น DFS จากโหนดหนึ่ง เราจะเปลี่ยนสถานะของโหนดนั้นเป็นสีเทา (1) เพื่อบอกว่าโหนดนั้นกำลังอยู่ในกระบวนการ DFS
- จากนั้นจะทำการเยี่ยมชมโหนดที่ติดกัน ถ้าเจอโหนดใดที่อยู่ในสถานะสีเทา (gray) หมายความว่าโหนดนั้นกำลังอยู่ใน stack อยู่แล้ว นั่นคือเราได้พบ cycle
- หลังจากเยี่ยมชมและประมวลผลลูกของโหนดครบแล้ว เราจะเปลี่ยนสถานะของโหนดนั้นเป็นสีดำ (2) เพื่อบ่งบอกว่าโหนดนั้นได้รับการประมวลผลอย่างสมบูรณ์แล้ว


**เหตุผลของการใช้ 3 สี**
ยกตัวอย่างกราฟ 

`2->1->3`

ในกรณีนี้ หากเราใช้เพียง visited array ในการตรวจจับ cycle โดยเริ่ม DFS จาก node 1 ก่อน เราจะทำให้ `visited[1] = true` และ `visited[3] = true` ซึ่งหมายความว่าเมื่อภายหลังเราเริ่ม DFS จาก node 2 แล้วจะพบว่า node 1 ถูก visited ไปแล้ว ทำให้ดูเหมือนว่าเกิด cycle ขึ้น (เพราะเจอ node 1 ที่เคยเยี่ยมชมแล้ว) แต่ความจริงแล้วในกราฟนี้ไม่มี cycle เกิดขึ้น เนื่องจากการเยี่ยมชม node 1 ในรอบ DFS จาก node 2 นั้นเป็นการเยี่ยมชมในบริบทของ DFS รอบใหม่ ไม่ใช่ใน DFS เดียวกัน

**ตัวอย่างโปรแกรม**
```cpp=
const int N = 1001;
int color[N]; // เริ่มต้นทุกโหนดเป็นสีขาว (0)

// ฟังก์ชัน DFS สำหรับตรวจจับ cycle ใน directed graph
// u คือโหนดปัจจุบัน
// คืนค่า true ถ้าพบ cycle, false ถ้าไม่พบ
bool dfs(int u) {
    // หากโหนด u อยู่ในสถานะสีเทา (gray) หมายความว่าอยู่ใน recursion stack แล้ว
    // พบ cycle แล้ว
    if (color[u] == 1)
        return true;
    // หากโหนด u อยู่ในสถานะสีดำ (black) หมายความว่าได้ประมวลผลครบแล้วในรอบก่อนหน้า
    if (color[u] == 2)
        return false;

    // เปลี่ยนสถานะของ u เป็นสีเทา เพื่อบอกว่าเริ่ม DFS จาก u แล้ว
    color[u] = 1;
    // เยี่ยมชมโหนดที่ติดกับ u
    for (int v : G[u]) {
        if (dfs(v))
            return true;
    }
    // เมื่อประมวลผลลูกครบแล้ว เปลี่ยนสถานะของ u เป็นสีดำ
    color[u] = 2;
    return false;
}

// ใน main function เราจะทำการเรียก DFS สำหรับทุกโหนดที่ยังไม่ได้ประมวลผล
for (int u = 1; u <= n; ++u) {
    if (color[u] == 0) {
        if (dfs(u)) {
            // พบ cycle
            cout << "พบ cycle" << "\n";
            break;
        }
    }
}
```

### 2.3.3 การนับจำนวน Component ในกราฟที่ไม่มีทิศทางด้วย DFS
การคำนวณจำนวนของ connected components หรือกลุ่มของโหนดที่เชื่อมต่อกันในกราฟที่ไม่มีทิศทาง (undirected graph) สามารถทำได้โดยการใช้ DFS เพื่อระบุโหนดที่ถูกเยี่ยมชมแล้ว จากนั้นนับจำนวนครั้งที่ต้องเริ่มต้น DFS ใหม่ในกราฟ ซึ่งแต่ละครั้งจะครอบคลุม component หนึ่ง

![Screenshot 2025-03-15 at 23.20.57](https://hackmd.io/_uploads/HkHSt7Q2ke.png)


**ตัวอย่างโปรแกรม**
```cpp=
bool visited[N];  // กำหนดให้ทุกตำแหน่งเป็น false ตั้งแต่เริ่มต้น

// ฟังก์ชัน DFS สำหรับมาร์คโหนดที่เชื่อมต่อกันใน component เดียวกัน
void dfs(int u) {
    if (visited[u])
        return;
    visited[u] = true;
    for (auto v : G[u])
        dfs(v);
}

// ใน main:
int component = 0;
for (int u = 1; u <= n; ++u) {
    if (!visited[u]) {
        ++component;
        dfs(u);  // DFS เพื่อมาร์คโหนดทั้งหมดใน component นี้
    }
}
```

> **หมายเหตุ:** 
> การนับจำนวน Component ในกราฟที่มีทิศทางสามารถแบ่งออกเป็นสองแบบหลัก:
> - Strongly Connected Components (SCC):
นั่นคือ ชุดของโหนดที่ในแต่ละคู่ของโหนดในชุดนั้น สามารถเข้าถึงกันและกันได้โดยใช้ทางเดินที่มีทิศทาง (directed path) สามารถทำได้ด้วยอัลกอริทึมอย่าง Kosaraju’s หรือ Tarjan’s Algorithm 
> - Weakly Connected Components:
หากละเว้นทิศทางของ edge แล้วมองกราฟเป็นแบบไม่มีทิศทาง (undirected graph) การนับ connected component ในกราฟที่ได้จะเป็นการนับ weakly connected components
วิธีนี้สามารถทำได้โดยการใช้ DFS หรือ BFS เหมือนกับกราฟไม่มีทิศทาง

### 2.3.4 การหาเส้นทางสั้นสุดในกราฟที่ไม่มีน้ำหนักด้วย BFS 
เนื่องจากกราฟที่ไม่มีน้ำหนัก ทุก edge มีค่าเท่ากัน (มักถือว่ามีค่าเป็น 1) การใช้ Breadth-first Search (BFS) จะเป็นวิธีที่เหมาะสมในการหาเส้นทางที่สั้นสุดระหว่างโหนดสองตัว เนื่องจาก BFS จะทำการเยี่ยมชมโหนดโดยเรียงลำดับตามระดับความลึกจากโหนดเริ่มต้น (level by level)

**ตัวอย่างโปรแกรม**
```cpp=
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

const int N = 1000; // กำหนดขนาดสูงสุดของโหนดในกราฟ
vector<int> G[N];   // กราฟที่เก็บในรูปแบบรายชื่อเพื่อนบ้าน
int level[N];       // อาร์เรย์เก็บระดับ (ระยะทาง) จากโหนดเริ่มต้น

int shortest_path(int start, int target) {
    // กำหนดค่าเริ่มต้นให้กับทุกตำแหน่งใน level เป็น -1 (ยังไม่เยี่ยมชม)
    fill(level, level + N, -1);
    
    queue<int> Q;
    level[start] = 0;
    Q.push(start);
    
    while (!Q.empty()) {
        int u = Q.front();
        Q.pop();
        
        // ถ้าเจอโหนดเป้าหมาย ให้คืนค่าระยะทางของโหนดนั้น
        if (u == target)
            return level[u];
        
        // เยี่ยมชมโหนดที่เชื่อมต่อกับ u
        for (int v : G[u]) {
            // ถ้าโหนด v ยังไม่ถูกเยี่ยมชม
            if (level[v] == -1) {
                level[v] = level[u] + 1;
                Q.push(v);
            }
        }
    }
    
    // ถ้าไม่พบเส้นทางให้คืนค่า -1
    return -1;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // ตัวอย่างการอ่านกราฟและเรียกใช้ฟังก์ชัน shortest_path
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++){
        int u, v;
        cin >> u >> v;
        // สมมุติว่ากราฟไม่มีทิศทาง
        G[u].push_back(v);
        G[v].push_back(u);
    }
    
    int start, target;
    cin >> start >> target;
    
    int distance = shortest_path(start, target);
    if (distance != -1)
        cout << "ระยะทางจาก " << start << " ถึง " << target << " = " << distance << "\n";
    else
        cout << "ไม่มีเส้นทางจาก " << start << " ถึง " << target << "\n";
    
    return 0;
}
```

### 2.3.5 เพื่อตรวจสอบ Bipartite Graph หรือ 2-coloring graph ด้วย DFS

**นิยามของ Bipartite Graph:**
กราฟจะเป็น Bipartite Graph ก็ต่อเมื่อสามารถแบ่งชุดของโหนดออกเป็นสองกลุ่ม (สองสี) โดยที่ไม่มีขอบเชื่อมระหว่างโหนดในกลุ่มเดียวกัน กล่าวคือ ทุกขอบจะเชื่อมระหว่างโหนดในกลุ่มที่ต่างกัน โดยกำหนด
- ค่า 0 หมายถึงยังไม่ได้ระบายสี
- ค่า 1 หมายถึงระบายด้วยสีแรก
- ค่า 2 หมายถึงระบายด้วยสีที่สอง

**กระบวนการ**
เมื่อเริ่มต้น DFS จากโหนดหนึ่ง เราจะระบายสีโหนดนั้นด้วยสีที่กำหนด (เช่นสี 1) แล้วทำการ DFS ไปยังโหนดที่ติดกัน โดยสลับสีให้กับโหนดที่เชื่อมต่อกัน
- หากเจอโหนดที่เคยระบายสีแล้วและสีที่ระบายไม่ตรงกับสีที่คาดหวัง (จากการสลับสี) ให้สรุปว่าไม่เป็น Bipartite Graph
- หากทุกการระบายสีสำเร็จโดยไม่มีความขัดแย้ง แสดงว่าโครงสร้างกราฟในส่วนที่ DFS เดียวกันนั้นเป็น Bipartite

![Screenshot 2025-03-15 at 23.19.35](https://hackmd.io/_uploads/Hk2idXX3yx.png)


**ตัวอย่างโปรแกรม**

```cpp=
const int N = 1001;
int color[N]; // เริ่มต้นทุกโหนดเป็น 0 (ยังไม่ได้ระบายสี)
// สมมุติว่า G เป็นกราฟที่เก็บในรูปแบบของ adjacency list

// ฟังก์ชัน DFS เพื่อทดลองระบายสีโหนด u ด้วยสี c
// คืนค่า true ถ้าสามารถระบายสีได้โดยไม่มีความขัดแย้ง (ยังอาจเป็น bipartite graph)
// คืนค่า false ถ้าพบความขัดแย้งในการระบายสี
bool dfs(int u, int c) {
    if (color[u] != 0) { // ถ้าโหนด u เคยถูกระบายสีแล้ว
        // สีที่ระบายไว้ต้องตรงกับสีที่คาดหวัง หากไม่ตรงกัน แสดงว่ามีความขัดแย้ง
        return (color[u] == c);
    }
    // ระบายสีโหนด u ด้วยสี c
    color[u] = c;
    // เยี่ยมชมโหนดที่เชื่อมต่อกับ u และสลับสีให้กับโหนดลูก
    for (auto v : G[u]) {
        // หากการระบายสีสำหรับโหนด v ไม่สำเร็จ ให้ return false ทันที
        if (!dfs(v, (c == 1 ? 2 : 1)))
            return false;
    }
    return true;
}

int main() {
    // สมมุติว่า n คือจำนวนโหนดและ G เป็น adjacency list ของกราฟ
    int n;
    // ... (อ่านข้อมูลกราฟเข้ามาและกำหนดค่าใน G)
    
    // ตั้งค่าเริ่มต้นให้กับ color ทุกโหนดเป็น 0 (ยังไม่ได้ระบายสี)
    for (int i = 1; i <= n; i++) {
        color[i] = 0;
    }
    
    bool isBipartite = true;
    // เรียก DFS สำหรับทุกโหนดที่ยังไม่ได้ระบายสี
    for (int u = 1; u <= n; u++) {
        if (color[u] == 0) { // ยังไม่ได้ระบายสี หมายความว่าสำหรับ component นี้ยังไม่ถูกตรวจสอบ
            if (!dfs(u, 1)) { // เริ่มระบายสีด้วยสี 1
                isBipartite = false;
                break;
            }
        }
    }
    
    if (isBipartite)
        cout << "กราฟเป็น Bipartite Graph" << "\n";
    else
        cout << "กราฟไม่เป็น Bipartite Graph" << "\n";
    
    return 0;
}
```

> **หมายเหตุ:** 
> - เนื่องจากกราฟอาจแยกออกเป็นส่วน ๆ (disconnected components) จึงต้องเรียก DFS สำหรับทุกโหนดที่ยังไม่ได้ระบายสี เพื่อให้แน่ใจว่าทุกส่วนของกราฟได้รับการตรวจสอบ
> - การตรวจสอบว่าโหนดในกราฟสามารถระบายสีด้วย k สีโดยที่โหนดที่เชื่อมต่อกันไม่มีสีเดียวกันนั้นเป็นเรื่องที่ซับซ้อนมาก แม้ในกรณีที่ k=3 ก็ยังไม่มีอัลกอริทึมที่มีประสิทธิภาพสำหรับแก้ปัญหานี้ เนื่องจากปัญหาดังกล่าวเป็น NP-hard.

## ตัวอย่างโจทย์
- https://programming.in.th/tasks/1031
- https://programming.in.th/tasks/1057
- https://programming.in.th/tasks/1061
- https://programming.in.th/tasks/1063
- https://programming.in.th/tasks/1085
- https://programming.in.th/tasks/1160
- https://programming.in.th/tasks/1161

# 3. Shortest Paths Algorithms
การหาเส้นทางสั้นสุด (Shortest Path) ในกราฟเป็นปัญหาพื้นฐานที่พบได้ในงานด้านการวิเคราะห์และออกแบบเครือข่าย โดยมีวัตถุประสงค์เพื่อค้นหาเส้นทางที่ใช้ค่าใช้จ่ายหรือระยะทางน้อยที่สุดระหว่างโหนดต้นทางและโหนดปลายทาง โดยมีอัลกอริทึมหลายแบบที่สามารถแก้ปัญหานี้ได้ ซึ่งแต่ละแบบมีข้อดีข้อเสียแตกต่างกันไป

**Dijkstra’s Algorithm:**
ใช้สำหรับกราฟที่มี edge weight เป็นค่าบวกเท่านั้น โดยอัลกอริทึมจะทำงานโดยเริ่มจากโหนดต้นทางและค่อย ๆ อัปเดตระยะทางไปยังโหนดอื่น ๆ โดยใช้ priority queue เพื่อเลือกโหนดที่มีระยะทางน้อยที่สุดในแต่ละขั้นตอน มีความซับซ้อนในแง่ของเวลา $O((m + n) \log(n))$

**Bellman-Ford Algorithm:**
ใช้สำหรับกราฟที่อาจมี edge ที่มี negative weight ได้ โดยอัลกอริทึมนี้จะทำการปรับค่าเส้นทางสั้นสุดโดยพิจารณา edge ทั้งหมดซ้ำ ๆ ไม่เกิน n−1 รอบ แต่มีความซับซ้อนในแง่ของเวลา $O(nm)$

<!-- **Shortest Path Faster Algorithm (SPFA):**
เป็นการปรับปรุงของ Bellman-Ford โดยผสมผสานกับแนวคิดของ BFS ซึ่งในกรณีเฉลี่ยมักทำงานได้รวดเร็วกว่า Dijkstra’s และ Bellman-Ford แต่ Worst case ยังคง $O(nm)$ -->

**Floyd-Warshall Algorithm:**
ใช้สำหรับคำนวณ All-Pair Shortest Path ได้อย่างง่ายดายเพียงไม่กี่บรรทัด แต่มีความซับซ้อนในแง่เวลาที่ $O(n^3)$ จึงเหมาะกับกราฟขนาดเล็กเท่านั้น

## 3.1 Dijkstra’s Algorithm
**กระบวนการทำงาน**
1. การกำหนดค่าเริ่มต้น:
กำหนดให้ระยะทาง (distance) จากโหนดเริ่มต้นไปยังทุกโหนดในกราฟเป็นค่าอนันต์ (infinity) ยกเว้นโหนดเริ่มต้นที่มีค่าเป็น 0 จากนั้นนำโหนดเริ่มต้นใส่ลงในคิว (priority queue)
2. การเลือกโหนด:
ในแต่ละขั้นตอน นำโหนดที่มีค่า distance ต่ำที่สุดออกจากคิว (ซึ่งทำให้เราได้โหนดที่อยู่ใกล้โหนดเริ่มต้นที่สุดในขณะนั้น)
3. การปรับปรุงค่า:
สำหรับโหนดที่เลือกออกมา ให้พิจารณาเพื่อนบ้านทั้งหมด (โดยดูจากข้อมูลใน Adjacency List) และปรับปรุงค่า distance ของเพื่อนบ้านเหล่านั้นโดยการบวกค่า edge weight เข้าไป ถ้าการปรับปรุงนี้ทำให้ค่า distance ของเพื่อนบ้านลดลง ให้ update ค่า distance และนำเพื่อนบ้านนั้นใส่ลงในคิว
4. การสิ้นสุดการทำงาน:
กระบวนการดำเนินต่อไปจนกว่าคิวจะว่าง หรือจนกว่าจะพบโหนดเป้าหมาย

**ข้อสังเกต**
- อัลกอริทึมนี้มีประสิทธิภาพในการหาเส้นทางสั้นสุดในกราฟที่มี edge weight เป็นค่าบวก โดยมีความซับซ้อน $O((m+n)\log(n))$
- ควรระวังว่า Dijkstra’s Algorithm ไม่สามารถใช้งานกับกราฟที่มี edge ที่มี negative weight ได้
![Screenshot 2025-03-15 at 23.57.25](https://hackmd.io/_uploads/rJlcWNQ31g.png)
จากกราฟข้างต้นเส้นทางสั้นสุดจากโหนด 1 ไปยังโหนด 4 ที่แท้จริงคือ 1 → 3 → 4 โดยมีความยาวรวมเท่ากับ 1 อย่างไรก็ตาม Dijkstra’s algorithm พบเส้นทาง 1 → 2 → 4 โดยเลือก edge ที่มีน้ำหนักน้อยที่สุด โดยอัลกอริทึมนี้ไม่ได้พิจารณาว่าในเส้นทางอีกเส้นหนึ่ง น้ำหนัก −5 ชดเชยน้ำหนักสูง 6 ที่ผ่านมา ทำให้ไม่พบเส้นทางที่สั้นสุดตามที่ควรเป็นในกรณีที่มี edge มีค่า negative weight
- กราฟถูกเก็บในรูปแบบ Adjacency List โดยใช้โครงสร้างข้อมูล
`vector<pair<int, int>> G[N]` ซึ่งในแต่ละสมาชิกของ G[u] จะเป็นคู่ (v, w) โดยที่:
    - v คือหมายเลขของโหนดปลายทาง
    - w คือความยาว (น้ำหนัก) ของ edge จาก u ไป v
- ใช้ Priority Queue (min-heap) ในการเลือกโหนดที่มี distance ต่ำที่สุด ซึ่งใน C++ สามารถใช้ `priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>` หรือจะกำหนดให้ค่า weight เป็นค่าลบเพื่อเปลี่ยนจาก max เป็น min priority queue ได้
- https://visualgo.net/en/sssp?slide=7

**ตัวอย่างโปรแกรม**
```cpp=
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const int INF = 1e9;   // กำหนดค่า infinity ที่เหมาะสม
const int N = 1001;    // สมมุติว่า N คือจำนวนสูงสุดของโหนด (ใช้ 1-based indexing)

vector<pair<int, int>> G[N];  // โครงสร้างเก็บกราฟในรูปแบบ Adjacency List
// ตัวอย่าง: ใน G[u], pair<int,int> เก็บ (v, w) คือโหนดปลายทางและน้ำหนักของ edge

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    // รับข้อมูลกราฟ
    for (int i = 0; i < m; i++){
        int u, v, w;
        cin >> u >> v >> w;
        G[u].push_back({v, w});
        // หากเป็นกราฟไม่มีทิศทาง ให้เพิ่มอีกด้าน:
        // G[v].push_back({u, w});
    }
    
    int start, target;
    cin >> start >> target;
    
    // เตรียมอาร์เรย์เก็บระยะทางจากโหนด start
    vector<int> dist(n+1, INF);
    vector<bool> visited(n+1, false);
    
    // ใช้ priority_queue ในรูปแบบ min-heap
    typedef pair<int, int> pii;
    priority_queue<pii, vector<pii>, greater<pii>> Q;
    
    dist[start] = 0;
    Q.push({0, start});
    
    while (!Q.empty()){
        int u = Q.top().second;
        int d = Q.top().first;
        Q.pop();
        
        // หากโหนด u ถูกเยี่ยมชมไปแล้ว ให้ข้ามไป
        if (visited[u])
            continue;
        visited[u] = true;
        
        // หากเจอโหนดเป้าหมาย ให้หยุดและแสดงผล
        if (u == target) {
            cout << "ระยะทางจาก " << start << " ถึง " << target << " = " << dist[target] << "\n";
            break;
        }
        
        // ปรับปรุงค่า distance ของเพื่อนบ้านที่เชื่อมต่อกับ u
        for (auto vw : G[u]){
            int v = vw.first;
            int w = vw.second;
            if (!visited[v] && d + w < dist[v]){
                dist[v] = d + w;
                Q.push({dist[v], v});
            }
        }
    }
    
    // หากไม่เจอโหนดเป้าหมาย
    if (!visited[target])
        cout << "ไม่พบเส้นทางจาก " << start << " ถึง " << target << "\n";
    
    return 0;
}
```

## 3.2 Bellman-Ford Algorithm
Bellman-Ford Algorithm มีไว้เพื่อหาเส้นทางสั้นสุดจากโหนดเริ่มต้นไปยังโหนดอื่น ๆ ในกราฟ โดยสามารถจัดการกับกราฟที่มี edge weight ที่เป็นค่าลบได้ 

**กระบวนการทำงาน**
1. กำหนดค่าเริ่มต้น:
นิยามให้ `dist[v]` เป็นระยะทางสั้นสุดจากโหนดเริ่มต้นไปยังโหนด `v` โดยตั้งค่า `dist[v] = INF` สำหรับทุก `v` ยกเว้นโหนดเริ่มต้นที่กำหนดให้ `dist[start] = 0`
2. การปรับปรุงค่า:
ทำการพิจารณา edge แต่ละ edge `(u, v, w)` ในกราฟ โดยเปรียบเทียบระยะทางที่ได้จากสองเส้นทางว่าเส้นทางใหม่ที่มาจากการเดินทางจาก `u` แล้วตามด้วย `edge (u, v)` ซึ่งมีค่า `dist[u] + w` ถ้า `dist[u] + w < dist[v]` ให้ปรับปรุงค่า `dist[v]` ด้วยค่าใหม่คือ `dist[u] + w`
3. ทำซ้ำ:
ทำขั้นตอนที่ 2 ซ้ำกันทั้งหมดไม่เกิน $n-1$ รอบ (โดยที่ $n$ คือจำนวนโหนด) เนื่องจากเส้นทางสั้นสุดจากโหนดเริ่มต้นไปยังโหนดใด ๆ จะผ่าน edge ไม่เกิน $n-1$ เส้น

หากหลังจากรอบที่ n-1 ยังพบการเปลี่ยนแปลงค่า dist[v] อยู่ แสดงว่ากราฟมี negative cycle (cycle ที่น้ำหนักรวมติดลบ) อยู่

**ข้อสังเกต**
- อัลกอริทึมนี้จะต้องพิจารณา edge ซ้ำทั้งหมดไม่เกิน n-1 รอบ เพราะ path จาก node เริ่มต้นไปยัง node ใด ๆ ที่เป็นเส้นทางสั้นสุด ย่อมผ่านเส้นไม่เกิน n-1 เส้น ดังนั้นอัลกอริทึมนี้จะทำงานในเวลา $O(mn)$
- กราฟถูกเก็บในรูปแบบ Edge list โดยใช้โครงสร้างข้อมูล
`vector<Edge> edges;` และ `struct Edge {
    int u, v, w;
};` ซึ่งในแต่ละสมาชิกของ edge จะเป็นคู่ลำดับ (u, v, w) โดยที่:
    - u คือหมายเลขของโหนดต้นทาง
    - v คือหมายเลขของโหนดปลายทาง
    - w คือความยาว (น้ำหนัก) ของ edge จาก u ไป v
- ในกรณีที่กราฟมี negative cycle (cycle ที่มี weight รวมติดลบ) algorithm อาจจะไม่จบการทำงาน ดังนั้นให้นับจำนวนรอบที่พิจารณา edge ด้วย หากทำงานรอบที่ `n-1` แล้วยังพบว่ามีการเปลี่ยนแปลงค่า `dist[v]` ก็สามารถสรุปได้ว่ากราฟมี negative cycle
- https://visualgo.net/en/sssp?slide=4

**ตัวอย่างโปรแกรม**
```cpp=
#include <iostream>
#include <vector>
#include <limits>
using namespace std;

const int INF = numeric_limits<int>::max();
const int N = 1001; // สมมุติว่าโหนดมีค่า 1-based index

// โครงสร้างสำหรับเก็บ edge
struct Edge {
    int u, v, w;
};

int main(){
    int n, m;
    cin >> n >> m;
    
    vector<Edge> edges;
    // รับข้อมูลกราฟในรูปแบบ edge list
    for (int i = 0; i < m; i++){
        int u, v, w;
        cin >> u >> v >> w;
        edges.push_back({u, v, w});
    }
    
    int start;
    cin >> start;
    
    // เตรียม vector สำหรับเก็บระยะทาง จากโหนด start ไปยังทุกโหนด
    vector<int> dist(n+1, INF);
    dist[start] = 0;
    
    int count = 0;
    bool found_changes = false;
    bool neg_cycle = false;
    
    // ทำการปรับปรุงค่า edge ไม่เกิน n-1 รอบ
    do {
        found_changes = false;
        for (auto edge : edges) {
            int u = edge.u, v = edge.v, w = edge.w;
            if (dist[u] != INF && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                found_changes = true;
            }
        }
        ++count;
        // ถ้าหลังจากรอบที่ n-1 ยังพบการเปลี่ยนแปลงค่า
        if (count > n - 1 && found_changes) {
            neg_cycle = true;
            break;
        }
    } while (found_changes);
    
    if (neg_cycle)
        cout << "กราฟมี negative cycle" << "\n";
    else {
        // แสดงผลระยะทางสั้นสุดจากโหนด start ไปยังโหนดอื่น ๆ
        for (int v = 1; v <= n; v++){
            cout << "dist[" << v << "] = ";
            if (dist[v] == INF)
                cout << "INF";
            else
                cout << dist[v];
            cout << "\n";
        }
    }
    
    return 0;
}
```

## 3.4 Floyd-Warshall Algorithm

นิยามให้ `dist[u][v]` เป็นระยะทางสั้นสุดที่ทราบ ณ ตอนนั้น จากโหนด u ไปยังโหนด v
- เริ่มแรก เราไม่ทราบระยะทางที่แท้จริงของคู่โหนดต่าง ๆ ทั้งหมด จึงกำหนดให้ทุกตำแหน่งใน dist เป็น ∞ ยกเว้นตำแหน่งที่ u=v ให้กำหนดเป็น 0 เพราะระยะทางจากโหนดไปยังตัวเองเท่ากับ 0
- เมื่อรับข้อมูล edge ในกราฟ (edge มีรูปแบบ (u,v,w)) ให้เซต `dist[u][v] = w` เนื่องจากตอนนี้เราทราบระยะทางโดยตรงของ edge นั้นแล้ว 

**กระบวนการทำงาน**
จากนั้นเราใช้การลูป 3 ชั้น โดยมีตัวแปร $k$ $i$ และ $j$ ดังนี้:

1. สำหรับทุกโหนด `k` (พิจารณาเป็นโหนดกลาง)
2. สำหรับทุกโหนด `i` (เป็นโหนดเริ่มต้น)
3. สำหรับทุกโหนด `j` (เป็นโหนดปลายทาง)
    - เปรียบเทียบเส้นทางที่มีอยู่เดิม `dist[i][j]` กับการเดินทางผ่านโหนด `k` โดยกำหนด `dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])`

**ข้อสังเกต**
- อัลกอริทึมนี้จะต้องพิจารณาโหนดทั้งหมดสามรอบจึงทำงานในเวลา $O(n^3)$ ซึ่งเหมาะสำหรับกราฟที่มีขนาดไม่ใหญ่มาก
- กราฟถูกเก็บในรูปแบบ Adjacency Matrix โดยใช้โครงสร้างข้อมูล `int dist[N_MAX][N_MAX];`
- สามารถใช้งานกับกราฟที่มี edge weight เป็นค่าลบได้
- การตรวจสอบ negative cycle สามารถทำได้โดยดูค่า 
`dist[u][u]` สำหรับทุกโหนด `u` หากมีค่า `dist[u][u]<0` แสดงว่ามี negative cycle อยู่ในกราฟ

**ตัวอย่างโปรแกรม**
```cpp=
#include <cstdio>
#include <algorithm>
using namespace std;

const int INF = 1e9;
const int N_MAX = 1001;
int dist[N_MAX][N_MAX];

int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    
    // เซตค่าเริ่มต้นให้กับ dist:
    // ถ้า i == j ให้เป็น 0, ไม่เช่นนั้นให้เป็น INF
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (i == j)
                dist[i][j] = 0;
            else
                dist[i][j] = INF;
        }
    }
    
    // รับข้อมูลกราฟ (edge list)
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        dist[u][v] = w;
        // หากเป็นกราฟไม่มีทิศทาง ให้ใช้:
        // dist[v][u] = w;
    }
    
    // Floyd-Warshall Algorithm
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
    
    // ตรวจสอบ negative cycle โดยดู dist[u][u] ของทุกโหนด
    bool negativeCycle = false;
    for (int u = 1; u <= n; ++u) {
        if (dist[u][u] < 0) {
            negativeCycle = true;
            break;
        }
    }
    
    if (negativeCycle)
        printf("กราฟมี negative cycle\n");
    else {
        // แสดงผลระยะทางสั้นสุดสำหรับทุกคู่โหนด
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (dist[i][j] == INF)
                    printf("INF ");
                else
                    printf("%d ", dist[i][j]);
            }
            printf("\n");
        }
    }
    
    return 0;
}
```

## สรุป

| อัลกอริทึม                   | ประเภทกราฟที่ใช้ได้                             | ความซับซ้อน (Time Complexity)            | ข้อดี                                                                 | ข้อเสีย                                                        |
|-------------------------------|-------------------------------------------------|------------------------------------------|----------------------------------------------------------------------|----------------------------------------------------------------|
| **Dijkstra’s Algorithm**      | กราฟที่มี edge weight เป็นบวกเท่านั้น           | O((V + E) log V) หรือ O(E log V)          | มีประสิทธิภาพสูงสำหรับกราฟ sparse<br>ใช้งานง่ายและมี implementation ที่ชัดเจน | ไม่รองรับ edge ที่มี negative weight                           |
| **Bellman-Ford Algorithm**    | กราฟที่มี edge weight เป็นบวกและลบได้           | O(V × E)                                 | รองรับ negative weight ได้<br>สามารถตรวจจับ negative cycle ได้        | ช้ากว่า Dijkstra ในกราฟที่ไม่มี negative edges               |
| **Floyd-Warshall Algorithm**  | หาค่า All-Pairs Shortest Path ในกราฟขนาดเล็ก   | O(V³)                                    | โค้ดสั้นและง่ายต่อการเข้าใจ<br>หาเส้นทางสั้นสุดระหว่างทุกคู่ของโหนดได้   | ใช้เวลามากเมื่อจำนวนโหนดมีมาก<br>ไม่เหมาะกับกราฟที่มี V สูงมาก |


## ตัวอย่างโจทย์
- https://programming.in.th/tasks/1111
- https://programming.in.th/tasks/1133
- https://programming.in.th/tasks/codecube_051
<!-- - https://programming.in.th/tasks/o59_oct_c1_delivery -->




# อ้างอิง

- https://cses.fi/book/book.pdf
- https://github.com/tchomphoochan/toi14-tutorial/tree/master
- https://visualgo.net/en
- https://programming.in.th/¬
