{"id":1226,"date":"2024-07-03T07:45:45","date_gmt":"2024-07-03T07:45:45","guid":{"rendered":"https:\/\/britainwriters.com\/answers\/?p=1226"},"modified":"2024-07-03T07:45:52","modified_gmt":"2024-07-03T07:45:52","slug":"inter-city-bus-networks-with-kruskals-algorithm-assignment-2","status":"publish","type":"post","link":"https:\/\/britainwriters.com\/answers\/inter-city-bus-networks-with-kruskals-algorithm-assignment-2\/","title":{"rendered":"\u00a0Inter-City Bus Networks with Kruskal&#8217;s Algorithm Assignment"},"content":{"rendered":"\n<h3 class=\"wp-block-heading\"><strong>Assignment Task<\/strong><\/h3>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Problem-1: Number of paths in DAG<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/www.unilearno.com\/uploads\/2024\/06\/20240617100115AM-735024965-177763131.png\" alt=\"20240617100115AM-735024965-177763131.png\"\/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">Give a linear-time algorithm that takes as input a directed acyclic graph G (V, E) and two vertices s and t, and returns the number of simple paths from s to t in G. For example, the directed acyclic graph of Figure 22.8 contains exactly four simple paths from vertex p to vertex v: pov, poryv, posryv, and psryv. (Your algorithm needs only to count the simple paths, not list them.)<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Problem-2: Kruskal and Prim (Exam: Dec 2011, Dec 2012)<\/strong><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">2a. In which situations, you prefer Prim\u2019s algorithm over Kruskal\u2019s, and vice versa?<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">2b. Let us assume that the graph represents the inter-city bus network in the Rogaland district: the vertices represent the cities and the weights of the edges represent the distant between cities. Assuming that vertex \u201cf\u201d represents Stavanger, explain how you can force Kruskal\u2019s algorithm to make most connections through \u201cf\u201d.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">2c. Using a Depth-First-Search or otherwise, propose an algorithm for listing all the cycles in a directed graph. Find the running time of the algorithm.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Problem-3: Dijkstra&#8217;s algorithm for single-source shortest paths<\/strong><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Find the shortest paths between the vertex&nbsp;<em>A&nbsp;<\/em>and the rest, using Dijkstra\u2019s algorithm.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Problem-4: Maximum-Flow<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/www.unilearno.com\/uploads\/2024\/06\/20240617100115AM-1242623154-229373820.png\" alt=\"20240617100115AM-1242623154-229373820.png\"\/><\/figure>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Given the flow network G above, find a flow of maximum value from source\u00a0<strong><em>s\u00a0<\/em><\/strong>to sink\u00a0<strong><em>t<\/em><\/strong>, using the Ford-Fulkerson method.<\/li>\n\n\n\n<li>Suggest any improvement in this approach.<\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Assignment Task Problem-1: Number of paths in DAG Give a linear-time algorithm that takes as input a directed acyclic graph G (V, E) and two vertices s and t, and returns the number of simple paths from s to t in G. For example, the directed acyclic graph of Figure 22.8 contains exactly four simple [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-1226","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v27.9 - https:\/\/yoast.com\/product\/yoast-seo-wordpress\/ -->\n<title>\u00a0Inter-City Bus Networks with Kruskal&#039;s Algorithm Assignment - My Blog<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/britainwriters.com\/answers\/inter-city-bus-networks-with-kruskals-algorithm-assignment-2\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"\u00a0Inter-City Bus Networks with Kruskal&#039;s Algorithm Assignment - My Blog\" \/>\n<meta property=\"og:description\" content=\"Assignment Task Problem-1: Number of paths in DAG Give a linear-time algorithm that takes as input a directed acyclic graph G (V, E) and two vertices s and t, and returns the number of simple paths from s to t in G. For example, the directed acyclic graph of Figure 22.8 contains exactly four simple [&hellip;]\" \/>\n<meta property=\"og:url\" content=\"https:\/\/britainwriters.com\/answers\/inter-city-bus-networks-with-kruskals-algorithm-assignment-2\/\" \/>\n<meta property=\"og:site_name\" content=\"My Blog\" \/>\n<meta property=\"article:published_time\" content=\"2024-07-03T07:45:45+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-07-03T07:45:52+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/www.unilearno.com\/uploads\/2024\/06\/20240617100115AM-735024965-177763131.png\" \/>\n<meta name=\"author\" content=\"admin\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"admin\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"2 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\\\/\\\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\\\/\\\/britainwriters.com\\\/answers\\\/inter-city-bus-networks-with-kruskals-algorithm-assignment-2\\\/#article\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/britainwriters.com\\\/answers\\\/inter-city-bus-networks-with-kruskals-algorithm-assignment-2\\\/\"},\"author\":{\"name\":\"admin\",\"@id\":\"https:\\\/\\\/britainwriters.com\\\/answers\\\/#\\\/schema\\\/person\\\/c698e0f0b4a723b0d250ea199e68a6d3\"},\"headline\":\"\u00a0Inter-City Bus Networks with Kruskal&#8217;s Algorithm Assignment\",\"datePublished\":\"2024-07-03T07:45:45+00:00\",\"dateModified\":\"2024-07-03T07:45:52+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\\\/\\\/britainwriters.com\\\/answers\\\/inter-city-bus-networks-with-kruskals-algorithm-assignment-2\\\/\"},\"wordCount\":238,\"commentCount\":0,\"publisher\":{\"@id\":\"https:\\\/\\\/britainwriters.com\\\/answers\\\/#organization\"},\"image\":{\"@id\":\"https:\\\/\\\/britainwriters.com\\\/answers\\\/inter-city-bus-networks-with-kruskals-algorithm-assignment-2\\\/#primaryimage\"},\"thumbnailUrl\":\"https:\\\/\\\/www.unilearno.com\\\/uploads\\\/2024\\\/06\\\/20240617100115AM-735024965-177763131.png\",\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\\\/\\\/britainwriters.com\\\/answers\\\/inter-city-bus-networks-with-kruskals-algorithm-assignment-2\\\/#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\\\/\\\/britainwriters.com\\\/answers\\\/inter-city-bus-networks-with-kruskals-algorithm-assignment-2\\\/\",\"url\":\"https:\\\/\\\/britainwriters.com\\\/answers\\\/inter-city-bus-networks-with-kruskals-algorithm-assignment-2\\\/\",\"name\":\"\u00a0Inter-City Bus Networks with Kruskal's Algorithm Assignment - My Blog\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/britainwriters.com\\\/answers\\\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\\\/\\\/britainwriters.com\\\/answers\\\/inter-city-bus-networks-with-kruskals-algorithm-assignment-2\\\/#primaryimage\"},\"image\":{\"@id\":\"https:\\\/\\\/britainwriters.com\\\/answers\\\/inter-city-bus-networks-with-kruskals-algorithm-assignment-2\\\/#primaryimage\"},\"thumbnailUrl\":\"https:\\\/\\\/www.unilearno.com\\\/uploads\\\/2024\\\/06\\\/20240617100115AM-735024965-177763131.png\",\"datePublished\":\"2024-07-03T07:45:45+00:00\",\"dateModified\":\"2024-07-03T07:45:52+00:00\",\"breadcrumb\":{\"@id\":\"https:\\\/\\\/britainwriters.com\\\/answers\\\/inter-city-bus-networks-with-kruskals-algorithm-assignment-2\\\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\\\/\\\/britainwriters.com\\\/answers\\\/inter-city-bus-networks-with-kruskals-algorithm-assignment-2\\\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\\\/\\\/britainwriters.com\\\/answers\\\/inter-city-bus-networks-with-kruskals-algorithm-assignment-2\\\/#primaryimage\",\"url\":\"https:\\\/\\\/www.unilearno.com\\\/uploads\\\/2024\\\/06\\\/20240617100115AM-735024965-177763131.png\",\"contentUrl\":\"https:\\\/\\\/www.unilearno.com\\\/uploads\\\/2024\\\/06\\\/20240617100115AM-735024965-177763131.png\"},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\\\/\\\/britainwriters.com\\\/answers\\\/inter-city-bus-networks-with-kruskals-algorithm-assignment-2\\\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\\\/\\\/britainwriters.com\\\/answers\\\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"\u00a0Inter-City Bus Networks with Kruskal&#8217;s Algorithm Assignment\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\\\/\\\/britainwriters.com\\\/answers\\\/#website\",\"url\":\"https:\\\/\\\/britainwriters.com\\\/answers\\\/\",\"name\":\"My Blog\",\"description\":\"My WordPress Blog\",\"publisher\":{\"@id\":\"https:\\\/\\\/britainwriters.com\\\/answers\\\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\\\/\\\/britainwriters.com\\\/answers\\\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Organization\",\"@id\":\"https:\\\/\\\/britainwriters.com\\\/answers\\\/#organization\",\"name\":\"My Blog\",\"url\":\"https:\\\/\\\/britainwriters.com\\\/answers\\\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\\\/\\\/britainwriters.com\\\/answers\\\/#\\\/schema\\\/logo\\\/image\\\/\",\"url\":\"https:\\\/\\\/britainwriters.com\\\/answers\\\/wp-content\\\/uploads\\\/2023\\\/12\\\/bw-logo.png\",\"contentUrl\":\"https:\\\/\\\/britainwriters.com\\\/answers\\\/wp-content\\\/uploads\\\/2023\\\/12\\\/bw-logo.png\",\"width\":379,\"height\":81,\"caption\":\"My Blog\"},\"image\":{\"@id\":\"https:\\\/\\\/britainwriters.com\\\/answers\\\/#\\\/schema\\\/logo\\\/image\\\/\"}},{\"@type\":\"Person\",\"@id\":\"https:\\\/\\\/britainwriters.com\\\/answers\\\/#\\\/schema\\\/person\\\/c698e0f0b4a723b0d250ea199e68a6d3\",\"name\":\"admin\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/9c8389b9a2505b8a25de6eb6bd63d1b3bd34e49d8d91d40d9935e77bdb797c34?s=96&d=mm&r=g\",\"url\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/9c8389b9a2505b8a25de6eb6bd63d1b3bd34e49d8d91d40d9935e77bdb797c34?s=96&d=mm&r=g\",\"contentUrl\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/9c8389b9a2505b8a25de6eb6bd63d1b3bd34e49d8d91d40d9935e77bdb797c34?s=96&d=mm&r=g\",\"caption\":\"admin\"},\"sameAs\":[\"https:\\\/\\\/britainwriters.com\\\/website\"],\"url\":\"https:\\\/\\\/britainwriters.com\\\/answers\\\/author\\\/admin\\\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"\u00a0Inter-City Bus Networks with Kruskal's Algorithm Assignment - My Blog","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/britainwriters.com\/answers\/inter-city-bus-networks-with-kruskals-algorithm-assignment-2\/","og_locale":"en_US","og_type":"article","og_title":"\u00a0Inter-City Bus Networks with Kruskal's Algorithm Assignment - My Blog","og_description":"Assignment Task Problem-1: Number of paths in DAG Give a linear-time algorithm that takes as input a directed acyclic graph G (V, E) and two vertices s and t, and returns the number of simple paths from s to t in G. For example, the directed acyclic graph of Figure 22.8 contains exactly four simple [&hellip;]","og_url":"https:\/\/britainwriters.com\/answers\/inter-city-bus-networks-with-kruskals-algorithm-assignment-2\/","og_site_name":"My Blog","article_published_time":"2024-07-03T07:45:45+00:00","article_modified_time":"2024-07-03T07:45:52+00:00","og_image":[{"url":"https:\/\/www.unilearno.com\/uploads\/2024\/06\/20240617100115AM-735024965-177763131.png","type":"","width":"","height":""}],"author":"admin","twitter_card":"summary_large_image","twitter_misc":{"Written by":"admin","Est. reading time":"2 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/britainwriters.com\/answers\/inter-city-bus-networks-with-kruskals-algorithm-assignment-2\/#article","isPartOf":{"@id":"https:\/\/britainwriters.com\/answers\/inter-city-bus-networks-with-kruskals-algorithm-assignment-2\/"},"author":{"name":"admin","@id":"https:\/\/britainwriters.com\/answers\/#\/schema\/person\/c698e0f0b4a723b0d250ea199e68a6d3"},"headline":"\u00a0Inter-City Bus Networks with Kruskal&#8217;s Algorithm Assignment","datePublished":"2024-07-03T07:45:45+00:00","dateModified":"2024-07-03T07:45:52+00:00","mainEntityOfPage":{"@id":"https:\/\/britainwriters.com\/answers\/inter-city-bus-networks-with-kruskals-algorithm-assignment-2\/"},"wordCount":238,"commentCount":0,"publisher":{"@id":"https:\/\/britainwriters.com\/answers\/#organization"},"image":{"@id":"https:\/\/britainwriters.com\/answers\/inter-city-bus-networks-with-kruskals-algorithm-assignment-2\/#primaryimage"},"thumbnailUrl":"https:\/\/www.unilearno.com\/uploads\/2024\/06\/20240617100115AM-735024965-177763131.png","inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/britainwriters.com\/answers\/inter-city-bus-networks-with-kruskals-algorithm-assignment-2\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/britainwriters.com\/answers\/inter-city-bus-networks-with-kruskals-algorithm-assignment-2\/","url":"https:\/\/britainwriters.com\/answers\/inter-city-bus-networks-with-kruskals-algorithm-assignment-2\/","name":"\u00a0Inter-City Bus Networks with Kruskal's Algorithm Assignment - My Blog","isPartOf":{"@id":"https:\/\/britainwriters.com\/answers\/#website"},"primaryImageOfPage":{"@id":"https:\/\/britainwriters.com\/answers\/inter-city-bus-networks-with-kruskals-algorithm-assignment-2\/#primaryimage"},"image":{"@id":"https:\/\/britainwriters.com\/answers\/inter-city-bus-networks-with-kruskals-algorithm-assignment-2\/#primaryimage"},"thumbnailUrl":"https:\/\/www.unilearno.com\/uploads\/2024\/06\/20240617100115AM-735024965-177763131.png","datePublished":"2024-07-03T07:45:45+00:00","dateModified":"2024-07-03T07:45:52+00:00","breadcrumb":{"@id":"https:\/\/britainwriters.com\/answers\/inter-city-bus-networks-with-kruskals-algorithm-assignment-2\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/britainwriters.com\/answers\/inter-city-bus-networks-with-kruskals-algorithm-assignment-2\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/britainwriters.com\/answers\/inter-city-bus-networks-with-kruskals-algorithm-assignment-2\/#primaryimage","url":"https:\/\/www.unilearno.com\/uploads\/2024\/06\/20240617100115AM-735024965-177763131.png","contentUrl":"https:\/\/www.unilearno.com\/uploads\/2024\/06\/20240617100115AM-735024965-177763131.png"},{"@type":"BreadcrumbList","@id":"https:\/\/britainwriters.com\/answers\/inter-city-bus-networks-with-kruskals-algorithm-assignment-2\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/britainwriters.com\/answers\/"},{"@type":"ListItem","position":2,"name":"\u00a0Inter-City Bus Networks with Kruskal&#8217;s Algorithm Assignment"}]},{"@type":"WebSite","@id":"https:\/\/britainwriters.com\/answers\/#website","url":"https:\/\/britainwriters.com\/answers\/","name":"My Blog","description":"My WordPress Blog","publisher":{"@id":"https:\/\/britainwriters.com\/answers\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/britainwriters.com\/answers\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"https:\/\/britainwriters.com\/answers\/#organization","name":"My Blog","url":"https:\/\/britainwriters.com\/answers\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/britainwriters.com\/answers\/#\/schema\/logo\/image\/","url":"https:\/\/britainwriters.com\/answers\/wp-content\/uploads\/2023\/12\/bw-logo.png","contentUrl":"https:\/\/britainwriters.com\/answers\/wp-content\/uploads\/2023\/12\/bw-logo.png","width":379,"height":81,"caption":"My Blog"},"image":{"@id":"https:\/\/britainwriters.com\/answers\/#\/schema\/logo\/image\/"}},{"@type":"Person","@id":"https:\/\/britainwriters.com\/answers\/#\/schema\/person\/c698e0f0b4a723b0d250ea199e68a6d3","name":"admin","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/secure.gravatar.com\/avatar\/9c8389b9a2505b8a25de6eb6bd63d1b3bd34e49d8d91d40d9935e77bdb797c34?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/9c8389b9a2505b8a25de6eb6bd63d1b3bd34e49d8d91d40d9935e77bdb797c34?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/9c8389b9a2505b8a25de6eb6bd63d1b3bd34e49d8d91d40d9935e77bdb797c34?s=96&d=mm&r=g","caption":"admin"},"sameAs":["https:\/\/britainwriters.com\/website"],"url":"https:\/\/britainwriters.com\/answers\/author\/admin\/"}]}},"_links":{"self":[{"href":"https:\/\/britainwriters.com\/answers\/wp-json\/wp\/v2\/posts\/1226","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/britainwriters.com\/answers\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/britainwriters.com\/answers\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/britainwriters.com\/answers\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/britainwriters.com\/answers\/wp-json\/wp\/v2\/comments?post=1226"}],"version-history":[{"count":1,"href":"https:\/\/britainwriters.com\/answers\/wp-json\/wp\/v2\/posts\/1226\/revisions"}],"predecessor-version":[{"id":1227,"href":"https:\/\/britainwriters.com\/answers\/wp-json\/wp\/v2\/posts\/1226\/revisions\/1227"}],"wp:attachment":[{"href":"https:\/\/britainwriters.com\/answers\/wp-json\/wp\/v2\/media?parent=1226"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/britainwriters.com\/answers\/wp-json\/wp\/v2\/categories?post=1226"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/britainwriters.com\/answers\/wp-json\/wp\/v2\/tags?post=1226"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}