Hello, everyone! Today, we will take a deep dive into the Dijkstra’s Algorithm<\/strong> and solve problems that are frequently asked in coding tests. Dijkstra’s Algorithm is an algorithm used to find the shortest path in a weighted graph, primarily used to solve network shortest path problems.<\/p>\n Dijkstra’s Algorithm, developed by Edsger Dijkstra in 1956, is a shortest path algorithm used to find the shortest path from a specific vertex to all other vertices. This algorithm does not allow negative weights and assumes that the graph is connected.<\/p>\n Now let’s apply Dijkstra’s Algorithm through a real problem.<\/p>\n Write a program to find the shortest path from a specific starting vertex to all other vertices given a graph provided as input.<\/p>\n Output the shortest distance from the starting vertex First, we represent the graph as an adjacency list<\/strong> based on the given edge information. In Python, we can use a dictionary to store each vertex and the other vertices connected to it along with their weights.<\/p>\n Now we will implement Dijkstra’s Algorithm. This algorithm efficiently updates the shortest path found so far using a priority queue.<\/p>\n We compile all elements to write the final code, which also includes the input handling and result processing parts.<\/p>\n1. Overview of Dijkstra’s Algorithm<\/h2>\n
1.1 Algorithm Operating Principle<\/h3>\n
\n
2. Problem Description<\/h2>\n
Problem: Find the Shortest Path<\/h3>\n
Input Conditions<\/h4>\n
\n
V<\/code> and the number of edges E<\/code>. (1 \u2264 V \u2264 20, 1 \u2264 E \u2264 100)<\/li>\nA<\/code>, ending vertex B<\/code>, and weight C<\/code>.<\/li>\nK<\/code>.<\/li>\n<\/ul>\nOutput Conditions<\/h4>\n
K<\/code> to all other vertices. If there is no path to any vertex, output INF<\/code>.<\/p>\n3. Problem Solving Process<\/h2>\n
3.1 Graph Representation<\/h3>\n
from collections import defaultdict\nimport heapq\n\ndef create_graph(edges):\n graph = defaultdict(list)\n for A, B, C in edges:\n graph[A].append((B, C))\n return graph\n<\/code><\/pre>\n3.2 Implementing Dijkstra’s Algorithm<\/h3>\n
def dijkstra(graph, start, V):\n distances = {vertex: float('inf') for vertex in range(1, V + 1)}\n distances[start] = 0\n priority_queue = [(0, start)]\n\n while priority_queue:\n current_distance, current_vertex = heapq.heappop(priority_queue)\n\n if current_distance > distances[current_vertex]:\n continue\n\n for neighbor, weight in graph[current_vertex]:\n distance = current_distance + weight\n\n if distance < distances[neighbor]:\n distances[neighbor] = distance\n heapq.heappush(priority_queue, (distance, neighbor))\n\n return distances\n<\/code><\/pre>\n3.3 Final Code<\/h3>\n
def main():\n V, E = map(int, input().split())\n edges = [tuple(map(int, input().split())) for _ in range(E)]\n K = int(input())\n\n graph = create_graph(edges)\n distances = dijkstra(graph, K, V)\n\n for vertex in range(1, V + 1):\n if distances[vertex] == float('inf'):\n print(\"INF\")\n else:\n print(distances[vertex])\n\nif __name__ == \"__main__\":\n main()\n<\/code><\/pre>\n4. Time Complexity<\/h2>\n