{"id":34394,"date":"2024-11-01T09:27:37","date_gmt":"2024-11-01T09:27:37","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=34394"},"modified":"2024-11-01T11:41:26","modified_gmt":"2024-11-01T11:41:26","slug":"javascript-coding-test-course-floyd-warshall","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/34394\/","title":{"rendered":"Javascript Coding Test Course, Floyd-Warshall"},"content":{"rendered":"<article>\n<header>\n<p>Author: [Your Name]<\/p>\n<p>Written on: [Date]<\/p>\n<\/header>\n<section>\n<h2>Table of Contents<\/h2>\n<ol>\n<li><a href=\"#intro\">1. Introduction<\/a><\/li>\n<li><a href=\"#problem\">2. Problem Description<\/a><\/li>\n<li><a href=\"#floyd\">3. Understanding the Floyd-Warshall Algorithm<\/a><\/li>\n<li><a href=\"#implementation\">4. JavaScript Implementation<\/a><\/li>\n<li><a href=\"#complexity\">5. Time Complexity<\/a><\/li>\n<li><a href=\"#conclusion\">6. Conclusion<\/a><\/li>\n<\/ol>\n<\/section>\n<section id=\"intro\">\n<h2>1. Introduction<\/h2>\n<p>Algorithm problems are frequently presented in coding tests, and the ability to understand and implement various algorithms is important. This course will cover the Floyd-Warshall algorithm and teach how to implement it in JavaScript. The Floyd-Warshall algorithm is useful for finding the shortest paths between all pairs of vertices in a graph, particularly suited for large graphs.<\/p>\n<\/section>\n<section id=\"problem\">\n<h2>2. Problem Description<\/h2>\n<p>Problem: Write an algorithm to find the shortest paths between all vertices in a given directed graph. The graph consists of edges with weights. If there is no path between two vertices, the value of the shortest path is handled as infinity.<\/p>\n<pre><code>\nInput:\n- Number of vertices N (1 \u2264 N \u2264 100)\n- Number of edges M (1 \u2264 M \u2264 10000)\n- Edge information of M edges (A, B, C): weight C from A to B\n\nOutput:\n- Print an N x N matrix representing the lengths of the shortest paths between the destination vertices.\n        <\/code><\/pre>\n<\/section>\n<section id=\"floyd\">\n<h2>3. Understanding the Floyd-Warshall Algorithm<\/h2>\n<p>The Floyd-Warshall algorithm uses dynamic programming techniques to compute the shortest paths between all pairs. The algorithm includes the following steps:<\/p>\n<ol>\n<li>Initialize distance values between all pairs of vertices (i, j). Set weights for directly connected vertices and infinity (INFINITY) for non-connected ones.<\/li>\n<li>Set each vertex as an intermediate vertex and check the shortest path from i to j. Using k as the intermediate vertex, check if the path i -> k -> j is shorter than the direct path i -> j.<\/li>\n<li>Repeat this process for all vertices.<\/li>\n<\/ol>\n<p>By doing this, we can ultimately find the shortest paths between all pairs of vertices.<\/p>\n<pre><code>\nfunction floydWarshall(graph) {\n  const dist = JSON.parse(JSON.stringify(graph)); \/\/ Copy the graph to initialize the distance matrix\n\n  const n = graph.length; \/\/ Number of vertices\n  for (let k = 0; k < n; k++) {\n    for (let i = 0; i < n; i++) {\n      for (let j = 0; j < n; j++) {\n        if (dist[i][j] > dist[i][k] + dist[k][j]) {\n          dist[i][j] = dist[i][k] + dist[k][j];\n        }\n      }\n    }\n  }\n  return dist;\n}\n        <\/code><\/pre>\n<\/section>\n<section id=\"implementation\">\n<h2>4. JavaScript Implementation<\/h2>\n<p>Now let&#8217;s implement the Floyd-Warshall algorithm in JavaScript. First, we will handle input, initialize the graph, and then write a function to calculate the shortest paths:<\/p>\n<pre><code>\nfunction initializeGraph(N, edges) {\n  const graph = Array.from({ length: N }, () => Array(N).fill(Infinity));\n  for (let i = 0; i < N; i++) {\n    graph[i][i] = 0; \/\/ The case for going to itself is 0\n  }\n\n  edges.forEach(([A, B, C]) => {\n    graph[A][B] = Math.min(graph[A][B], C); \/\/ Update to the minimum weight if there are multiple edges\n  });\n\n  return graph;\n}\n\n\/\/ Main function to solve the problem\nfunction solve(N, M, edges) {\n  const graph = initializeGraph(N, edges);\n  const shortestPaths = floydWarshall(graph);\n\n  console.log(\"Shortest Path Matrix:\");\n  shortestPaths.forEach(row => console.log(row.join(\" \")));\n}\n        <\/code><\/pre>\n<\/section>\n<section id=\"complexity\">\n<h2>5. Time Complexity<\/h2>\n<p>The time complexity of the Floyd-Warshall algorithm is O(N^3). This is because a triple loop is used to check each pair of vertices when N is the number of vertices. Therefore, it can be efficiently used when the number of vertices is reasonably small (100 or less), but for graphs with hundreds of vertices, other algorithms should be considered.<\/p>\n<\/section>\n<section id=\"conclusion\">\n<h2>6. Conclusion<\/h2>\n<p>In this course, we explored the theory of the Floyd-Warshall algorithm and how to implement it in JavaScript. By understanding the algorithm and practicing the code implementation, we can enhance our problem-solving skills in coding tests. Next time, we will cover even more diverse algorithms.<\/p>\n<\/section>\n<\/article>\n","protected":false},"excerpt":{"rendered":"<p>Author: [Your Name] Written on: [Date] Table of Contents 1. Introduction 2. Problem Description 3. Understanding the Floyd-Warshall Algorithm 4. JavaScript Implementation 5. Time Complexity 6. Conclusion 1. Introduction Algorithm problems are frequently presented in coding tests, and the ability to understand and implement various algorithms is important. This course will cover the Floyd-Warshall algorithm &hellip; <a href=\"https:\/\/atmokpo.com\/w\/34394\/\" class=\"more-link\">\ub354 \ubcf4\uae30<span class=\"screen-reader-text\"> &#8220;Javascript 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":[141],"tags":[],"class_list":["post-34394","post","type-post","status-publish","format-standard","hentry","category-javascript-coding-test"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v26.2 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>Javascript 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\/34394\/\" \/>\n<meta property=\"og:locale\" content=\"ko_KR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Javascript Coding Test Course, Floyd-Warshall - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"og:description\" content=\"Author: [Your Name] Written on: [Date] Table of Contents 1. Introduction 2. Problem Description 3. Understanding the Floyd-Warshall Algorithm 4. JavaScript Implementation 5. Time Complexity 6. Conclusion 1. Introduction Algorithm problems are frequently presented in coding tests, and the ability to understand and implement various algorithms is important. This course will cover the Floyd-Warshall algorithm &hellip; \ub354 \ubcf4\uae30 &quot;Javascript Coding Test Course, Floyd-Warshall&quot;\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/34394\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:27:37+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T11:41:26+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=\"3\ubd84\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/atmokpo.com\/w\/34394\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34394\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"Javascript Coding Test Course, Floyd-Warshall\",\"datePublished\":\"2024-11-01T09:27:37+00:00\",\"dateModified\":\"2024-11-01T11:41:26+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34394\/\"},\"wordCount\":372,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"Javascript Coding Test\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/34394\/\",\"url\":\"https:\/\/atmokpo.com\/w\/34394\/\",\"name\":\"Javascript Coding Test Course, Floyd-Warshall - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#website\"},\"datePublished\":\"2024-11-01T09:27:37+00:00\",\"dateModified\":\"2024-11-01T11:41:26+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34394\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/34394\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/34394\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Javascript 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":"Javascript 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\/34394\/","og_locale":"ko_KR","og_type":"article","og_title":"Javascript Coding Test Course, Floyd-Warshall - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","og_description":"Author: [Your Name] Written on: [Date] Table of Contents 1. Introduction 2. Problem Description 3. Understanding the Floyd-Warshall Algorithm 4. JavaScript Implementation 5. Time Complexity 6. Conclusion 1. Introduction Algorithm problems are frequently presented in coding tests, and the ability to understand and implement various algorithms is important. This course will cover the Floyd-Warshall algorithm &hellip; \ub354 \ubcf4\uae30 \"Javascript Coding Test Course, Floyd-Warshall\"","og_url":"https:\/\/atmokpo.com\/w\/34394\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:27:37+00:00","article_modified_time":"2024-11-01T11:41:26+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":"3\ubd84"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/atmokpo.com\/w\/34394\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/34394\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"Javascript Coding Test Course, Floyd-Warshall","datePublished":"2024-11-01T09:27:37+00:00","dateModified":"2024-11-01T11:41:26+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/34394\/"},"wordCount":372,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["Javascript Coding Test"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/34394\/","url":"https:\/\/atmokpo.com\/w\/34394\/","name":"Javascript Coding Test Course, Floyd-Warshall - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/#website"},"datePublished":"2024-11-01T09:27:37+00:00","dateModified":"2024-11-01T11:41:26+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/34394\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/34394\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/34394\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"Javascript 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\/34394","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=34394"}],"version-history":[{"count":1,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34394\/revisions"}],"predecessor-version":[{"id":34395,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34394\/revisions\/34395"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=34394"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=34394"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=34394"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}