Repeatedly update the distance matrix to ultimately find the shortest distances for all pairs.<\/li>\n<\/ol>\nProblem Description<\/h2>\n
Now let’s examine the problem. Suppose we are given a graph as follows.<\/p>\n
\n Nodes: 0, 1, 2\n Edges: \n 0 -> 1 (distance 3)\n 0 -> 2 (distance 8)\n 1 -> 2 (distance 2)\n <\/pre>\nInput<\/h3>\n
The number of nodes in the graph and the distance information for each edge will be provided. Input is received in the following format:<\/p>\n
\n 3\n 0 1 3\n 0 2 8\n 1 2 2\n <\/pre>\nOutput<\/h3>\n
The shortest distance matrix between each pair of nodes will be output.<\/p>\n
Algorithm Implementation<\/h2>\n
Now let’s implement the Floyd-Warshall algorithm in Python. Below is the code for the algorithm:<\/p>\n
\ndef floyd_warshall(num_vertices, edges):\n # Initialize distances to infinity\n dist = [[float('inf')] * num_vertices for _ in range(num_vertices)]\n \n # Distance to self is 0\n for i in range(num_vertices):\n dist[i][i] = 0\n \n # Set initial distances based on given edges\n for u, v, w in edges:\n dist[u][v] = min(dist[u][v], w) # Set minimum distance if multiple paths exist\n \n # Execute the Floyd-Warshall algorithm\n for k in range(num_vertices):\n for i in range(num_vertices):\n for j in range(num_vertices):\n if dist[i][j] > dist[i][k] + dist[k][j]:\n dist[i][j] = dist[i][k] + dist[k][j]\n \n return dist\n\n# Take input\nnum_vertices = int(input(\"Enter the number of nodes: \"))\nedges = []\n\nfor _ in range(int(input(\"Enter the number of edges: \"))):\n u, v, w = map(int, input(\"Enter the edge (u, v, distance): \").split())\n edges.append((u, v, w))\n\n# Execute the algorithm\nshortest_paths = floyd_warshall(num_vertices, edges)\n\n# Output results\nfor row in shortest_paths:\n print(row)<\/code>\n <\/pre>\nCode Explanation<\/h2>\n
Now let’s look at the code step by step.<\/p>\n
Distance Initialization<\/h3>\n
We create the distance matrix based on the number of nodes in the graph. Initially, all distances are set to infinity, and the distance to itself is set to 0.<\/p>\n
Edge Input Processing<\/h3>\n
We read the given edge information and set the initial distances between each pair of nodes. If multiple edges exist, we choose the minimum distance.<\/p>\n
Main Algorithm Logic<\/h3>\n
We use three nested loops to compute the shortest paths between all pairs of nodes. This loop uses k as an intermediate vertex to update the shortest path from i to j.<\/p>\n
Execution Example<\/h2>\n
Let’s execute the algorithm as follows:<\/p>\n
\n Enter the number of nodes: 3\n Enter the number of edges: 3\n Enter the edge (u, v, distance): 0 1 3\n Enter the edge (u, v, distance): 0 2 8\n Enter the edge (u, v, distance): 1 2 2\n <\/pre>\nThe output when executing the above example would be as follows:<\/p>\n
\n [0, 3, 5]\n [inf, 0, 2]\n [inf, inf, 0]\n <\/pre>\nConclusion<\/h2>\n
The Floyd-Warshall algorithm is a very useful algorithm for finding the shortest paths between all pairs. Through this algorithm, we can efficiently find the shortest paths even in complex structures of graphs. It’s important to practice applying this algorithm to solve various problems. In the next coding test, try to solve various problems using this algorithm!<\/p>\n
<\/body><\/p>\n","protected":false},"excerpt":{"rendered":"
Hello! In this tutorial, we will delve deep into the Floyd-Warshall algorithm. This algorithm is very useful for solving the problem of finding the shortest paths between all pairs in a given graph. We will explain this algorithm through examples, and discuss various modifications including optimizations. What is the Floyd-Warshall Algorithm? The Floyd-Warshall algorithm is … \ub354 \ubcf4\uae30 “python coding test course, Floyd-Warshall”<\/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":[145],"tags":[],"class_list":["post-33818","post","type-post","status-publish","format-standard","hentry","category-python-coding-test"],"yoast_head":"\npython 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\/33818\/\" \/>\n<meta property=\"og:locale\" content=\"ko_KR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"python coding test course, Floyd-Warshall - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"og:description\" content=\"Hello! In this tutorial, we will delve deep into the Floyd-Warshall algorithm. This algorithm is very useful for solving the problem of finding the shortest paths between all pairs in a given graph. We will explain this algorithm through examples, and discuss various modifications including optimizations. What is the Floyd-Warshall Algorithm? The Floyd-Warshall algorithm is … \ub354 \ubcf4\uae30 "python coding test course, Floyd-Warshall"\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/33818\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:20:46+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T11:46:32+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\/33818\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33818\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"python coding test course, Floyd-Warshall\",\"datePublished\":\"2024-11-01T09:20:46+00:00\",\"dateModified\":\"2024-11-01T11:46:32+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33818\/\"},\"wordCount\":374,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"Python Coding Test\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/33818\/\",\"url\":\"https:\/\/atmokpo.com\/w\/33818\/\",\"name\":\"python coding test course, Floyd-Warshall - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#website\"},\"datePublished\":\"2024-11-01T09:20:46+00:00\",\"dateModified\":\"2024-11-01T11:46:32+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33818\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/33818\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/33818\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"python 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":"python 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\/33818\/","og_locale":"ko_KR","og_type":"article","og_title":"python coding test course, Floyd-Warshall - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","og_description":"Hello! In this tutorial, we will delve deep into the Floyd-Warshall algorithm. This algorithm is very useful for solving the problem of finding the shortest paths between all pairs in a given graph. We will explain this algorithm through examples, and discuss various modifications including optimizations. What is the Floyd-Warshall Algorithm? The Floyd-Warshall algorithm is … \ub354 \ubcf4\uae30 \"python coding test course, Floyd-Warshall\"","og_url":"https:\/\/atmokpo.com\/w\/33818\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:20:46+00:00","article_modified_time":"2024-11-01T11:46:32+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\/33818\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/33818\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"python coding test course, Floyd-Warshall","datePublished":"2024-11-01T09:20:46+00:00","dateModified":"2024-11-01T11:46:32+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/33818\/"},"wordCount":374,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["Python Coding Test"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/33818\/","url":"https:\/\/atmokpo.com\/w\/33818\/","name":"python coding test course, Floyd-Warshall - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/#website"},"datePublished":"2024-11-01T09:20:46+00:00","dateModified":"2024-11-01T11:46:32+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/33818\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/33818\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/33818\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"python 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\/33818","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=33818"}],"version-history":[{"count":1,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/33818\/revisions"}],"predecessor-version":[{"id":33819,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/33818\/revisions\/33819"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=33818"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=33818"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=33818"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}