{"id":460,"date":"2024-02-09T14:25:50","date_gmt":"2024-02-09T14:25:50","guid":{"rendered":"https:\/\/cyberenlightener.com\/?page_id=460"},"modified":"2025-03-13T07:29:21","modified_gmt":"2025-03-13T07:29:21","slug":"network-flow","status":"publish","type":"page","link":"https:\/\/cyberenlightener.com\/?page_id=460","title":{"rendered":"Network Flow"},"content":{"rendered":"\n<ul class=\"wp-block-list\">\n<li><strong><a href=\"#Netw\" data-type=\"internal\" data-id=\"#Netw\">Flow Network &amp; its components<\/a><\/strong><\/li>\n\n\n\n<li id=\"Netw\"><strong>Maximum Flow <\/strong><\/li>\n\n\n\n<li><strong><a href=\"https:\/\/www.youtube.com\/watch?v=VvfC9s_nqPg&amp;t=1585s\">Dijkstra&#8217;s algorithm<\/a><\/strong><\/li>\n\n\n\n<li><strong><a href=\"#Dijkstra\">Dijkstra&#8217;s Vs Bellman-Ford&nbsp;algorithm<\/a><\/strong><\/li>\n\n\n\n<li><strong><a href=\"#Bellman\" data-type=\"internal\" data-id=\"#Bellman\">Bellman-Ford&nbsp;algorithm<\/a><\/strong><\/li>\n\n\n\n<li><a href=\"#Howitworks\" data-type=\"internal\" data-id=\"#Howitworks\"><strong>How Bellman-Ford works?<\/strong><\/a><\/li>\n\n\n\n<li><strong><a href=\"#Fordful\" data-type=\"internal\" data-id=\"#Fordful\">Ford Fulkerson Algorithm<\/a><\/strong><\/li>\n\n\n\n<li><a href=\"#edmond\" data-type=\"internal\" data-id=\"#edmond\"><strong>Edmond Karp Algorithm<\/strong><\/a><\/li>\n\n\n\n<li><strong><a href=\"#Pushlbl\" data-type=\"internal\" data-id=\"#Pushlbl\">Push Relabel Algorithm<\/a><\/strong><\/li>\n\n\n\n<li><strong><a href=\"#Floyd\" data-type=\"internal\" data-id=\"#Floyd\">Floyd Warshall Algorithm<\/a><\/strong><\/li>\n\n\n\n<li><strong><a href=\"https:\/\/www.cs.emory.edu\/~cheung\/Courses\/253\/Syllabus\/NetFlow\/max-flow-min-cut.html\" data-type=\"link\" data-id=\"https:\/\/www.cs.emory.edu\/~cheung\/Courses\/253\/Syllabus\/NetFlow\/max-flow-min-cut.html\">MaxFlow Min Cut<\/a><\/strong><\/li>\n\n\n\n<li><strong><a href=\"#Bip\" data-type=\"internal\" data-id=\"#Bip\">Bipartite Matching<\/a><\/strong><\/li>\n\n\n\n<li><strong><a href=\"#Cycle\" data-type=\"internal\" data-id=\"#Cycle\">Cycle Cancellation Algorithm<\/a><\/strong><\/li>\n<\/ul>\n\n\n\n<p><br>A<strong> flow network, <\/strong>also known as a network flow, is a directed graph where each edge has a capacity and each node (except for the source and sink nodes) has a flow value associated with it. Flow networks are commonly used to model transportation or distribution systems, such as water distribution networks, traffic flow, or computer networks.<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"381\" height=\"172\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/FN.png\" alt=\"\" class=\"wp-image-461\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/FN.png 381w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/FN-300x135.png 300w\" sizes=\"auto, (max-width: 381px) 100vw, 381px\" \/><\/figure>\n\n\n\n<p>Fig.An example of flow network with Source and Sink node with capacities of each link<\/p>\n\n\n\n<p>In a flow network:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Nodes<\/strong>: These represent points in the network where the flow can split or merge. Typically, there are two special nodes: a source node, from which flow originates, and a sink node, where flow terminates.<\/li>\n\n\n\n<li><strong>Edges<\/strong>: These represent the connections between nodes and have associated capacities, which indicate the maximum amount of flow that can traverse the edge.<\/li>\n\n\n\n<li><strong>Flow<\/strong>: This is the amount of material, information, or whatever is being transported, that is sent from the source to the sink through the network. The flow must satisfy certain constraints:\n<ul class=\"wp-block-list\">\n<li>The flow through any edge cannot exceed its capacity.<\/li>\n\n\n\n<li>The total flow out of any node (except the source and sink) must equal the total flow into that node.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\n<p>Flow networks are used in optimization problems, such as the maximum flow problem, where the goal is to determine the maximum amount of flow that can be sent from the source to the sink without violating the capacity constraints. They also find applications in various fields including transportation planning, telecommunications, and logistics.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\" id=\"Dijkstra\"><strong>Dijkstra&#8217;s Vs Bellman-Ford&nbsp;algorithm<\/strong><\/h4>\n\n\n\n<div data-wp-interactive=\"core\/file\" class=\"wp-block-file\"><object data-wp-bind--hidden=\"!state.hasPdfPreview\" hidden class=\"wp-block-file__embed\" data=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/03\/Dijkstra-vs-Bellman-Ford-1-1.pdf\" type=\"application\/pdf\" style=\"width:100%;height:600px\" aria-label=\"Embed of Dijkstra vs Bellman-Ford (1) (1).\"><\/object><a id=\"wp-block-file--media-6d39349b-14d8-4fb6-a5bc-a12a903eaffe\" href=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/03\/Dijkstra-vs-Bellman-Ford-1-1.pdf\">Dijkstra vs Bellman-Ford (1) (1)<\/a><a href=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/03\/Dijkstra-vs-Bellman-Ford-1-1.pdf\" class=\"wp-block-file__button wp-element-button\" download aria-describedby=\"wp-block-file--media-6d39349b-14d8-4fb6-a5bc-a12a903eaffe\">Download<\/a><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"Bellman\">Bellman-Ford&nbsp;algorithm<\/h3>\n\n\n\n<figure class=\"wp-block-gallery has-nested-images columns-default is-cropped wp-block-gallery-1 is-layout-flex wp-block-gallery-is-layout-flex\">\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"745\" height=\"1024\" data-id=\"1742\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/03\/001-1-745x1024.jpg\" alt=\"\" class=\"wp-image-1742\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/03\/001-1-745x1024.jpg 745w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/03\/001-1-218x300.jpg 218w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/03\/001-1-768x1056.jpg 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/03\/001-1-1117x1536.jpg 1117w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/03\/001-1-1489x2048.jpg 1489w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/03\/001-1-scaled.jpg 1861w\" sizes=\"auto, (max-width: 745px) 100vw, 745px\" \/><\/figure>\n<\/figure>\n\n\n\n<figure class=\"wp-block-image size-large is-resized\"><img loading=\"lazy\" decoding=\"async\" width=\"745\" height=\"1024\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/03\/002-2-745x1024.jpg\" alt=\"\" class=\"wp-image-1743\" style=\"width:997px;height:auto\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/03\/002-2-745x1024.jpg 745w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/03\/002-2-218x300.jpg 218w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/03\/002-2-768x1056.jpg 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/03\/002-2-1117x1536.jpg 1117w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/03\/002-2-1489x2048.jpg 1489w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/03\/002-2-scaled.jpg 1861w\" sizes=\"auto, (max-width: 745px) 100vw, 745px\" \/><\/figure>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"Howitworks\"><strong>How Does Bellman-Ford Work?<\/strong><\/h3>\n\n\n\n<figure class=\"wp-block-embed is-type-video is-provider-youtube wp-block-embed-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"Bellman-Ford Algorithm Explained | Short &amp; Simple\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/nlslmEqjDXk?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\">Ford Fulkerson Algorithm<\/h2>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"733\" height=\"335\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/FORD_FULKERSON.png\" alt=\"\" class=\"wp-image-462\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/FORD_FULKERSON.png 733w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/FORD_FULKERSON-300x137.png 300w\" sizes=\"auto, (max-width: 733px) 100vw, 733px\" \/><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"endmond\"><strong>Edmond Karp Algorithm<\/strong><\/h2>\n\n\n\n<p>The algorithm is identical to the&nbsp;<a href=\"https:\/\/en.wikipedia.org\/wiki\/Ford%E2%80%93Fulkerson_algorithm\">Ford\u2013Fulkerson algorithm<\/a>, except that the search order when finding the&nbsp;<a href=\"https:\/\/en.wikipedia.org\/wiki\/Flow_network#Augmenting_paths\">augmenting path<\/a>&nbsp;is defined. The path found must be a shortest path that has available capacity. This can be found by a&nbsp;<a href=\"https:\/\/en.wikipedia.org\/wiki\/Breadth-first_search\">breadth-first search<\/a>, where we apply a weight of 1 to each edge. The running time of &nbsp;<img decoding=\"async\" src=\"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/ae5bc5dfaecce53a04efd47719ac640aa983e706\" alt=\"{\\displaystyle O(|V||E|^{2})}\">&nbsp;is found by showing that each augmenting path can be found in&nbsp;<img decoding=\"async\" src=\"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/976fe7f1e011d0dcdb3d6163754c877aaad5187f\" alt=\"{\\displaystyle O(|E|)}\">&nbsp;time, that every time at least one of the&nbsp;<img decoding=\"async\" src=\"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/4232c9de2ee3eec0a9c0a19b15ab92daa6223f9b\" alt=\"{\\displaystyle E}\">&nbsp;edges becomes saturated (an edge which has the maximum possible flow), that the distance from the saturated edge to the source along the augmenting path must be longer than last time it was saturated, and that the length is at most&nbsp;<img decoding=\"async\" src=\"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/9ddcffc28643ac01a14dd0fb32c3157859e365a7\" alt=\"{\\displaystyle |V|}\">. Another property of this algorithm is that the length of the shortest augmenting path increases monotonically. There is an accessible proof in&nbsp;<em><a href=\"https:\/\/en.wikipedia.org\/wiki\/Introduction_to_Algorithms\">Introduction to Algorithms<\/a><\/em>.(THC book).<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"Pushlbl\"><strong>Push Relabel Algorithm<\/strong><\/h2>\n\n\n\n<p>In&nbsp;<a href=\"https:\/\/en.wikipedia.org\/wiki\/Mathematical_optimization\">mathematical optimization<\/a>, the&nbsp;<strong>push\u2013relabel algorithm<\/strong>&nbsp;(alternatively,&nbsp;<strong>preflow\u2013push algorithm<\/strong>) is an algorithm for computing&nbsp;<a href=\"https:\/\/en.wikipedia.org\/wiki\/Maximum_flow\">maximum flows<\/a>&nbsp;in a&nbsp;<a href=\"https:\/\/en.wikipedia.org\/wiki\/Flow_network\">flow network<\/a>. The name &#8220;push\u2013relabel&#8221; comes from the two basic operations used in the algorithm. Throughout its execution, the algorithm maintains a &#8220;preflow&#8221; and gradually converts it into a maximum flow by moving flow locally between neighboring nodes using&nbsp;<em>push<\/em>&nbsp;operations under the guidance of an admissible network maintained by&nbsp;<em>relabel<\/em>&nbsp;operations. In comparison, the&nbsp;<a href=\"https:\/\/en.wikipedia.org\/wiki\/Ford%E2%80%93Fulkerson_algorithm\">Ford\u2013Fulkerson algorithm<\/a>&nbsp;performs global augmentations that send flow following paths from the source all the way to the sink.<\/p>\n\n\n\n<figure class=\"wp-block-embed is-type-video is-provider-youtube wp-block-embed-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\ud835\udc05\ud835\udc25\ud835\udc28\ud835\udc30 \ud835\udc0d\ud835\udc1e\ud835\udc2d\ud835\udc30\ud835\udc28\ud835\udc2b\ud835\udc24\ud835\udc2c|| \ud835\udc05\ud835\udc0e\ud835\udc11\ud835\udc03 \ud835\udc05\ud835\udc14\ud835\udc0b\ud835\udc0a\ud835\udc04\ud835\udc11\ud835\udc12\ud835\udc0e\ud835\udc0d || \ud835\udc0f\ud835\udc14\ud835\udc12\ud835\udc07 \ud835\udc11\ud835\udc04-\ud835\udc0b\ud835\udc00\ud835\udc01\ud835\udc04\ud835\udc0b|| \ud835\udc04\ud835\udc0d\ud835\udc03\ud835\udc0c\ud835\udc0e\ud835\udc0d\ud835\udc03 \ud835\udc0a\ud835\udc00\ud835\udc11\ud835\udc0f\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/4BlE8nj9HGA?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><figcaption class=\"wp-element-caption\">Network flow\/flow networks.<\/figcaption><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Ford Fulkerson<\/strong><\/h2>\n\n\n\n<p>The <strong>Ford-Fulkerson algorithm<\/strong> is used to compute the maximum flow in a flow network. It works by repeatedly finding augmenting paths in the residual graph and increasing the flow along those paths. This method can be implemented with <strong>DFS (Depth-First Search)<\/strong> or <strong>BFS (Breadth-First Search)<\/strong> for finding augmenting paths. Here, we\u2019ll use <strong>DFS<\/strong> for simplicity in the explanation.<\/p>\n\n\n\n<pre id=\"Fordful\" class=\"wp-block-code\"><code><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-ast-global-color-1-color\">\/\/<strong>C code for<\/strong> <strong>Ford-Fulkerson algorithm<\/strong><\/mark>\n#include &lt;stdio.h&gt;\n#include &lt;limits.h&gt;  \/\/ For INT_MAX (used to represent infinity)\n#include &lt;string.h&gt;  \/\/ For memset function\n\n\/\/ Maximum number of vertices in the graph\n#define V 6  \/\/ You can change this to modify the number of vertices\n\n\/\/ Function to perform Depth-First Search (DFS) in the residual graph\n\/\/ It will find an augmenting path from source to sink and update the parent array\nint dfs(int residualGraph&#91;V]&#91;V], int source, int sink, int parent&#91;], int visited&#91;]) {\n    \/\/ Mark the source node as visited\n    visited&#91;source] = 1;\n\n    \/\/ If we reach the sink, return true (path found)\n    if (source == sink) {\n        return 1;\n    }\n\n    \/\/ Try all adjacent vertices of the current vertex\n    for (int v = 0; v &lt; V; v++) {\n        \/\/ If v is not visited and there is a positive capacity (residual capacity)\n        if (!visited&#91;v] &amp;&amp; residualGraph&#91;source]&#91;v] &gt; 0) {\n            parent&#91;v] = source;  \/\/ Set the parent of v as the current vertex\n            \/\/ Recur to explore further\n            if (dfs(residualGraph, v, sink, parent, visited)) {\n                return 1;  \/\/ If augmenting path is found, return true\n            }\n        }\n    }\n\n    \/\/ If no augmenting path is found, return false\n    return 0;\n}\n\n\/\/ Function to implement the Ford-Fulkerson algorithm\nint fordFulkerson(int graph&#91;V]&#91;V], int source, int sink) {\n    \/\/ Create a residual graph and initialize it as the input graph\n    int residualGraph&#91;V]&#91;V];\n    for (int i = 0; i &lt; V; i++) {\n        for (int j = 0; j &lt; V; j++) {\n            residualGraph&#91;i]&#91;j] = graph&#91;i]&#91;j];\n        }\n    }\n\n    int parent&#91;V];  \/\/ Array to store the path\n    int maxFlow = 0;  \/\/ Variable to store the maximum flow\n\n    \/\/ Augment the flow while there is an augmenting path\n    while (1) {\n        \/\/ Visited array to keep track of visited nodes during DFS\n        int visited&#91;V] = {0};\n\n        \/\/ Perform DFS to find an augmenting path\n        if (!dfs(residualGraph, source, sink, parent, visited)) {\n            break;  \/\/ No more augmenting path, break the loop\n        }\n\n        \/\/ Find the maximum flow in the found path\n        int pathFlow = INT_MAX;\n        for (int v = sink; v != source; v = parent&#91;v]) {\n            int u = parent&#91;v];\n            pathFlow = (pathFlow &lt; residualGraph&#91;u]&#91;v]) ? pathFlow : residualGraph&#91;u]&#91;v];\n        }\n\n        \/\/ Update the residual graph by subtracting the flow from forward edges\n        \/\/ and adding the flow to the reverse edges\n        for (int v = sink; v != source; v = parent&#91;v]) {\n            int u = parent&#91;v];\n            residualGraph&#91;u]&#91;v] -= pathFlow;\n            residualGraph&#91;v]&#91;u] += pathFlow;\n        }\n\n        \/\/ Add the flow of the current path to the overall flow\n        maxFlow += pathFlow;\n    }\n\n    return maxFlow;  \/\/ Return the maximum flow found\n}\n\nint main() {\n    \/\/ Example graph (6 vertices)\n    \/\/ Graph represented as an adjacency matrix (capacity matrix)\n    int graph&#91;V]&#91;V] = {\n        {0, 16, 13, 0, 0, 0},  \/\/ Vertex 0 connects to 1 with capacity 16, 2 with capacity 13\n        {0, 0, 10, 12, 0, 0},  \/\/ Vertex 1 connects to 2 with capacity 10, 3 with capacity 12\n        {0, 4, 0, 0, 14, 0},   \/\/ Vertex 2 connects to 1 with capacity 4, 4 with capacity 14\n        {0, 0, 9, 0, 0, 20},   \/\/ Vertex 3 connects to 2 with capacity 9, 5 with capacity 20\n        {0, 0, 0, 7, 0, 4},    \/\/ Vertex 4 connects to 3 with capacity 7, 5 with capacity 4\n        {0, 0, 0, 0, 0, 0}     \/\/ Vertex 5 is the sink (no outgoing edges)\n    };\n\n    int source = 0;  \/\/ Source node (vertex 0)\n    int sink = 5;    \/\/ Sink node (vertex 5)\n\n    \/\/ Calling the Ford-Fulkerson algorithm to find the maximum flow\n    int maxFlow = fordFulkerson(graph, source, sink);\n\n    \/\/ Output the maximum flow\n    printf(\"The maximum flow from source %d to sink %d is %d\\n\", source, sink, maxFlow);\n    \n    return 0;\n}\nOutput :\nThe maximum flow from source 0 to sink 5 is 23<\/code><\/pre>\n\n\n\n<p><strong>Here\u2019s below the complete C++ code for implementing the Ford-Fulkerson algorithm using classes and the Standard Template Library (STL). Each line is explained with comments.<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code><strong><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-ast-global-color-1-color\">\/\/ C++ code for implementing the Ford-Fulkerson<\/mark><\/strong>\n#include &lt;iostream&gt;\n#include &lt;vector&gt;\n#include &lt;queue&gt;\n#include &lt;climits&gt; \/\/ For INT_MAX\n\nusing namespace std;\n\n\/\/ Class to represent a graph\nclass Graph {\nprivate:\n    int numVertices; \/\/ Number of vertices in the graph\n    vector&lt;vector&lt;int&gt;&gt; capacity; \/\/ Capacity matrix\n\npublic:\n    \/\/ Constructor to initialize the graph\n    Graph(int vertices) : numVertices(vertices) {\n        capacity.resize(vertices, vector&lt;int&gt;(vertices, 0));\n    }\n\n    \/\/ Function to add an edge with a given capacity\n    void addEdge(int u, int v, int cap) {\n        capacity&#91;u]&#91;v] = cap; \/\/ Set the capacity of the edge from u to v\n    }\n\n    \/\/ Function to perform BFS and find an augmenting path\n    bool bfs(vector&lt;vector&lt;int&gt;&gt; &amp;residualCapacity, int source, int sink, vector&lt;int&gt; &amp;parent) {\n        vector&lt;bool&gt; visited(numVertices, false); \/\/ Keep track of visited vertices\n        queue&lt;int&gt; q; \/\/ Queue for BFS\n        q.push(source);\n        visited&#91;source] = true;\n        parent&#91;source] = -1; \/\/ Source has no parent\n\n        while (!q.empty()) {\n            int u = q.front();\n            q.pop();\n\n            \/\/ Explore all neighbors of u\n            for (int v = 0; v &lt; numVertices; v++) {\n                \/\/ If v is not visited and there is residual capacity\n                if (!visited&#91;v] &amp;&amp; residualCapacity&#91;u]&#91;v] &gt; 0) {\n                    q.push(v);\n                    visited&#91;v] = true;\n                    parent&#91;v] = u; \/\/ Set parent of v to u\n\n                    \/\/ If we reach the sink, return true\n                    if (v == sink)\n                        return true;\n                }\n            }\n        }\n\n        \/\/ If no path to sink is found\n        return false;\n    }\n\n    \/\/ Function to implement the Ford-Fulkerson algorithm\n    int fordFulkerson(int source, int sink) {\n        vector&lt;vector&lt;int&gt;&gt; residualCapacity = capacity; \/\/ Create a residual capacity matrix\n        vector&lt;int&gt; parent(numVertices); \/\/ To store the augmenting path\n        int maxFlow = 0; \/\/ Initialize the max flow to 0\n\n        \/\/ While there exists an augmenting path\n        while (bfs(residualCapacity, source, sink, parent)) {\n            \/\/ Find the minimum residual capacity in the augmenting path\n            int pathFlow = INT_MAX;\n            for (int v = sink; v != source; v = parent&#91;v]) {\n                int u = parent&#91;v];\n                pathFlow = min(pathFlow, residualCapacity&#91;u]&#91;v]);\n            }\n\n            \/\/ Update the residual capacities of the edges and reverse edges\n            for (int v = sink; v != source; v = parent&#91;v]) {\n                int u = parent&#91;v];\n                residualCapacity&#91;u]&#91;v] -= pathFlow;\n                residualCapacity&#91;v]&#91;u] += pathFlow;\n            }\n\n            \/\/ Add the path flow to the overall flow\n            maxFlow += pathFlow;\n        }\n\n        return maxFlow;\n    }\n};\n\nint main() {\n    \/\/ Create a graph with 6 vertices (0 to 5)\n    Graph g(6);\n\n    \/\/ Add edges along with their capacities\n    g.addEdge(0, 1, 16);\n    g.addEdge(0, 2, 13);\n    g.addEdge(1, 2, 10);\n    g.addEdge(1, 3, 12);\n    g.addEdge(2, 1, 4);\n    g.addEdge(2, 4, 14);\n    g.addEdge(3, 2, 9);\n    g.addEdge(3, 5, 20);\n    g.addEdge(4, 3, 7);\n    g.addEdge(4, 5, 4);\n\n    \/\/ Display the maximum flow from source (0) to sink (5)\n    cout &lt;&lt; \"The maximum possible flow is: \" &lt;&lt; g.fordFulkerson(0, 5) &lt;&lt; endl;\n\n    return 0;\n}\nOutput :\nThe maximum possible flow is: 23<\/code><\/pre>\n\n\n\n<p><strong>Here below is a C code implementation of the Edmond Karp, with detailed explanations for each line within the code:<\/strong><\/p>\n\n\n\n<pre id=\"edmond\" class=\"wp-block-code\"><code><strong><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-ast-global-color-1-color\">\/\/C Code for Edmonds-Karp Algorithm:<\/mark><\/strong>\n#include &lt;stdio.h&gt;\n#include &lt;limits.h&gt;  \/\/ To use INT_MAX for infinite capacity\n#include &lt;queue&gt;  \/\/ For BFS (using STL queue for simple implementation)\n\n\/\/ Number of vertices in the graph\n#define V 6  \/\/ Example graph with 6 vertices (adjust as necessary)\n\n\/\/ Function to perform BFS and find the path with available capacity\nint bfs(int residualGraph&#91;V]&#91;V], int source, int sink, int parent&#91;]) {\n    \/\/ Initialize all nodes as not visited\n    bool visited&#91;V] = {0};\n\n    \/\/ Create a queue for BFS\n    std::queue&lt;int&gt; q;\n\n    \/\/ Start BFS from the source\n    q.push(source);\n    visited&#91;source] = true;\n    parent&#91;source] = -1;  \/\/ Source has no parent\n\n    \/\/ BFS to find an augmenting path from source to sink\n    while (!q.empty()) {\n        int u = q.front();\n        q.pop();\n\n        \/\/ Traverse all adjacent vertices of u\n        for (int v = 0; v &lt; V; v++) {\n            if (visited&#91;v] == false &amp;&amp; residualGraph&#91;u]&#91;v] &gt; 0) {  \/\/ If v is not visited and has capacity left\n                q.push(v);\n                parent&#91;v] = u;  \/\/ Set parent of v as u\n                visited&#91;v] = true;\n\n                \/\/ If we reached the sink, no need to go further\n                if (v == sink) {\n                    return 1;  \/\/ Return true if we found a path\n                }\n            }\n        }\n    }\n    return 0;  \/\/ Return false if no augmenting path exists\n}\n\n\/\/ Function to implement the Edmonds-Karp algorithm\nint edmondsKarp(int graph&#91;V]&#91;V], int source, int sink) {\n    \/\/ Create a residual graph and initialize it as the input graph\n    int residualGraph&#91;V]&#91;V];\n    for (int i = 0; i &lt; V; i++) {\n        for (int j = 0; j &lt; V; j++) {\n            residualGraph&#91;i]&#91;j] = graph&#91;i]&#91;j];\n        }\n    }\n\n    int parent&#91;V];  \/\/ Array to store the path\n    int maxFlow = 0;  \/\/ Variable to store the maximum flow\n\n    \/\/ Augment the flow while there is a path from source to sink\n    while (bfs(residualGraph, source, sink, parent)) {\n        \/\/ Find the maximum flow in the found path\n        int pathFlow = INT_MAX;\n        for (int v = sink; v != source; v = parent&#91;v]) {\n            int u = parent&#91;v];\n            pathFlow = (pathFlow &lt; residualGraph&#91;u]&#91;v]) ? pathFlow : residualGraph&#91;u]&#91;v];\n        }\n\n        \/\/ Update the residual graph by subtracting the flow from forward edges\n        \/\/ and adding the flow to the reverse edges\n        for (int v = sink; v != source; v = parent&#91;v]) {\n            int u = parent&#91;v];\n            residualGraph&#91;u]&#91;v] -= pathFlow;\n            residualGraph&#91;v]&#91;u] += pathFlow;\n        }\n\n        \/\/ Add the path flow to the overall flow\n        maxFlow += pathFlow;\n    }\n\n    return maxFlow;  \/\/ Return the maximum flow found\n}\n\n\/\/ Main function to test the Edmonds-Karp algorithm\nint main() {\n    \/\/ Example graph with 6 vertices (0 to 5)\n    \/\/ Graph represented as an adjacency matrix\n    int graph&#91;V]&#91;V] = {\n        {0, 16, 13, 0, 0, 0},  \/\/ Vertex 0 is connected to 1 (capacity 16), 2 (capacity 13)\n        {0, 0, 10, 12, 0, 0},  \/\/ Vertex 1 is connected to 2 (capacity 10), 3 (capacity 12)\n        {0, 4, 0, 0, 14, 0},   \/\/ Vertex 2 is connected to 1 (capacity 4), 4 (capacity 14)\n        {0, 0, 9, 0, 0, 20},   \/\/ Vertex 3 is connected to 2 (capacity 9), 5 (capacity 20)\n        {0, 0, 0, 7, 0, 4},    \/\/ Vertex 4 is connected to 3 (capacity 7), 5 (capacity 4)\n        {0, 0, 0, 0, 0, 0}     \/\/ Vertex 5 is connected to no one (sink)\n    };\n\n    int source = 0;  \/\/ Source node (vertex 0)\n    int sink = 5;    \/\/ Sink node (vertex 5)\n\n    \/\/ Calling the Edmonds-Karp algorithm to find the maximum flow\n    int maxFlow = edmondsKarp(graph, source, sink);\n\n    \/\/ Output the maximum flow\n    printf(\"The maximum flow from source %d to sink %d is %d\\n\", source, sink, maxFlow);\n    return 0;\n}\n\nOutput :\n<strong>The maximum flow from source 0 to sink 5 is 23<\/strong><\/code><\/pre>\n\n\n\n<pre class=\"wp-block-code\"><code><strong><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-ast-global-color-1-color\">\/\/C++ Code with Class and Vector STL:<\/mark><\/strong>\n#include &lt;iostream&gt;\n#include &lt;vector&gt;\n#include &lt;queue&gt;\n#include &lt;limits.h&gt;  \/\/ For INT_MAX\n\nusing namespace std;\n\nclass EdmondsKarp {\nprivate:\n    int V;  \/\/ Number of vertices\n    vector&lt;vector&lt;int&gt;&gt; graph;  \/\/ Adjacency matrix (graph representation)\n    \n    \/\/ Helper function to perform BFS and find the augmenting path\n    bool bfs(vector&lt;vector&lt;int&gt;&gt;&amp; residualGraph, int source, int sink, vector&lt;int&gt;&amp; parent) {\n        vector&lt;bool&gt; visited(V, false);\n        queue&lt;int&gt; q;\n        q.push(source);\n        visited&#91;source] = true;\n        parent&#91;source] = -1;\n\n        \/\/ Perform BFS to find an augmenting path from source to sink\n        while (!q.empty()) {\n            int u = q.front();\n            q.pop();\n\n            for (int v = 0; v &lt; V; v++) {\n                \/\/ If the vertex is not visited and there is remaining capacity\n                if (!visited&#91;v] &amp;&amp; residualGraph&#91;u]&#91;v] &gt; 0) {\n                    q.push(v);\n                    parent&#91;v] = u;\n                    visited&#91;v] = true;\n\n                    \/\/ If we reached the sink, stop\n                    if (v == sink) {\n                        return true;\n                    }\n                }\n            }\n        }\n        return false;  \/\/ No augmenting path found\n    }\n\npublic:\n    \/\/ Constructor to initialize the graph with a given number of vertices\n    EdmondsKarp(int vertices) : V(vertices) {\n        graph.resize(V, vector&lt;int&gt;(V, 0));  \/\/ Initialize graph with 0s\n    }\n\n    \/\/ Function to set the capacities of edges (graph initialization)\n    void setEdge(int u, int v, int capacity) {\n        graph&#91;u]&#91;v] = capacity;\n    }\n\n    \/\/ Function to implement the Edmonds-Karp algorithm\n    int edmondsKarp(int source, int sink) {\n        \/\/ Create a residual graph initially as a copy of the input graph\n        vector&lt;vector&lt;int&gt;&gt; residualGraph = graph;\n        vector&lt;int&gt; parent(V);  \/\/ Array to store the path\n        \n        int maxFlow = 0;  \/\/ Variable to store the maximum flow\n        \n        \/\/ Augment the flow while there is an augmenting path\n        while (bfs(residualGraph, source, sink, parent)) {\n            \/\/ Find the maximum flow in the found path\n            int pathFlow = INT_MAX;\n            for (int v = sink; v != source; v = parent&#91;v]) {\n                int u = parent&#91;v];\n                pathFlow = min(pathFlow, residualGraph&#91;u]&#91;v]);  \/\/ Get the minimum capacity in the path\n            }\n\n            \/\/ Update the residual graph\n            for (int v = sink; v != source; v = parent&#91;v]) {\n                int u = parent&#91;v];\n                residualGraph&#91;u]&#91;v] -= pathFlow;  \/\/ Reduce the capacity of the forward edge\n                residualGraph&#91;v]&#91;u] += pathFlow;  \/\/ Increase the capacity of the reverse edge\n            }\n\n            \/\/ Add the flow of the current path to the total flow\n            maxFlow += pathFlow;\n        }\n\n        return maxFlow;  \/\/ Return the total maximum flow\n    }\n};\n\nint main() {\n    int V = 6;  \/\/ Number of vertices in the graph\n    EdmondsKarp ek(V);  \/\/ Create an object of EdmondsKarp class\n\n    \/\/ Set edges and their capacities (graph initialization)\n    ek.setEdge(0, 1, 16);\n    ek.setEdge(0, 2, 13);\n    ek.setEdge(1, 2, 10);\n    ek.setEdge(1, 3, 12);\n    ek.setEdge(2, 1, 4);\n    ek.setEdge(2, 4, 14);\n    ek.setEdge(3, 2, 9);\n    ek.setEdge(3, 5, 20);\n    ek.setEdge(4, 3, 7);\n    ek.setEdge(4, 5, 4);\n\n    int source = 0;  \/\/ Source node\n    int sink = 5;    \/\/ Sink node\n\n    \/\/ Find the maximum flow\n    int maxFlow = ek.edmondsKarp(source, sink);\n\n    \/\/ Output the maximum flow\n    cout &lt;&lt; \"The maximum flow from source \" &lt;&lt; source &lt;&lt; \" to sink \" &lt;&lt; sink &lt;&lt; \" is \" &lt;&lt; maxFlow &lt;&lt; endl;\n\n    return 0;\n}\nOutput :\n<strong>The maximum flow from source 0 to sink 5 is 23<\/strong><\/code><\/pre>\n\n\n\n<p>What is all pairs shortest path?<\/p>\n\n\n\n<p>An example of the all-pairs shortest path problem can be illustrated with a simple weighted directed graph representing a road network. Consider the following graph:<\/p>\n\n\n\n<figure class=\"wp-block-image size-full is-resized\"><img loading=\"lazy\" decoding=\"async\" width=\"218\" height=\"286\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/all3.png\" alt=\"\" class=\"wp-image-465\" style=\"width:1200px;height:auto\"\/><\/figure>\n\n\n\n<p>In this graph:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Vertices: There are four vertices labeled from 1 to 4.<\/li>\n\n\n\n<li>Edges: Each edge is weighted, representing the distance between connected vertices.<\/li>\n<\/ul>\n\n\n\n<p>For example:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>There is an edge from vertex 1 to vertex 3 with weight 4.<\/li>\n\n\n\n<li>There is an edge from vertex 1 to vertex 2 with weight 1.<\/li>\n<\/ul>\n\n\n\n<p>The task is to find the shortest path between every pair of vertices in this graph.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Floyd Warshall Algorithm<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"267\" height=\"226\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/allpair2.png\" alt=\"\" class=\"wp-image-464\"\/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-full is-resized\" id=\"FORD\"><img loading=\"lazy\" decoding=\"async\" width=\"620\" height=\"220\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/FLOYD1.png\" alt=\"\" class=\"wp-image-466\" style=\"width:1199px;height:auto\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/FLOYD1.png 620w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/FLOYD1-300x106.png 300w\" sizes=\"auto, (max-width: 620px) 100vw, 620px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-full is-resized\"><img loading=\"lazy\" decoding=\"async\" width=\"644\" height=\"452\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/FLOYD2.png\" alt=\"\" class=\"wp-image-467\" style=\"width:1201px;height:auto\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/FLOYD2.png 644w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/FLOYD2-300x211.png 300w\" sizes=\"auto, (max-width: 644px) 100vw, 644px\" \/><\/figure>\n\n\n\n<p><\/p>\n\n\n\n<figure class=\"wp-block-image size-full is-resized\"><img loading=\"lazy\" decoding=\"async\" width=\"694\" height=\"305\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/FLOYD3.png\" alt=\"\" class=\"wp-image-468\" style=\"width:1199px;height:auto\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/FLOYD3.png 694w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/FLOYD3-300x132.png 300w\" sizes=\"auto, (max-width: 694px) 100vw, 694px\" \/><\/figure>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"Floyd\"><strong>Floyd Warshall<\/strong><\/h3>\n\n\n\n<figure class=\"wp-block-embed is-type-video is-provider-youtube wp-block-embed-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\ud835\udc05\ud835\udc25\ud835\udc28\ud835\udc32\ud835\udc1d \ud835\udc16\ud835\udc1a\ud835\udc2b\ud835\udc2c\ud835\udc21\ud835\udc1a\ud835\udc25\ud835\udc25 : \ud835\udc00\ud835\udc25\ud835\udc25 \ud835\udc0f\ud835\udc1a\ud835\udc22\ud835\udc2b \ud835\udc12\ud835\udc21\ud835\udc28\ud835\udc2b\ud835\udc2d\ud835\udc1e\ud835\udc2c\ud835\udc2d \ud835\udc0f\ud835\udc1a\ud835\udc2d\ud835\udc21 \ud835\udc00\ud835\udc25\ud835\udc20\ud835\udc28\ud835\udc2b\ud835\udc22\ud835\udc2d\ud835\udc21\ud835\udc26|| \ud835\udc00\ud835\udc25\ud835\udc25 \ud835\udc29\ud835\udc1a\ud835\udc22\ud835\udc2b \ud835\udc2c\ud835\udc21\ud835\udc28\ud835\udc2b\ud835\udc2d\ud835\udc1e\ud835\udc2c\ud835\udc2d \ud835\udc29\ud835\udc1a\ud835\udc2d\ud835\udc21\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/l6QasEwYauA?list=PLNC-2IODvQCBd3VWnwfmQW78J7pQpOW4W\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<pre id=\"Floyd\" class=\"wp-block-code\"><code><strong><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-ast-global-color-1-color\">\/\/Here is the C program implementing the Floyd-Warshall algorithm \n\/\/with comments explaining each part of the code:<\/mark><\/strong>\n#include &lt;stdio.h&gt;\n#include &lt;limits.h&gt;\n\n#define MAX 10  \/\/ Defining the maximum size for the matrix (number of vertices)\n\n\/\/ Function to implement the Floyd-Warshall algorithm\nvoid floydWarshall(int dist&#91;MAX]&#91;MAX], int n) {\n    \/\/ k is the intermediate node, i is the source node, and j is the destination node\n    for (int k = 0; k &lt; n; k++) {  \/\/ Loop over each intermediate node\n        for (int i = 0; i &lt; n; i++) {  \/\/ Loop over each source node\n            for (int j = 0; j &lt; n; j++) {  \/\/ Loop over each destination node\n                \/\/ If the path through the intermediate node k is shorter, update the distance\n                if (dist&#91;i]&#91;k] != INT_MAX &amp;&amp; dist&#91;k]&#91;j] != INT_MAX &amp;&amp; dist&#91;i]&#91;j] &gt; dist&#91;i]&#91;k] + dist&#91;k]&#91;j]) {\n                    dist&#91;i]&#91;j] = dist&#91;i]&#91;k] + dist&#91;k]&#91;j];\n                }\n            }\n        }\n    }\n}\n\n\/\/ Function to print the distance matrix\nvoid printSolution(int dist&#91;MAX]&#91;MAX], int n) {\n    printf(\"The shortest distances between every pair of vertices are:\\n\");\n    for (int i = 0; i &lt; n; i++) {\n        for (int j = 0; j &lt; n; j++) {\n            if (dist&#91;i]&#91;j] == INT_MAX) {\n                printf(\"INF \");  \/\/ If no path exists, print INF\n            } else {\n                printf(\"%d \", dist&#91;i]&#91;j]);\n            }\n        }\n        printf(\"\\n\");\n    }\n}\n\nint main() {\n    int n, i, j;\n    \n    \/\/ Take input for number of vertices in the graph\n    printf(\"Enter the number of vertices: \");\n    scanf(\"%d\", &amp;n);\n    \/\/ Create the distance matrix (initialize with INT_MAX where there is no direct path)\n    int dist&#91;MAX]&#91;MAX];\n    printf(\"Enter the adjacency matrix (use 0 for no direct edge and other positive values for edge weights):\\n\");\n     for (i = 0; i &lt; n; i++) {\n     for (j = 0; j &lt; n; j++) {\n            scanf(\"%d\", &amp;dist&#91;i]&#91;j]);\n           \n            \/\/ If there is no direct edge, set distance to INF (INT_MAX)\n            if (dist&#91;i]&#91;j] == 0 &amp;&amp; i != j) {\n                dist&#91;i]&#91;j] = INT_MAX;\n            }\n        }\n    }\n\n    \/\/ Call the Floyd-Warshall algorithm\n    floydWarshall(dist, n);\n    \n    \/\/ Print the result\n    printSolution(dist, n);\n    \n    return 0;\n}\n\nOutput :\nEnter the number of vertices: 4\nEnter the adjacency matrix (use 0 for no direct edge and other positive values for edge weights):\n0 3 0 0\n3 0 4 0\n0 4 0 2\n0 0 2 0\n\nThe shortest distances between every pair of vertices are:\n0 3 7 5 \n3 0 4 6 \n7 4 0 2 \n5 6 2 0 <\/code><\/pre>\n\n\n\n<pre class=\"wp-block-code\"><code><strong><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-ast-global-color-1-color\">\/*To display not only the shortest distances and the vertices involved in the \nshortest paths but also the total cost (the total distance) of each shortest path, we will update the program further.We need to modify the following: Track the shortest paths and their costs. Print the shortest path from one vertex to another, showing the intermediate vertices and the total cost.*\/<\/mark><\/strong>\n#include &lt;stdio.h&gt;\n#include &lt;limits.h&gt;\n\n#define MAX 10  \/\/ Defining the maximum size for the matrix (number of vertices)\n\n\/\/ Function to implement the Floyd-Warshall algorithm\nvoid floydWarshall(int dist&#91;MAX]&#91;MAX], int next&#91;MAX]&#91;MAX], int n) {\n    \/\/ k is the intermediate node, i is the source node, and j is the destination node\n    for (int k = 0; k &lt; n; k++) {  \/\/ Loop over each intermediate node\n        for (int i = 0; i &lt; n; i++) {  \/\/ Loop over each source node\n            for (int j = 0; j &lt; n; j++) {  \/\/ Loop over each destination node\n                \/\/ If the path through the intermediate node k is shorter, update the distance\n                if (dist&#91;i]&#91;k] != INT_MAX &amp;&amp; dist&#91;k]&#91;j] != INT_MAX &amp;&amp; dist&#91;i]&#91;j] &gt; dist&#91;i]&#91;k] + dist&#91;k]&#91;j]) {\n                    dist&#91;i]&#91;j] = dist&#91;i]&#91;k] + dist&#91;k]&#91;j];\n                    next&#91;i]&#91;j] = next&#91;i]&#91;k];  \/\/ Update the next vertex on the shortest path\n                }\n            }\n        }\n    }\n}\n\n\/\/ Function to print the distance matrix\nvoid printSolution(int dist&#91;MAX]&#91;MAX], int next&#91;MAX]&#91;MAX], int n) {\n    printf(\"The shortest distances between every pair of vertices are:\\n\");\n    for (int i = 0; i &lt; n; i++) {\n        for (int j = 0; j &lt; n; j++) {\n            if (dist&#91;i]&#91;j] == INT_MAX) {\n                printf(\"INF \");  \/\/ If no path exists, print INF\n            } else {\n                printf(\"%d \", dist&#91;i]&#91;j]);\n            }\n        }\n        printf(\"\\n\");\n    }\n\n    \/\/ Now print the shortest paths and total cost\n    printf(\"\\nShortest paths between every pair of vertices (with total cost) are:\\n\");\n    for (int i = 0; i &lt; n; i++) {\n        for (int j = 0; j &lt; n; j++) {\n            if (i != j) {\n                printf(\"Shortest path from %d to %d: \", i + 1, j + 1);\n                int current = i;\n                int totalCost = 0;\n                \/\/ Traverse the path and calculate total cost\n                while (current != j) {\n                    printf(\"%d -&gt; \", current + 1);\n                    totalCost += dist&#91;current]&#91;next&#91;current]&#91;j]];  \/\/ Add the cost of the edge\n                    current = next&#91;current]&#91;j];\n                }\n                totalCost += dist&#91;current]&#91;j];  \/\/ Add the cost from last node to the destination\n                printf(\"%d | Total cost: %d\\n\", j + 1, totalCost);\n            }\n        }\n    }\n}\n\nint main() {\n    int n, i, j;\n    \n    \/\/ Take input for number of vertices in the graph\n    printf(\"Enter the number of vertices: \");\n    scanf(\"%d\", &amp;n);\n    \n    \/\/ Create the distance matrix (initialize with INT_MAX where there is no direct path)\n    int dist&#91;MAX]&#91;MAX];\n    int next&#91;MAX]&#91;MAX];\n\n    printf(\"Enter the adjacency matrix (use 0 for no direct edge and other positive values for edge weights):\\n\");\n\n    for (i = 0; i &lt; n; i++) {\n        for (j = 0; j &lt; n; j++) {\n            scanf(\"%d\", &amp;dist&#91;i]&#91;j]);\n            \n            \/\/ Initialize next matrix to help in path reconstruction\n            if (dist&#91;i]&#91;j] != 0 &amp;&amp; dist&#91;i]&#91;j] != INT_MAX) {\n                next&#91;i]&#91;j] = j;  \/\/ If there's an edge, set next&#91;i]&#91;j] as j\n            } else if (i == j) {\n                next&#91;i]&#91;j] = i;  \/\/ For diagonal, the next node is itself\n            } else {\n                next&#91;i]&#91;j] = -1;  \/\/ No path initially\n            }\n            \n            \/\/ If there is no direct edge, set distance to INF\n            if (dist&#91;i]&#91;j] == 0 &amp;&amp; i != j) {\n                dist&#91;i]&#91;j] = INT_MAX;\n                next&#91;i]&#91;j] = -1;\n            }\n        }\n    }\n\n    \/\/ Call the Floyd-Warshall algorithm\n    floydWarshall(dist, next, n);\n    \n    \/\/ Print the result\n    printSolution(dist, next, n);\n    \n    return 0;\n}\nOutput :\nEnter the number of vertices: 4\nEnter the adjacency matrix (use 0 for no direct edge and other positive values for edge weights):\n0 3 0 0\n3 0 4 0\n0 4 0 2\n0 0 2 0\n\nThe shortest distances between every pair of vertices are:\n0 3 7 5 \n3 0 4 6 \n7 4 0 2 \n5 6 2 0 \n\nShortest paths between every pair of vertices (with total cost) are:\nShortest path from 1 to 2: 1 -&gt; 2 | Total cost: 3\nShortest path from 1 to 3: 1 -&gt; 2 -&gt; 3 | Total cost: 7\nShortest path from 1 to 4: 1 -&gt; 2 -&gt; 3 -&gt; 4 | Total cost: 5\nShortest path from 2 to 1: 2 -&gt; 1 | Total cost: 3\nShortest path from 2 to 3: 2 -&gt; 3 | Total cost: 4\nShortest path from 2 to 4: 2 -&gt; 3 -&gt; 4 | Total cost: 6\nShortest path from 3 to 1: 3 -&gt; 2 -&gt; 1 | Total cost: 7\nShortest path from 3 to 2: 3 -&gt; 2 | Total cost: 4\nShortest path from 3 to 4: 3 -&gt; 4 | Total cost: 2\nShortest path from 4 to 1: 4 -&gt; 3 -&gt; 2 -&gt; 1 | Total cost: 5\nShortest path from 4 to 2: 4 -&gt; 3 -&gt; 2 | Total cost: 6\nShortest path from 4 to 3: 4 -&gt; 3 | Total cost: 2\n<\/code><\/pre>\n\n\n\n<pre class=\"wp-block-code\"><code><strong><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-ast-global-color-1-color\">\/\/C++ Code Using Class and Vector STL:<\/mark><\/strong>\n#include &lt;iostream&gt;\n#include &lt;vector&gt;\n#include &lt;limits.h&gt;\nusing namespace std;\n\nclass FloydWarshall {\nprivate:\n    vector&lt;vector&lt;int&gt;&gt; dist;  \/\/ Distance matrix (using vector of vectors)\n    int n;  \/\/ Number of vertices\n\npublic:\n    \/\/ Constructor to initialize the number of vertices and the distance matrix\n    FloydWarshall(int vertices) : n(vertices) {\n        dist.resize(n, vector&lt;int&gt;(n, INT_MAX));  \/\/ Resize the matrix with INT_MAX initially\n    }\n\n    \/\/ Method to take input for the adjacency matrix\n    void inputGraph() {\n        cout &lt;&lt; \"Enter the adjacency matrix (use 0 for no direct edge and other positive values for edge weights):\\n\";\n        for (int i = 0; i &lt; n; i++) {\n            for (int j = 0; j &lt; n; j++) {\n                cin &gt;&gt; dist&#91;i]&#91;j];\n                if (dist&#91;i]&#91;j] == 0 &amp;&amp; i != j) {\n                    dist&#91;i]&#91;j] = INT_MAX;  \/\/ No path exists, set to infinity\n                }\n            }\n        }\n    }\n\n    \/\/ Method to implement the Floyd-Warshall algorithm\n    void runAlgorithm() {\n        \/\/ Loop over each intermediate node (k)\n        for (int k = 0; k &lt; n; k++) {\n            \/\/ Loop over each source node (i)\n            for (int i = 0; i &lt; n; i++) {\n                \/\/ Loop over each destination node (j)\n                for (int j = 0; j &lt; n; j++) {\n                    \/\/ If a shorter path is found through the intermediate node k\n                    if (dist&#91;i]&#91;k] != INT_MAX &amp;&amp; dist&#91;k]&#91;j] != INT_MAX &amp;&amp; dist&#91;i]&#91;j] &gt; dist&#91;i]&#91;k] + dist&#91;k]&#91;j]) {\n                        dist&#91;i]&#91;j] = dist&#91;i]&#91;k] + dist&#91;k]&#91;j];\n                    }\n                }\n            }\n        }\n    }\n\n    \/\/ Method to print the distance matrix\n    void printSolution() {\n        cout &lt;&lt; \"The shortest distances between every pair of vertices are:\\n\";\n        for (int i = 0; i &lt; n; i++) {\n            for (int j = 0; j &lt; n; j++) {\n                if (dist&#91;i]&#91;j] == INT_MAX) {\n                    cout &lt;&lt; \"INF \";  \/\/ If no path exists, print INF\n                } else {\n                    cout &lt;&lt; dist&#91;i]&#91;j] &lt;&lt; \" \";\n                }\n            }\n            cout &lt;&lt; endl;\n        }\n    }\n};\n\nint main() {\n    int n;\n\n    \/\/ Take input for number of vertices in the graph\n    cout &lt;&lt; \"Enter the number of vertices: \";\n    cin &gt;&gt; n;\n\n    \/\/ Create an object of FloydWarshall class\n    FloydWarshall fw(n);\n\n    \/\/ Take input for the adjacency matrix\n    fw.inputGraph();\n\n    \/\/ Run the Floyd-Warshall algorithm\n    fw.runAlgorithm();\n\n    \/\/ Print the result (shortest distances)\n    fw.printSolution();\n\n    return 0;\n}\nEnter the number of vertices: 4\nEnter the adjacency matrix (use 0 for no direct edge and other positive values for edge weights):\n0 3 0 0\n3 0 4 0\n0 4 0 2\n0 0 2 0\nThe shortest distances between every pair of vertices are:\n0 3 7 5 \n3 0 4 6 \n7 4 0 2 \n5 6 2 0 <\/code><\/pre>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Networks Flow : Bipartite Matching<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image size-large\" id=\"Bip\"><img loading=\"lazy\" decoding=\"async\" width=\"767\" height=\"1024\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/1-3-767x1024.jpg\" alt=\"\" class=\"wp-image-490\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/1-3-767x1024.jpg 767w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/1-3-225x300.jpg 225w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/1-3-768x1025.jpg 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/1-3-1151x1536.jpg 1151w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/1-3.jpg 1198w\" sizes=\"auto, (max-width: 767px) 100vw, 767px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"759\" height=\"1024\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/WhatsApp-Image-2024-02-10-at-20.45.29-759x1024.jpeg\" alt=\"\" class=\"wp-image-486\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/WhatsApp-Image-2024-02-10-at-20.45.29-759x1024.jpeg 759w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/WhatsApp-Image-2024-02-10-at-20.45.29-222x300.jpeg 222w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/WhatsApp-Image-2024-02-10-at-20.45.29-768x1036.jpeg 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/WhatsApp-Image-2024-02-10-at-20.45.29.jpeg 949w\" sizes=\"auto, (max-width: 759px) 100vw, 759px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"795\" height=\"1024\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/3-3-795x1024.png\" alt=\"\" class=\"wp-image-492\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/3-3-795x1024.png 795w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/3-3-233x300.png 233w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/3-3-768x989.png 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/3-3-1192x1536.png 1192w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/3-3.png 1242w\" sizes=\"auto, (max-width: 795px) 100vw, 795px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"771\" height=\"1024\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/2-1-771x1024.png\" alt=\"\" class=\"wp-image-488\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/2-1-771x1024.png 771w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/2-1-226x300.png 226w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/2-1-768x1021.png 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/2-1-1156x1536.png 1156w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/2-1.png 1204w\" sizes=\"auto, (max-width: 771px) 100vw, 771px\" \/><\/figure>\n\n\n\n<p><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code><strong><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-ast-global-color-1-color\">\/\/ C code for bipartite matching<\/mark><\/strong>\n#include &lt;stdio.h&gt;\n#include &lt;stdbool.h&gt;\n\n\/\/ Function to check if a path exists from u to v using BFS\nbool bpm(bool bpGraph&#91;100]&#91;100], int u, bool seen&#91;], int matchR&#91;]) {\n    \/\/ Base case: If this column is not assigned to any row yet\n    for (int v = 0; v &lt; 100; v++) {\n        if (bpGraph&#91;u]&#91;v] &amp;&amp; !seen&#91;v]) { \n            seen&#91;v] = true; \n\n            \/\/ If v is not visited and there is an edge from u to v, \n            \/\/ then try to assign this v to an unmatched row. \n            if (matchR&#91;v] &lt; 0 || bpm(bpGraph, matchR&#91;v], seen, matchR)) {\n                matchR&#91;v] = u;\n                return true;\n            }\n        }\n    }\n    return false;\n}\n\n\/\/ Returns maximum number of matching from M to N\nint maxBPM(bool bpGraph&#91;100]&#91;100], int n) {\n    \/\/ An array to keep track of the matchings of the vertices of N\n    int matchR&#91;100]; \n\n    \/\/ Initially all jobs are available\n    for(int i = 0; i &lt; 100; i++)\n        matchR&#91;i] = -1; \n\n    int result = 0; \/\/ Count of jobs assigned to applicants\n    for (int u = 0; u &lt; n; u++) {\n        \/\/ Mark all vertices as not visited for next applicant.\n        bool seen&#91;100];\n        for(int i=0; i&lt;100; i++)\n            seen&#91;i] = false; \n\n        \/\/ Find if the applicant 'u' can get any job\n        if (bpm(bpGraph, u, seen, matchR))\n            result++;\n    }\n    return result;\n}\n\n\/\/ Driver code\nint main() {\n    \/\/ Let us create a sample graph \n    \/\/ where the applicants are at one side of the \n    \/\/ graph, jobs at the other side and connecting \n    \/\/ lines indicate possible assignments. \n    bool bpGraph&#91;100]&#91;100] = {\n        {0, 1, 1, 0, 0},\n        {1, 0, 0, 1, 0},\n        {0, 0, 1, 0, 1},\n        {0, 0, 0, 0, 0},\n        {0, 0, 1, 0, 1}\n    };\n    int n = 5; \n    printf(\"Maximum number of applicants that can be assigned jobs = %d\\n\", maxBPM(bpGraph, n));\n\n    return 0;\n}\nOutput :\nMaximum number of applicants that can be assigned jobs = 3<\/code><\/pre>\n\n\n\n<pre class=\"wp-block-code\"><code><strong><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-ast-global-color-1-color\">\/\/ C++ code for bipartite matching<\/mark><\/strong>\n#include &lt;iostream&gt;\n#include &lt;vector&gt;\n#include &lt;queue&gt;\n\nusing namespace std;\n\nclass BipartiteMatching {\nprivate:\n    int N; \/\/ Number of vertices on the left side\n    int M; \/\/ Number of vertices on the right side\n    vector&lt;vector&lt;int&gt;&gt; graph; \n\npublic:\n    BipartiteMatching(int N, int M) {\n        this-&gt;N = N;\n        this-&gt;M = M;\n        graph.resize(N, vector&lt;int&gt;(M, 0)); \n    }\n\n    void addEdge(int u, int v) {\n        graph&#91;u]&#91;v] = 1;\n    }\n\n    bool bfs(vector&lt;int&gt;&amp; matchR, vector&lt;bool&gt;&amp; seen) {\n        queue&lt;int&gt; q; \n        for (int u = 0; u &lt; N; u++) {\n            if (matchR&#91;u] == -1) {\n                seen&#91;u] = true;\n                q.push(u);\n            }\n        }\n\n        while (!q.empty()) {\n            int u = q.front();\n            q.pop();\n\n            for (int v = 0; v &lt; M; v++) {\n                if (graph&#91;u]&#91;v] &amp;&amp; !seen&#91;v]) {\n                    seen&#91;v] = true;\n                    if (matchR&#91;v] &lt; 0 || bfs(matchR, seen)) {\n                        matchR&#91;v] = u;\n                        return true;\n                    }\n                }\n            }\n        }\n\n        return false;\n    }\n\n    int maxMatching() {\n        vector&lt;int&gt; matchR(M, -1); \/\/ Array to store the matchings\n        int result = 0;\n\n        for (int u = 0; u &lt; N; u++) {\n            vector&lt;bool&gt; seen(M, false);\n            if (bfs(matchR, seen)) {\n                result++;\n            }\n        }\n\n        return result;\n    }\n};\n\nint main() {\n    int N = 5, M = 5; \n    BipartiteMatching bm(N, M);\n\n    bm.addEdge(0, 1);\n    bm.addEdge(0, 2);\n    bm.addEdge(1, 0);\n    bm.addEdge(1, 3);\n    bm.addEdge(2, 2);\n    bm.addEdge(2, 4);\n    bm.addEdge(4, 2);\n    bm.addEdge(4, 4);\n\n    cout &lt;&lt; \"Maximum number of matchings: \" &lt;&lt; bm.maxMatching() &lt;&lt; endl;\n\n    return 0;\n}\nOutput :\nMaximum number of applicants that can be assigned jobs = 3<\/code><\/pre>\n\n\n\n<p><strong>Explanation:<\/strong><\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Include Headers:<\/strong>\n<ul class=\"wp-block-list\">\n<li><code>iostream<\/code>: For input\/output operations.<\/li>\n\n\n\n<li><code>vector<\/code>: For using the <code>vector<\/code> STL.<\/li>\n\n\n\n<li><code>queue<\/code>: For using the <code>queue<\/code> STL in the BFS implementation.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>BipartiteMatching Class:<\/strong>\n<ul class=\"wp-block-list\">\n<li><strong>Private Members:<\/strong>\n<ul class=\"wp-block-list\">\n<li><code>N<\/code>: Number of vertices on the left side.<\/li>\n\n\n\n<li><code>M<\/code>: Number of vertices on the right side.<\/li>\n\n\n\n<li><code>graph<\/code>: A 2D vector representing the bipartite graph. <code>graph[u][v]<\/code> is 1 if there&#8217;s an edge from <code>u<\/code> to <code>v<\/code>, 0 otherwise.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Public Members:<\/strong>\n<ul class=\"wp-block-list\">\n<li><strong>Constructor:<\/strong> Initializes <code>N<\/code>, <code>M<\/code>, and resizes the <code>graph<\/code> vector.<\/li>\n\n\n\n<li><strong>addEdge():<\/strong> Adds an edge between vertices <code>u<\/code> and <code>v<\/code>.<\/li>\n\n\n\n<li><strong>bfs():<\/strong> Implements Breadth-First Search to find an augmenting path.<\/li>\n\n\n\n<li><strong>maxMatching():<\/strong> Finds the maximum number of matchings in the bipartite graph.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>bfs() Function:<\/strong>\n<ul class=\"wp-block-list\">\n<li>Uses a queue to perform BFS.<\/li>\n\n\n\n<li>Initially, enqueues all unmatched vertices on the left side.<\/li>\n\n\n\n<li>In each iteration:\n<ul class=\"wp-block-list\">\n<li>Dequeues a vertex <code>u<\/code>.<\/li>\n\n\n\n<li>Explores all neighbors <code>v<\/code> of <code>u<\/code>.<\/li>\n\n\n\n<li>If <code>v<\/code> is not visited:\n<ul class=\"wp-block-list\">\n<li>Marks <code>v<\/code> as visited.<\/li>\n\n\n\n<li>If <code>v<\/code> is unmatched or an augmenting path can be found for the vertex currently matched with <code>v<\/code>, assign <code>u<\/code> to <code>v<\/code> and return <code>true<\/code>.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>maxMatching() Function:<\/strong>\n<ul class=\"wp-block-list\">\n<li>Initializes an array <code>matchR<\/code> to store the matchings.<\/li>\n\n\n\n<li>Iterates through all vertices on the left side.\n<ul class=\"wp-block-list\">\n<li>Calls <code>bfs()<\/code> to check if an augmenting path exists for the current vertex.<\/li>\n\n\n\n<li>If an augmenting path is found, increment the <code>result<\/code> count.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>Returns the maximum number of matchings.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>main() Function:<\/strong>\n<ul class=\"wp-block-list\">\n<li>Creates a <code>BipartiteMatching<\/code> object.<\/li>\n\n\n\n<li>Adds edges to the graph using <code>addEdge()<\/code>.<\/li>\n\n\n\n<li>Calls <code>maxMatching()<\/code> to find the maximum number of matchings.<\/li>\n\n\n\n<li>Prints the result.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\n<p>This above C++ code provides a more object-oriented and concise implementation of the bipartite matching algorithm using STL features like <code>vector<\/code> and <code>queue<\/code>.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"Cycle\"><strong>Cycle Cancellation Algorithm<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-embed is-type-video is-provider-youtube wp-block-embed-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"(1\/2) Solving Minimum Cost Flow Problems: Cycle Cancelling Algorithm Explained\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/1rMv2B70yz8?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<figure class=\"wp-block-embed is-type-video is-provider-youtube wp-block-embed-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"(2\/2)Solving Minimum Cost Flow Problems: Cycle Cancelling Algorithm Explained\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/UNwG-LCMBAo?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Dijkstra algorithm<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-embed is-type-video is-provider-youtube wp-block-embed-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"Dijkstra&#039;s algorithm\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/VvfC9s_nqPg?start=4&#038;feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<pre id=\"Dijkstra\" class=\"wp-block-code\"><code><strong><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-ast-global-color-1-color\">\/\/ C code for Dijkstra algorithm<\/mark><\/strong>\n#include &lt;stdio.h&gt;\n#include &lt;limits.h&gt;\n\n#define V 9 \/\/ Number of vertices in the graph\n\n\/\/ Function to print the constructed distance array\nvoid printSolution(int dist&#91;])\n{\n    printf(\"Vertex \\t\\t Distance from Source\\n\");\n    for (int i = 0; i &lt; V; i++)\n        printf(\"%d \\t\\t %d\\n\", i, dist&#91;i]);\n}\n\n\/\/ Function to find the vertex with the minimum distance value, \n\/\/ from the set of vertices not yet included in shortest path tree\nint minDistance(int dist&#91;], bool sptSet&#91;])\n{\n    \/\/ Initialize min value\n    int min = INT_MAX, min_index;\n\n    for (int v = 0; v &lt; V; v++)\n        if (sptSet&#91;v] == false &amp;&amp; dist&#91;v] &lt;= min)\n            min = dist&#91;v], min_index = v;\n\n    return min_index;\n}\n\n\/\/ Function to implement Dijkstra's single source shortest path algorithm\n\/\/ from a given source to all other vertices\nvoid dijkstra(int graph&#91;V]&#91;V], int src)\n{\n    int dist&#91;V];     \/\/ The output array. dist&#91;i] will hold the shortest\n                    \/\/ distance from src to i\n\n    bool sptSet&#91;V]; \/\/ sptSet&#91;i] will be true if vertex i is included in shortest\n                    \/\/ path tree or shortest distance from src to i is finalized\n\n    \/\/ Initialize all distances as INFINITE and stptSet&#91;] as false\n    for (int i = 0; i &lt; V; i++)\n        dist&#91;i] = INT_MAX, sptSet&#91;i] = false;\n\n    \/\/ Distance of source vertex from itself will always be 0\n    dist&#91;src] = 0;\n\n    \/\/ Find shortest path for all vertices\n    for (int count = 0; count &lt; V - 1; count++) {\n        \/\/ Pick the minimum distance vertex from the set of vertices \n        \/\/ not yet processed. u is always equal to src in the first iteration.\n        int u = minDistance(dist, sptSet);\n\n        \/\/ Mark the picked vertex as processed\n        sptSet&#91;u] = true;\n\n        \/\/ Update dist value of the adjacent vertices of the picked vertex.\n        for (int v = 0; v &lt; V; v++)\n\n            \/\/ Update dist&#91;v] only if is not in sptSet, there is an edge from \n            \/\/ u to v, and total weight of path from src to v through u is \n            \/\/ smaller than current value of dist&#91;v]\n            if (!sptSet&#91;v] &amp;&amp; graph&#91;u]&#91;v] &amp;&amp; dist&#91;u] != INT_MAX &amp;&amp; dist&#91;u] + graph&#91;u]&#91;v] &lt; dist&#91;v])\n                dist&#91;v] = dist&#91;u] + graph&#91;u]&#91;v];\n    }\n\n    \/\/ print the constructed distance array\n    printSolution(dist);\n}\n\n\/\/ Driver program to test above functions\nint main()\n{\n    \/* Let us create the example graph discussed above *\/\n    int graph&#91;V]&#91;V] = { { 0, 4, 0, 0, 0, 0, 0, 8, 0 },\n                        { 4, 0, 8, 0, 0, 0, 0, 11, 0 },\n                        { 0, 8, 0, 7, 0, 4, 0, 0, 2 },\n                        { 0, 0, 7, 0, 9, 14, 0, 0, 0 },\n                        { 0, 0, 0, 9, 0, 10, 0, 0, 0 },\n                        { 0, 0, 4, 14, 10, 0, 2, 0, 0 },\n                        { 0, 0, 0, 0, 0, 2, 0, 1, 6 },\n                        { 8, 11, 0, 0, 0, 0, 1, 0, 7 },\n                        { 0, 0, 2, 0, 0, 0, 6, 7, 0 } };\n\n    dijkstra(graph, 0);\n\n    return 0;\n}\nOutput:\n\nVertex     Distance from Source\n0          0\n1          4\n2          8\n3          7\n4          9\n5          10\n6          2\n7          8\n8          7\nThis output shows the shortest distances from vertex 0 to all other vertices in the given grap<\/code><\/pre>\n\n\n\n<pre class=\"wp-block-code\"><code><strong><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-ast-global-color-1-color\">\/\/C++ code for Dijkstra algorithm<\/mark><\/strong>\n#include &lt;iostream&gt;\n#include &lt;vector&gt;\n#include &lt;limits.h&gt;\n#include &lt;algorithm&gt;\n\nusing namespace std;\n\nclass Graph {\nprivate:\n    int V; \/\/ Number of vertices\n    vector&lt;vector&lt;int&gt;&gt; adj; \/\/ Adjacency list representation\n\npublic:\n    Graph(int V) {\n        this-&gt;V = V;\n        adj.resize(V);\n    }\n\n    void addEdge(int u, int v, int w) {\n        adj&#91;u].push_back({v, w}); \n        \/\/ Assuming undirected graph, add edge in both directions\n        adj&#91;v].push_back({u, w}); \n    }\n\n    int minDistance(vector&lt;int&gt;&amp; dist, vector&lt;bool&gt;&amp; sptSet) {\n        int min = INT_MAX, min_index;\n\n        for (int v = 0; v &lt; V; v++)\n            if (sptSet&#91;v] == false &amp;&amp; dist&#91;v] &lt;= min)\n                min = dist&#91;v], min_index = v;\n\n        return min_index;\n    }\n\n    void dijkstra(int src) {\n        vector&lt;int&gt; dist(V, INT_MAX); \n        vector&lt;bool&gt; sptSet(V, false);\n\n        dist&#91;src] = 0;\n\n        for (int count = 0; count &lt; V - 1; count++) {\n            int u = minDistance(dist, sptSet);\n            sptSet&#91;u] = true;\n\n            for (auto i : adj&#91;u]) {\n                int v = i&#91;0];\n                int weight = i&#91;1];\n\n                if (!sptSet&#91;v] &amp;&amp; dist&#91;u] != INT_MAX &amp;&amp; dist&#91;u] + weight &lt; dist&#91;v])\n                    dist&#91;v] = dist&#91;u] + weight;\n            }\n        }\n\n        cout &lt;&lt; \"Vertex \\t\\t Distance from Source\\n\";\n        for (int i = 0; i &lt; V; i++)\n            cout &lt;&lt; i &lt;&lt; \" \\t\\t \" &lt;&lt; dist&#91;i] &lt;&lt; endl;\n    }\n};\n\nint main() {\n    int V = 9;\n    Graph g(V);\n\n    g.addEdge(0, 1, 4);\n    g.addEdge(0, 7, 8);\n    g.addEdge(1, 2, 8);\n    g.addEdge(1, 7, 11);\n    g.addEdge(2, 3, 7);\n    g.addEdge(2, 8, 2);\n    g.addEdge(2, 5, 4);\n    g.addEdge(3, 4, 9);\n    g.addEdge(3, 5, 14);\n    g.addEdge(4, 5, 10);\n    g.addEdge(5, 6, 2);\n    g.addEdge(6, 7, 1);\n    g.addEdge(6, 8, 6);\n    g.addEdge(7, 8, 7);\n\n    g.dijkstra(0);\n\n    return 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>A flow network, also known as a network flow, is a directed graph where each edge has a capacity and each node (except for the source and sink nodes) has a flow value associated with it. Flow networks are commonly used to model transportation or distribution systems, such as water distribution networks, traffic flow, or [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"default","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","ast-disable-related-posts":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"footnotes":""},"class_list":["post-460","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/cyberenlightener.com\/index.php?rest_route=\/wp\/v2\/pages\/460","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/cyberenlightener.com\/index.php?rest_route=\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/cyberenlightener.com\/index.php?rest_route=\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/cyberenlightener.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/cyberenlightener.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=460"}],"version-history":[{"count":35,"href":"https:\/\/cyberenlightener.com\/index.php?rest_route=\/wp\/v2\/pages\/460\/revisions"}],"predecessor-version":[{"id":1760,"href":"https:\/\/cyberenlightener.com\/index.php?rest_route=\/wp\/v2\/pages\/460\/revisions\/1760"}],"wp:attachment":[{"href":"https:\/\/cyberenlightener.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=460"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}