{"id":1392,"date":"2015-06-15T11:17:13","date_gmt":"2015-06-15T05:47:13","guid":{"rendered":"https:\/\/theoryofprogramming.wordpress.com\/?page_id=1392"},"modified":"2015-06-15T11:17:13","modified_gmt":"2015-06-15T05:47:13","slug":"bellman-ford-algorithm-using-cpp-stl","status":"publish","type":"page","link":"https:\/\/theoryofcoding.com\/index.php\/bellman-ford-algorithm-using-cpp-stl\/","title":{"rendered":"Bellman Ford\u00a0Algorithm using C++ STL"},"content":{"rendered":"<p>Hello people..! This is a special extension to my post on <strong><a href=\"http:\/\/theoryofprogramming.azurewebsites.net\/2015\/01\/19\/bellman-ford-algorithm\/\">Bellman Ford Algorithm<\/a><\/strong>.\u00a0Here, I give you a different implementation, Bellman Ford\u00a0Algorithm using C++ STL. Some of the features of this code are \u2013<\/p>\n<ul>\n<li>The Adjacency List used is exactly as in <strong><a href=\"http:\/\/theoryofprogramming.azurewebsites.net\/adjacency-list-using-cpp-stl\/\">Adjacency List using C++ STL<\/a><\/strong>.<\/li>\n<li>The Bellman Ford\u00a0algorithm function uses <a href=\"http:\/\/www.fredosaurus.com\/notes-cpp\/functions\/refparams.html\">C++ reference parameters<\/a> to yield the necessary results.<\/li>\n<li>The <b><span style=\"font-family:Consolas;\">shortestDistances<\/span><\/b> array is now a vector of pairs.<\/li>\n<li>It prints the vertices of negative cycle if the algorithm detects one.<\/li>\n<\/ul>\n<pre class=\"brush: cpp; title: ; notranslate\" title=\"\">\n\/*\n * Bellman-Ford Algorithm\n * using C++ STL\n * \n * Authored by,\n * Vamsi Sangam\n *\n *\/\n\n#include &lt;cstdio&gt;\n#include &lt;climits&gt;\n#include &lt;vector&gt;\n#include &lt;list&gt;\n#include &lt;utility&gt;\n\nusing namespace std;\n\nvoid PrintNegativeCycle(vector&lt; pair&lt;int, int&gt; &gt; shortestDistances, int vertex, int startVertex)\n{\n\tif (vertex == startVertex) {\n        printf(&quot;%d &quot;, vertex);\n    } else if (shortestDistances&#x5B;vertex].second == 0) {\n        PrintNegativeCycle(shortestDistances, startVertex, startVertex);\n        printf(&quot;%d &quot;, vertex);\n    } else {\n        PrintNegativeCycle(shortestDistances, shortestDistances&#x5B;vertex].second, startVertex);\n        printf(&quot;%d &quot;, vertex);\n    }\n}\n\n\/\/ Bellman-Ford Algorithm which takes the Adjacency List, starting vertex,\n\/\/ and an empty shortestDistances vector as input. It applies the algorithm\n\/\/ and keeps filling values into shortestDistances which is a reference\n\/\/ parameter. It returns true if there are no negative edges, and vice-versa.\nint bellmanFord(\n\t\t\t\t\tvector&lt; list&lt; pair&lt;int, int&gt; &gt; &gt; adjacencyList, \n\t\t\t\t\tint vertices,\n\t\t\t\t\tint startVertex,\n\t\t\t\t\tvector&lt; pair&lt;int, int&gt; &gt; &amp; shortestDistances\n\t\t\t   )\n{\n\tlist&lt; pair&lt;int, int&gt; &gt;::iterator traverse;\n\tint i, j, k;\n\t\n\t\/\/ Initialisation\n\tfor (i = 0; i &lt;= vertices; ++i) {\n\t\tshortestDistances&#x5B;i].first = INT_MAX;\n\t\tshortestDistances&#x5B;i].second = -1;\n\t}\n\t\n\t\/\/ Setting distance to source = 0\n\tshortestDistances&#x5B;startVertex].first = 0;\n\tshortestDistances&#x5B;startVertex].second = 0;\n\t\n\t\/\/ The Algorithm that computes Shortest Distances\n\tfor (i = 1; i &lt;= vertices - 1; ++i) {\t\/\/ Runs 'vertices - 1' times = O(|V|)\n\t\tfor (j = 1; j &lt;= vertices; ++j) {\t\/\/ Runs as many times as the edges = O(|E|)\n\t\t\t\/\/ The code ahead basically explores the whole of Adjcency List,\n\t\t\t\/\/ covering one edge once, so the runtime of the code in this \n\t\t\t\/\/ block is O(|E|)\n\t\t\t\n\t\t\ttraverse = adjacencyList&#x5B;j].begin();\n\t\t\t\n\t\t\twhile (traverse != adjacencyList&#x5B;j].end()) {\n\t\t\t\tif (shortestDistances&#x5B;j].first == INT_MAX) {\n\t\t\t\t\t\/\/ Important...!\n\t\t\t\t\t\/\/traverse = traverse-&gt;next;\n\t\t\t\t\t++traverse;\n\t\t\t\t\tcontinue;\n\t\t\t\t}\n\t\t\t\t\n\t\t\t\t\/\/ Checking for Relaxation\n\t\t\t\tif ((*traverse).second + shortestDistances&#x5B;j].first &lt; \n\t\t\t\t\t\t\t\t\t\tshortestDistances&#x5B;(*traverse).first].first) {\n\t\t\t\t\t\/\/ Relaxation\n\t\t\t\t\tshortestDistances&#x5B;(*traverse).first].first = (*traverse).second\n\t\t\t\t\t\t\t\t\t\t+ shortestDistances&#x5B;j].first;\n\t\t\t\t\tshortestDistances&#x5B;(*traverse).first].second = j;\n\t\t\t\t}\n\t\t\t\t\n\t\t\t\t++traverse;\n\t\t\t}\n\t\t}\n\t}\n\t\n\t\/\/ Checking for Negative Cycles\n\tfor (j = 1; j &lt;= vertices; ++j) {\n\t\ttraverse = adjacencyList&#x5B;j].begin();\n\t\t\n\t\twhile (traverse != adjacencyList&#x5B;j].end()) {\n\t\t\t\/\/ Checking for further relaxation\n\t\t\tif ((*traverse).second + shortestDistances&#x5B;j].first &lt; \n\t\t\t\t\t\t\t\t\t\tshortestDistances&#x5B;(*traverse).first].first) {\n\t\t\t\t\/\/ Negative Cycle found as further relaxation is possible\n\t\t\t\treturn j;\n\t\t\t}\n\t\t\t\n\t\t\t++traverse;\n\t\t}\n\t}\n\t\n\treturn -1;\n}\n\nint main()\n{\n\tint vertices, edges, v1, v2, weight;\n\t\n\tprintf(&quot;Enter the Number of Vertices -\\n&quot;);\n\tscanf(&quot;%d&quot;, &amp;vertices);\n\t\n\tprintf(&quot;Enter the Number of Edges -\\n&quot;);\n\tscanf(&quot;%d&quot;, &amp;edges);\n\t\n\t\/\/ Adjacency List is a vector of list.\n\t\/\/ Where each element is a pair&lt;int, int&gt;\n\t\/\/ pair.first -&gt; the edge's destination\n\t\/\/ pair.second -&gt; edge's weight\n\tvector&lt; list&lt; pair&lt;int, int&gt; &gt; &gt; adjacencyList(vertices + 1);\n\t\n\tprintf(&quot;Enter the Edges V1 -&gt; V2, of weight W\\n&quot;);\n\t\n\tfor (int i = 1; i &lt;= edges; ++i) {\n\t\tscanf(&quot;%d%d%d&quot;, &amp;v1, &amp;v2, &amp;weight);\n\t\t\n\t\t\/\/ Adding Edge to the Directed Graph\n\t\tadjacencyList&#x5B;v1].push_back(make_pair(v2, weight));\n\t}\n\t\n\tprintf(&quot;\\nThe Adjacency List-\\n&quot;);\n\t\/\/ Printing Adjacency List\n\tfor (int i = 1; i &lt; adjacencyList.size(); ++i) {\n\t\tprintf(&quot;adjacencyList&#x5B;%d] &quot;, i);\n\t\t\n\t\tlist&lt; pair&lt;int, int&gt; &gt;::iterator itr = adjacencyList&#x5B;i].begin();\n\t\t\n\t\twhile (itr != adjacencyList&#x5B;i].end()) {\n\t\t\tprintf(&quot; -&gt; %d(%d)&quot;, (*itr).first, (*itr).second);\n\t\t\t++itr;\n\t\t}\n\t\tprintf(&quot;\\n&quot;);\n\t}\n\t\t\n\tvector&lt; pair&lt;int, int&gt; &gt; shortestDistances(vertices + 1);\n\t\/\/ shortestDistances is a vector of pairs\n\t\/\/ pair.first -&gt; the shortest distance from start vertex\n\t\/\/ pair.second -&gt; parent vertex in the shortest path\n\t\n\tint startVertex;\n\t\n\tprintf(&quot;\\nEnter a Start Vertex -\\n&quot;);\n\tscanf(&quot;%d&quot;, &amp;startVertex);\n\t\n\tint returnValue = bellmanFord(adjacencyList, vertices, startVertex, shortestDistances);\n\t\n\tif (returnValue == -1) {\n\t\tprintf(&quot;No Negative Cycles exist in the Graph -\\n&quot;);\n\t} else {\n\t\tprintf(&quot;Negative Cycles exists in the Graph -\\n&quot;);\n\t\t\/\/ The Bellman-Ford Algorithm does not work with negative cycles,\n\t\t\/\/ all it can do is merely detect them, so when a negative cycle\n\t\t\/\/ is detected, the shortestDistances vector has wrong values\n\t\t\n\t\tPrintNegativeCycle(shortestDistances, shortestDistances&#x5B;returnValue].second\n\t\t\t\t\t\t\t\t\t\t\t, returnValue);\n\t\t\n\t\treturn 0;\n\t}\n\t\n\tprintf(&quot;\\n\\nVertex    Shortest Distance to Vertex %d     Parent Vertex-\\n&quot;, startVertex);\n\tfor (int i = 1; i &lt;= vertices; ++i) {\n\t\tprintf(&quot;%d \\t  %d \\t\\t\\t\\t    %d\\n&quot;, i, shortestDistances&#x5B;i].first,\n\t\t\t\t\t\t\t\t\t\t\t\tshortestDistances&#x5B;i].second);\n\t}\n\t\n\treturn 0;\n}\n<\/pre>\n<p>Keep comparing every strange line with the simple C++ code\u2026 I\u2019m sure you&#8217;ll get it..! \ud83d\ude42 \u2026 Feel free to comment if you have any doubts..! Keep practising..! Happy Coding..! \ud83d\ude00<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Hello people..! This is a special extension to my post on Bellman Ford Algorithm.\u00a0Here, I give you a different implementation, Bellman Ford\u00a0Algorithm [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"open","ping_status":"open","template":"","meta":{"jetpack_post_was_ever_published":false,"footnotes":""},"class_list":["post-1392","page","type-page","status-publish","hentry"],"jetpack_sharing_enabled":true,"jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/theoryofcoding.com\/index.php\/wp-json\/wp\/v2\/pages\/1392","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/theoryofcoding.com\/index.php\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/theoryofcoding.com\/index.php\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/theoryofcoding.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/theoryofcoding.com\/index.php\/wp-json\/wp\/v2\/comments?post=1392"}],"version-history":[{"count":0,"href":"https:\/\/theoryofcoding.com\/index.php\/wp-json\/wp\/v2\/pages\/1392\/revisions"}],"wp:attachment":[{"href":"https:\/\/theoryofcoding.com\/index.php\/wp-json\/wp\/v2\/media?parent=1392"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}