\n
Problem Description<\/h2>\n
\n Given a graph, implement an algorithm to find the shortest path from one vertex to another.
\n The given graph is a directed graph, and each edge has a weight.
\n Vertices are represented by integers from 0 to N-1, and if there is an edge between two vertices, we know its weight.<\/p>\n
Input Format:<\/strong><\/p>\n\n- The first line contains the number of vertices N (1 \u2264 N \u2264 1000).<\/li>\n
- The second line contains the number of edges M (1 \u2264 M \u2264 10000).<\/li>\n
- From the third line to the Mth line, the information of each edge is given.
\n This is in the form of “A B C”, meaning there is an edge from A to B with weight C.
\n (1 \u2264 A, B \u2264 N, 1 \u2264 C \u2264 1000)<\/li>\n - The last line contains the start point S (1 \u2264 S \u2264 N) and the end point E.<\/li>\n<\/ul>\n<\/div>\n
\n
Solution Process<\/h2>\n
\n The Dijkstra algorithm is an algorithm for finding the shortest path from one vertex to another in a graph.
\n This algorithm works correctly only when there are no negative weights, so it is important to check whether the weights are non-negative.<\/p>\n
Below is the implementation process of the Dijkstra algorithm using Kotlin.\n <\/p>\n
1. Graph Representation<\/h3>\n
\n To represent the graph, we use an adjacency list.
\n For each vertex, we store the vertices reachable from that vertex and the weight of the edge.
\n For example, we can represent each vertex as a list using an integer array.\n <\/p>\n
\n val graph = Array(N) { mutableListOf>() }\n <\/code><\/pre>\n2. Input Processing<\/h3>\n
\n Add the edge information received as input to the graph.
\n According to the input format, we store the information of each edge through a loop.\n <\/p>\n
\n for (i in 0 until M) {\n val (A, B, C) = readLine()!!.split(\" \").map { it.toInt() }\n graph[A-1].add(Pair(B-1, C)) \/\/ Edge from A to B with weight C\n }\n <\/code><\/pre>\n3. Dijkstra Algorithm Implementation<\/h3>\n
\n Implement the algorithm to find the current shortest path using a priority queue.
\n Below is the core logic of the Dijkstra algorithm.\n <\/p>\n
\n fun dijkstra(start: Int) {\n val distance = Array(N) { Int.MAX_VALUE }\n distance[start] = 0\n \n val pq = PriorityQueue>(compareBy { it.second })\n pq.add(Pair(start, 0))\n\n while (pq.isNotEmpty()) {\n val (current, dist) = pq.poll()\n\n if (dist > distance[current]) continue\n\n for (next in graph[current]) {\n val (nextNode, weight) = next\n val newDist = dist + weight\n\n if (newDist < distance[nextNode]) {\n distance[nextNode] = newDist\n pq.add(Pair(nextNode, newDist))\n }\n }\n }\n }\n <\/code><\/pre>\n4. Output Result<\/h3>\n
\n Finally, calculate and print the shortest distance to the endpoint.
\n If the endpoint is unreachable, print -1.\n <\/p>\n
\n dijkstra(S - 1)\n val result = if (distance[E - 1] == Int.MAX_VALUE) -1 else distance[E - 1]\n println(result)\n <\/code><\/pre>\nEntire Code<\/h2>\n
Based on the above logic, a complete code is as follows.<\/p>\n
\n import java.util.*\n\n fun main() {\n val (N, M) = readLine()!!.split(\" \").map { it.toInt() }\n val graph = Array(N) { mutableListOf>() }\n\n for (i in 0 until M) {\n val (A, B, C) = readLine()!!.split(\" \").map { it.toInt() }\n graph[A - 1].add(Pair(B - 1, C))\n }\n\n val (S, E) = readLine()!!.split(\" \").map { it.toInt() }\n\n fun dijkstra(start: Int) {\n val distance = Array(N) { Int.MAX_VALUE }\n distance[start] = 0\n\n val pq = PriorityQueue>(compareBy { it.second })\n pq.add(Pair(start, 0))\n\n while (pq.isNotEmpty()) {\n val (current, dist) = pq.poll()\n\n if (dist > distance[current]) continue\n\n for (next in graph[current]) {\n val (nextNode, weight) = next\n val newDist = dist + weight\n\n if (newDist < distance[nextNode]) {\n distance[nextNode] = newDist\n pq.add(Pair(nextNode, newDist))\n }\n }\n }\n return distance\n }\n\n dijkstra(S - 1)\n val result = if (distance[E - 1] == Int.MAX_VALUE) -1 else distance[E - 1]\n println(result)\n }\n <\/code><\/pre>\n<\/div>\n\n
Conclusion<\/h2>\n
\n The Dijkstra algorithm is a powerful tool that can be applied to various problems.
\n Through the process of implementing it in Kotlin, we could understand the structure of the graph and learn various techniques to enhance the algorithm's performance.<\/p>\n
It is necessary to practice how to solve complex problems simply and implement them in code.
\n Also, try to develop the ability to solve various shortest path problems in the real world using the Dijkstra algorithm.\n <\/p>\n<\/div>\n
<\/body><\/p>\n","protected":false},"excerpt":{"rendered":"
Problem Description Given a graph, implement an algorithm to find the shortest path from one vertex to another. The given graph is a directed graph, and each edge has a weight. Vertices are represented by integers from 0 to N-1, and if there is an edge between two vertices, we know its weight. Input Format: … \ub354 \ubcf4\uae30 “kotlin coding test course, Dijkstra”<\/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":[106],"tags":[],"class_list":["post-34984","post","type-post","status-publish","format-standard","hentry","category----en"],"yoast_head":"\nkotlin coding test course, Dijkstra - \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\/34984\/\" \/>\n<meta property=\"og:locale\" content=\"ko_KR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"kotlin coding test course, Dijkstra - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"og:description\" content=\"Problem Description Given a graph, implement an algorithm to find the shortest path from one vertex to another. The given graph is a directed graph, and each edge has a weight. Vertices are represented by integers from 0 to N-1, and if there is an edge between two vertices, we know its weight. Input Format: … \ub354 \ubcf4\uae30 "kotlin coding test course, Dijkstra"\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/34984\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:34:17+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T11:45:28+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\/34984\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34984\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"kotlin coding test course, Dijkstra\",\"datePublished\":\"2024-11-01T09:34:17+00:00\",\"dateModified\":\"2024-11-01T11:45:28+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34984\/\"},\"wordCount\":391,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"Kotlin coding test\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/34984\/\",\"url\":\"https:\/\/atmokpo.com\/w\/34984\/\",\"name\":\"kotlin coding test course, Dijkstra - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#website\"},\"datePublished\":\"2024-11-01T09:34:17+00:00\",\"dateModified\":\"2024-11-01T11:45:28+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34984\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/34984\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/34984\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"kotlin coding test course, Dijkstra\"}]},{\"@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":"kotlin coding test course, Dijkstra - \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\/34984\/","og_locale":"ko_KR","og_type":"article","og_title":"kotlin coding test course, Dijkstra - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","og_description":"Problem Description Given a graph, implement an algorithm to find the shortest path from one vertex to another. The given graph is a directed graph, and each edge has a weight. Vertices are represented by integers from 0 to N-1, and if there is an edge between two vertices, we know its weight. Input Format: … \ub354 \ubcf4\uae30 \"kotlin coding test course, Dijkstra\"","og_url":"https:\/\/atmokpo.com\/w\/34984\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:34:17+00:00","article_modified_time":"2024-11-01T11:45:28+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\/34984\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/34984\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"kotlin coding test course, Dijkstra","datePublished":"2024-11-01T09:34:17+00:00","dateModified":"2024-11-01T11:45:28+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/34984\/"},"wordCount":391,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["Kotlin coding test"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/34984\/","url":"https:\/\/atmokpo.com\/w\/34984\/","name":"kotlin coding test course, Dijkstra - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/#website"},"datePublished":"2024-11-01T09:34:17+00:00","dateModified":"2024-11-01T11:45:28+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/34984\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/34984\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/34984\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"kotlin coding test course, Dijkstra"}]},{"@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\/34984","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=34984"}],"version-history":[{"count":1,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34984\/revisions"}],"predecessor-version":[{"id":34985,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34984\/revisions\/34985"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=34984"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=34984"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=34984"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}