ทำความรู้จักกับ Ford-Fulkerson Algorithm ในภาษา C++

ปัญหาซึ่งนักวิทยาการคอมพิวเตอร์และวิศวกรรมนั้นต้องเผชิญอยู่บ่อยครั้งก็คือการหาสังข์การไหลของเครือข่าย (Network Flow) กล่าวคือปัญหาที่เราต้องพยายามหาจำนวนการไหลสูงสุดที่เป็นไปได้ตามเส้นทางที่ซับซ้อนภายในเครือข่าย อัลกอริธึมที่คนทั่วไปใช้ในการแก้ปัญหาประเภทนี้คือ Ford-Fulkerson Algorithm นั่นเองครับผม!

ความหมายของ Ford-Fulkerson Algorithm

Ford-Fulkerson Algorithm เป็นอัลกอริธึมที่ถูกออกแบบมาเพื่อคำนวณการไหลสูงสุด (Maximum Flow) ในเครือข่ายการไหล (Flow Network) ระหว่างแหล่งที่มา (source) และปลายทาง (sink) อัลกอริธึมนี้ทำงานโดยการค้นหาเส้นทางที่ยังสามารถเพิ่มการไหลได้ (augmenting path) และเพิ่มการไหลในเส้นทางนั้นจนกระทั่งไม่มีเส้นทางใดๆที่สามารถเพิ่มการไหลได้อีก

วิธีการทำงานของ Ford-Fulkerson Algorithm

อัลกอริธึมเริ่มโดยอาศัยการค้นหาแบบลึก (Depth-First Search, DFS) หรือการค้นหาแบบกว้าง (Breadth-First Search, BFS) เพื่อหาเส้นทางที่เพิ่มได้จากแหล่งที่มาไปยังปลายทาง จากนั้นจะประเมินความสามารถในการเพิ่มการไหลในเส้นทางนั้นโดยดูจากปริมาณน้ำหนักที่น้อยที่สุดที่เหลืออยู่ในเส้นทางหรือที่เรียกว่า bottleneck capacity

ด้านล่างนี้คือตัวอย่างโค้ดของ Ford-Fulkerson Algorithm ใช้ BFS ในภาษา C++:

#include 
#include 
#include 
#include 
using namespace std;

#define V 6 // จำนวนโหนดในเครือข่าย

/* ฟังก์ชันสำหรับค้นหาว่ามีเส้นทางไปยังปลายทางจากแหล่งที่มาใน residual graph
โดยใช้ BFS และจะ return true ถ้าหาเส้นทางได้ พร้อมทั้งเก็บ parent[] เพื่อเก็บเส้นทาง */
bool bfs(int rGraph[V][V], int s, int t, int parent[]) {
    // Create a visited array and mark all vertices as not visited
    bool visited[V];
    memset(visited, 0, sizeof(visited));

    // Create a queue, enqueue source vertex and mark source vertex as visited
    queue q;
    q.push(s);
    visited[s] = true;
    parent[s] = -1;

    // Standard BFS Loop
    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (int v = 0; v < V; v++) {
            if (visited[v] == false && rGraph[u][v] > 0) {
                // If we find a connection to the sink node, then there is no point in BFS anymore We just have to set its parent and can return true
                if (v == t) {
                    parent[v] = u;
                    return true;
                }
                q.push(v);
                parent[v] = u;
                visited[v] = true;
            }
        }
    }

    // We didn't reach sink in BFS starting from source, so return false
    return false;
}

// Returns the maximum flow from s to t in the given graph
int fordFulkerson(int graph[V][V], int s, int t) {
    int u, v;

    // Create a residual graph and fill the residual graph with given capacities in the original graph as residual capacities in residual graph
    int rGraph[V][V]; // Residual graph where rGraph[i][j] indicates residual capacity of edge from i to j (if there is an edge). If rGraph[i][j] is 0, then there is not.
    for (u = 0; u < V; u++)
        for (v = 0; v < V; v++)
             rGraph[u][v] = graph[u][v];

    int parent[V];  // This array is filled by BFS and to store path

    int max_flow = 0;  // There is no flow initially

    // Augment the flow while tere is path from source to sink
    while (bfs(rGraph, s, t, parent)) {
        // Find minimum residual capacity of the edhes along the path filled by BFS. Or we can say find the maximum flow through the path found.
        int path_flow = INT_MAX;
        for (v = t; v != s; v = parent[v]) {
            u = parent[v];
            path_flow = min(path_flow, rGraph[u][v]);
        }

        // update residual capacities of the edges and reverse edges along the path
        for (v = t; v != s; v = parent[v]) {
            u = parent[v];
            rGraph[u][v] -= path_flow;
            rGraph[v][u] += path_flow;
        }

        // Add path flow to overall flow
        max_flow += path_flow;
    }

    // Return the overall flow
    return max_flow;
}

int main() {
    // Let us create a graph shown in the above example
    int graph[V][V] = { {0, 16, 13, 0, 0, 0},
                        {0, 0, 10, 12, 0, 0},
                        {0, 4, 0, 0, 14, 0},
                        {0, 0, 9, 0, 0, 20},
                        {0, 0, 0, 7, 0, 4},
                        {0, 0, 0, 0, 0, 0}
                      };

    cout << "The maximum possible flow is " << fordFulkerson(graph, 0, 5);

    return 0;
}

Use Case ในโลกจริง

Ford-Fulkerson Algorithm มักใช้ในการขนส่งหรือกระจายน้ำมัน, การแบ่งสรรพื้นที่การเกษตร, ระบบเครือข่ายข้อมูล เช่น อินเทอร์เน็ต หรือแม้แต่ในการมองหาโซลูชันของปัญหาการจัดสรรทรัพยากรหลากหลายประเภท

วิเคราะห์ Complexity

Time Complexity ของ Ford-Fulkerson Algorithm นั้นจะขึ้นอยู่กับว่าเส้นทางที่เพิ่มได้นั้นมีจำนวนกี่ครั้ง และจะหาได้ภายในเวลา O(E |f*|) ที่ E คือจำนวนขอบในกราฟ และ |f*| คือ maximum flow นั่นเอง สำหรับ Space Complexity นั้นจะเป็น O(V^2) เนื่องจากต้องเก็บข้อมูลของ residual graph

ข้อดีข้อเสียของ Ford-Fulkerson Algorithm

ข้อดี:

- เรียบง่ายในการเข้าใจและการ implement

- มีประสิทธิภาพสูงในกรณีของกราฟที่มีขนาดเล็กและขนาดกลาง

ข้อเสีย:

- อัลกอริธึมอาจไม่รันจบในกรณีของกราฟที่มีความจุเป็นลอยฟ้า (floating point)

- ประสิทธิภาพอาจไม่ดีนักสำหรับกราฟขนาดใหญ่หรือกราฟที่มีข้อมูลที่ซับซ้อน

ในท้ายที่สุด การทำความรู้จักกับ Ford-Fulkerson และการฝึกฝนเขียนโค้ดไม่เพียงช่วยเพิ่มทักษะการโปรแกรมมิ่งของคุณเท่านั้น ยังทำให้คุณสามารถแก้ไขปัญหาเชิงพลวัตได้อย่างเฉียบคม และหากคุณต้องการเรียนรู้เพิ่มเติมเกี่ยวกับ Ford-Fulkerson หรืออัลกอริธึมอื่นๆ อย่าลืมมาที่ EPT ที่จะช่วยให้คุณนั้นก้าวขึ้นไปอีกขั้นในการเป็นนักพัฒนาซอฟต์แวร์ที่มีความรู้ความสามารถครับ!

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