{"id":34908,"date":"2024-11-01T09:33:28","date_gmt":"2024-11-01T09:33:28","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=34908"},"modified":"2024-11-01T11:26:00","modified_gmt":"2024-11-01T11:26:00","slug":"swift-coding-test-course-floyd-warshall","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/34908\/","title":{"rendered":"Swift Coding Test Course, Floyd-Warshall"},"content":{"rendered":"<article>\n<header>\n<p>Let&#8217;s learn about the Floyd-Warshall algorithm, which often appears in coding tests, and solve related algorithm problems. This article will detail the overview, working principle, and example problem-solving process of the Floyd-Warshall algorithm.<\/p>\n<\/header>\n<section>\n<h2>1. Overview of the Floyd-Warshall Algorithm<\/h2>\n<p>The Floyd-Warshall algorithm is an algorithm used to find the shortest paths between all pairs of vertices in a graph. This algorithm is based on dynamic programming and updates the shortest paths by considering paths that pass through vertex k at each step. The time complexity of the Floyd-Warshall algorithm is O(V\u00b3), where V represents the number of vertices.<\/p>\n<h3>1.1. Significance of the Algorithm<\/h3>\n<p>The Floyd-Warshall algorithm exhibits excellent efficiency in that it can identify the shortest paths between all pairs of vertices through a single process, not just finding the shortest path from a single starting point.<\/p>\n<h3>1.2. Applications<\/h3>\n<p>This algorithm is applied in various fields including calculating the shortest paths between all nodes in a network, optimizing road networks, and computing movement paths in games.<\/p>\n<\/section>\n<section>\n<h2>2. Working Principle of the Algorithm<\/h2>\n<p>The Floyd-Warshall algorithm operates in the following manner:<\/p>\n<ol>\n<li>Initialize the shortest paths for all edges of the graph. The distance between two directly connected vertices is set to the weight of the edge, while the remaining pairs are set to infinity.<\/li>\n<li>For each vertex k, update the shortest paths for all combinations of vertices i and j as follows: <strong>dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])<\/strong><\/li>\n<li>Repeat this process for all pairs of vertices.<\/li>\n<\/ol>\n<p>This algorithm allows us to find the shortest paths when there are paths that pass through vertex k.<\/p>\n<\/section>\n<section>\n<h2>3. Example Problem<\/h2>\n<h3>Problem Description<\/h3>\n<p>Here is a problem that can be solved using the Floyd-Warshall algorithm:<\/p>\n<blockquote>\n<p>Given a directed graph consisting of N vertices and M edges, write a program to find the shortest distance between each pair of vertices. The weights of the edges are given as positive integers, and if there is no edge between two vertices, it should be set to infinity.<\/p>\n<\/blockquote>\n<h3>Problem Input<\/h3>\n<p>The first line contains the number of vertices N (1 \u2264 N \u2264 100) and the number of edges M (1 \u2264 M \u2264 100,000). The next M lines provide the starting vertex, ending vertex, and weight of each edge. If there are multiple edges between two vertices, only the edge with the smallest weight should be considered.<\/p>\n<h3>Problem Output<\/h3>\n<p>Output the shortest distance between each pair of vertices. If the shortest distance does not exist, output INF.<\/p>\n<h3>Example<\/h3>\n<p>Input:<\/p>\n<pre>\n        4 7\n        1 2 1\n        1 3 3\n        2 3 1\n        2 4 2\n        3 4 1\n        4 1 2\n        4 2 3\n        <\/pre>\n<p>Output:<\/p>\n<pre>\n        0 1 2 3\n        INF 0 1 2\n        INF INF 0 1\n        2 1 2 0\n        <\/pre>\n<\/section>\n<section>\n<h2>4. Problem Solving Process<\/h2>\n<p>To solve the problem, we will implement the Floyd-Warshall algorithm. Below is the step-by-step process of problem-solving.<\/p>\n<h3>4.1. Initial Setup<\/h3>\n<p>First, set up the initial distance array using N vertices and M edges. The weights between directly connected vertices are set to the given values, and the distances for unconnected vertices are set to infinity.<\/p>\n<h3>4.2. Initialize Distance Array<\/h3>\n<pre>\n        var N = 4\n        var M = 7\n        var dist = [[Int]](repeating: [Int](repeating: Int.max, count: N + 1), count: N + 1)\n        \n        for i in 1...N {\n            dist[i][i] = 0\n        }\n        <\/pre>\n<p>This code initializes the distance array dist to infinity and sets the distance to itself as 0.<\/p>\n<h3>4.3. Input Edge Information<\/h3>\n<pre>\n        dist[1][2] = 1\n        dist[1][3] = 3\n        dist[2][3] = 1\n        dist[2][4] = 2\n        dist[3][4] = 1\n        dist[4][1] = 2\n        dist[4][2] = 3\n        <\/pre>\n<p>Now, set the weights between directly connected vertices using the edge information. If there are multiple edges, update it to the minimum weight.<\/p>\n<h3>4.4. Apply the Floyd-Warshall Algorithm<\/h3>\n<pre>\n        for k in 1...N {\n            for i in 1...N {\n                for j in 1...N {\n                    if dist[i][j] &gt; dist[i][k] + dist[k][j] {\n                        dist[i][j] = dist[i][k] + dist[k][j]\n                    }\n                }\n            }\n        }\n        <\/pre>\n<p>Here, k acts as an intermediate vertex, updating the shortest path from i to j.<\/p>\n<h3>4.5. Output Results<\/h3>\n<pre>\n        for i in 1...N {\n            for j in 1...N {\n                if dist[i][j] == Int.max {\n                    print(\"INF\", terminator: \" \")\n                } else {\n                    print(dist[i][j], terminator: \" \")\n                }\n            }\n            print(\"\")\n        }\n        <\/pre>\n<p>Finally, output the distance array to check the shortest distances between each pair of vertices.<\/p>\n<\/section>\n<section>\n<h2>5. Conclusion<\/h2>\n<p>In this lecture, we learned the concepts and operating principles of the Floyd-Warshall algorithm and examined the process of solving actual problems. This algorithm is a powerful tool for efficiently finding the shortest paths between all pairs of vertices. It is important to solve various examples to enhance your understanding of the algorithm. You should also practice solving algorithm problems in Swift to improve your skills!<\/p>\n<\/section>\n<\/article>\n","protected":false},"excerpt":{"rendered":"<p>Let&#8217;s learn about the Floyd-Warshall algorithm, which often appears in coding tests, and solve related algorithm problems. This article will detail the overview, working principle, and example problem-solving process of the Floyd-Warshall algorithm. 1. Overview of the Floyd-Warshall Algorithm The Floyd-Warshall algorithm is an algorithm used to find the shortest paths between all pairs of &hellip; <a href=\"https:\/\/atmokpo.com\/w\/34908\/\" class=\"more-link\">\ub354 \ubcf4\uae30<span class=\"screen-reader-text\"> &#8220;Swift Coding Test Course, Floyd-Warshall&#8221;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[129],"tags":[],"class_list":["post-34908","post","type-post","status-publish","format-standard","hentry","category-swift-coding-test"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v26.2 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>Swift Coding Test Course, Floyd-Warshall - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8<\/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:\/\/atmokpo.com\/w\/34908\/\" \/>\n<meta property=\"og:locale\" content=\"ko_KR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Swift Coding Test Course, Floyd-Warshall - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"og:description\" content=\"Let&#8217;s learn about the Floyd-Warshall algorithm, which often appears in coding tests, and solve related algorithm problems. This article will detail the overview, working principle, and example problem-solving process of the Floyd-Warshall algorithm. 1. Overview of the Floyd-Warshall Algorithm The Floyd-Warshall algorithm is an algorithm used to find the shortest paths between all pairs of &hellip; \ub354 \ubcf4\uae30 &quot;Swift Coding Test Course, Floyd-Warshall&quot;\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/34908\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:33:28+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T11:26:00+00:00\" \/>\n<meta name=\"author\" content=\"root\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@bebubo4\" \/>\n<meta name=\"twitter:site\" content=\"@bebubo4\" \/>\n<meta name=\"twitter:label1\" content=\"\uae00\uc4f4\uc774\" \/>\n\t<meta name=\"twitter:data1\" content=\"root\" \/>\n\t<meta name=\"twitter:label2\" content=\"\uc608\uc0c1 \ub418\ub294 \ud310\ub3c5 \uc2dc\uac04\" \/>\n\t<meta name=\"twitter:data2\" content=\"4\ubd84\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/atmokpo.com\/w\/34908\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34908\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"Swift Coding Test Course, Floyd-Warshall\",\"datePublished\":\"2024-11-01T09:33:28+00:00\",\"dateModified\":\"2024-11-01T11:26:00+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34908\/\"},\"wordCount\":618,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"Swift Coding Test\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/34908\/\",\"url\":\"https:\/\/atmokpo.com\/w\/34908\/\",\"name\":\"Swift Coding Test Course, Floyd-Warshall - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#website\"},\"datePublished\":\"2024-11-01T09:33:28+00:00\",\"dateModified\":\"2024-11-01T11:26:00+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34908\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/34908\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/34908\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Swift Coding Test Course, Floyd-Warshall\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/atmokpo.com\/w\/#website\",\"url\":\"https:\/\/atmokpo.com\/w\/\",\"name\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"description\":\"\",\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/atmokpo.com\/w\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"ko-KR\"},{\"@type\":\"Organization\",\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\",\"name\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"url\":\"https:\/\/atmokpo.com\/w\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"ko-KR\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png\",\"contentUrl\":\"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png\",\"width\":400,\"height\":400,\"caption\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\"},\"image\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/\"},\"sameAs\":[\"https:\/\/x.com\/bebubo4\"]},{\"@type\":\"Person\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\",\"name\":\"root\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"ko-KR\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g\",\"caption\":\"root\"},\"sameAs\":[\"http:\/\/atmokpo.com\/w\"],\"url\":\"https:\/\/atmokpo.com\/w\/author\/root\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Swift Coding Test Course, Floyd-Warshall - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","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:\/\/atmokpo.com\/w\/34908\/","og_locale":"ko_KR","og_type":"article","og_title":"Swift Coding Test Course, Floyd-Warshall - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","og_description":"Let&#8217;s learn about the Floyd-Warshall algorithm, which often appears in coding tests, and solve related algorithm problems. This article will detail the overview, working principle, and example problem-solving process of the Floyd-Warshall algorithm. 1. Overview of the Floyd-Warshall Algorithm The Floyd-Warshall algorithm is an algorithm used to find the shortest paths between all pairs of &hellip; \ub354 \ubcf4\uae30 \"Swift Coding Test Course, Floyd-Warshall\"","og_url":"https:\/\/atmokpo.com\/w\/34908\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:33:28+00:00","article_modified_time":"2024-11-01T11:26:00+00:00","author":"root","twitter_card":"summary_large_image","twitter_creator":"@bebubo4","twitter_site":"@bebubo4","twitter_misc":{"\uae00\uc4f4\uc774":"root","\uc608\uc0c1 \ub418\ub294 \ud310\ub3c5 \uc2dc\uac04":"4\ubd84"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/atmokpo.com\/w\/34908\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/34908\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"Swift Coding Test Course, Floyd-Warshall","datePublished":"2024-11-01T09:33:28+00:00","dateModified":"2024-11-01T11:26:00+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/34908\/"},"wordCount":618,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["Swift Coding Test"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/34908\/","url":"https:\/\/atmokpo.com\/w\/34908\/","name":"Swift Coding Test Course, Floyd-Warshall - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/#website"},"datePublished":"2024-11-01T09:33:28+00:00","dateModified":"2024-11-01T11:26:00+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/34908\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/34908\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/34908\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"Swift Coding Test Course, Floyd-Warshall"}]},{"@type":"WebSite","@id":"https:\/\/atmokpo.com\/w\/#website","url":"https:\/\/atmokpo.com\/w\/","name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","description":"","publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/atmokpo.com\/w\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"ko-KR"},{"@type":"Organization","@id":"https:\/\/atmokpo.com\/w\/#organization","name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","url":"https:\/\/atmokpo.com\/w\/","logo":{"@type":"ImageObject","inLanguage":"ko-KR","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/","url":"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png","contentUrl":"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png","width":400,"height":400,"caption":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8"},"image":{"@id":"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/x.com\/bebubo4"]},{"@type":"Person","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7","name":"root","image":{"@type":"ImageObject","inLanguage":"ko-KR","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g","caption":"root"},"sameAs":["http:\/\/atmokpo.com\/w"],"url":"https:\/\/atmokpo.com\/w\/author\/root\/"}]}},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34908","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/comments?post=34908"}],"version-history":[{"count":1,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34908\/revisions"}],"predecessor-version":[{"id":34909,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34908\/revisions\/34909"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=34908"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=34908"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=34908"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}