\n
\n 5 6\n 1 2 3\n 1 3 2\n 2 3 1\n 1 4 1\n 2 4 5\n 3 5 1\n <\/pre>\nThe first line indicates the number of vertices and edges, and each subsequent line shows the relationship between stops and the time required.<\/p>\n<\/div>\n
Problem Solving Process<\/h2>\nStep 1: Graph Modeling<\/h3>\n
\n To solve the above problem, we need to construct a graph where the bus stops are vertices and the bus routes and times are edges.
\n To do this, we will create an adjacency list that contains information about each stop and its edges.\n <\/p>\n
Step 2: Selecting the Shortest Path Algorithm<\/h3>\n
\n There are several algorithms to find the shortest path, but when there are weighted edges, it is appropriate to use Dijkstra’s Algorithm<\/strong>.
\n Dijkstra’s Algorithm is an effective way to calculate the shortest distance to each vertex.\n <\/p>\nStep 3: Implementing C# Code<\/h3>\n
\n Now, let’s write C# code based on the above content. The code below demonstrates how to implement Dijkstra’s Algorithm to find the shortest path in the given graph.\n <\/p>\n
\n
\n using System;\n using System.Collections.Generic;\n\n class Program\n {\n static void Main(string[] args)\n {\n int vertexCount = 5; \/\/ Number of vertices\n int[,] graph = new int[vertexCount + 1, vertexCount + 1];\n for (int i = 1; i <= vertexCount; i++)\n for (int j = 1; j <= vertexCount; j++)\n graph[i, j] = (i == j) ? 0 : int.MaxValue;\n\n \/\/ Add edges (time required)\n graph[1, 2] = 3;\n graph[1, 3] = 2;\n graph[2, 3] = 1;\n graph[1, 4] = 1;\n graph[2, 4] = 5;\n graph[3, 5] = 1;\n\n \/\/ Call Dijkstra's Algorithm\n int[] shortestPath = Dijkstra(graph, vertexCount, 1);\n\n \/\/ Output results\n Console.WriteLine(\"Shortest distance from vertex 1 to other vertices:\");\n for (int i = 1; i <= vertexCount; i++)\n {\n Console.WriteLine($\"Vertex 1 -> Vertex {i}: {(shortestPath[i] == int.MaxValue ? \"Unreachable\" : shortestPath[i].ToString())}\");\n }\n }\n\n static int[] Dijkstra(int[,] graph, int vertexCount, int start)\n {\n bool[] visited = new bool[vertexCount + 1];\n int[] distance = new int[vertexCount + 1];\n\n for (int i = 1; i <= vertexCount; i++)\n {\n distance[i] = (i == start) ? 0 : int.MaxValue;\n }\n\n for (int count = 0; count < vertexCount - 1; count++)\n {\n int u = MinDistance(distance, visited, vertexCount);\n visited[u] = true;\n\n for (int v = 1; v <= vertexCount; v++)\n {\n if (!visited[v] && graph[u, v] != int.MaxValue &&\n distance[u] != int.MaxValue &&\n distance[u] + graph[u, v] < distance[v])\n {\n distance[v] = distance[u] + graph[u, v];\n }\n }\n }\n\n return distance;\n }\n\n static int MinDistance(int[] distance, bool[] visited, int vertexCount)\n {\n int min = int.MaxValue;\n int minIndex = -1;\n\n for (int v = 1; v <= vertexCount; v++)\n {\n if (!visited[v] && distance[v] <= min)\n {\n min = distance[v];\n minIndex = v;\n }\n }\n return minIndex;\n }\n }\n <\/pre>\n<\/div>\nStep 4: Time Complexity Analysis<\/h3>\n
\n The time complexity of Dijkstra’s Algorithm is O(V^2)<\/code>, where V<\/code> represents the number of vertices.
\n Therefore, when there are many vertices, you may consider a more efficient method, which is the improved Dijkstra’s Algorithm using a priority queue.\n <\/p>\nConclusion<\/h2>\n
\n In this lecture, we implemented Dijkstra’s Algorithm to solve the problem of finding the fastest bus route using C#.
\n Similar problems may arise in actual coding tests or job interviews, so it is important to understand and practice this algorithm thoroughly.\n <\/p>\n
\n I hope you continue to study various algorithm problems and solutions in the future. If you have any additional questions or algorithm-related inquiries, feel free to ask!\n <\/p>\n
<\/body><\/p>\n","protected":false},"excerpt":{"rendered":"
In modern society, public transportation plays an important role, and especially when using buses, many people struggle to find the optimal routes. In this lecture, we will look at the process of solving the problem of finding the fastest bus route. To solve this problem, we will use C# to employ algorithms and data structures. … \ub354 \ubcf4\uae30 “C# Coding Test Course, Finding the Fastest Bus Route”<\/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":[90],"tags":[],"class_list":["post-33930","post","type-post","status-publish","format-standard","hentry","category-c-coding-test-tutorials"],"yoast_head":"\nC# Coding Test Course, Finding the Fastest Bus Route - \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\/33930\/\" \/>\n<meta property=\"og:locale\" content=\"ko_KR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"C# Coding Test Course, Finding the Fastest Bus Route - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"og:description\" content=\"In modern society, public transportation plays an important role, and especially when using buses, many people struggle to find the optimal routes. In this lecture, we will look at the process of solving the problem of finding the fastest bus route. To solve this problem, we will use C# to employ algorithms and data structures. … \ub354 \ubcf4\uae30 "C# Coding Test Course, Finding the Fastest Bus Route"\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/33930\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:22:07+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T10:55:01+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\/33930\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33930\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"C# Coding Test Course, Finding the Fastest Bus Route\",\"datePublished\":\"2024-11-01T09:22:07+00:00\",\"dateModified\":\"2024-11-01T10:55:01+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33930\/\"},\"wordCount\":374,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"C# Coding Test Tutorials\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/33930\/\",\"url\":\"https:\/\/atmokpo.com\/w\/33930\/\",\"name\":\"C# Coding Test Course, Finding the Fastest Bus Route - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#website\"},\"datePublished\":\"2024-11-01T09:22:07+00:00\",\"dateModified\":\"2024-11-01T10:55:01+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33930\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/33930\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/33930\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"C# Coding Test Course, Finding the Fastest Bus Route\"}]},{\"@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":"C# Coding Test Course, Finding the Fastest Bus Route - \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\/33930\/","og_locale":"ko_KR","og_type":"article","og_title":"C# Coding Test Course, Finding the Fastest Bus Route - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","og_description":"In modern society, public transportation plays an important role, and especially when using buses, many people struggle to find the optimal routes. In this lecture, we will look at the process of solving the problem of finding the fastest bus route. To solve this problem, we will use C# to employ algorithms and data structures. … \ub354 \ubcf4\uae30 \"C# Coding Test Course, Finding the Fastest Bus Route\"","og_url":"https:\/\/atmokpo.com\/w\/33930\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:22:07+00:00","article_modified_time":"2024-11-01T10:55:01+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\/33930\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/33930\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"C# Coding Test Course, Finding the Fastest Bus Route","datePublished":"2024-11-01T09:22:07+00:00","dateModified":"2024-11-01T10:55:01+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/33930\/"},"wordCount":374,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["C# Coding Test Tutorials"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/33930\/","url":"https:\/\/atmokpo.com\/w\/33930\/","name":"C# Coding Test Course, Finding the Fastest Bus Route - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/#website"},"datePublished":"2024-11-01T09:22:07+00:00","dateModified":"2024-11-01T10:55:01+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/33930\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/33930\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/33930\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"C# Coding Test Course, Finding the Fastest Bus Route"}]},{"@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\/33930","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=33930"}],"version-history":[{"count":1,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/33930\/revisions"}],"predecessor-version":[{"id":33931,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/33930\/revisions\/33931"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=33930"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=33930"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=33930"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}