In this post, we will learn about Dijkstra’s algorithm and solve a problem using it. Dijkstra’s algorithm is an algorithm used to find the shortest path between each vertex in a graph and is mainly used in various pathfinding problems.<\/p>\n
Dijkstra’s algorithm is an efficient method for finding the shortest path from a starting vertex to all other vertices in a weighted graph. This algorithm works by calculating the path length to reach specific vertices and continuously updating the shortest path.<\/p>\n
This problem involves finding the shortest path between the starting vertex and the destination vertex in a given weighted graph. The graph is provided with a number of vertices and edges, and the weights of each edge are also given.<\/p>\n
Print the length of the shortest path from the starting vertex S to the destination vertex E. If it cannot be reached, print -1.<\/p>\n
import java.util.*;\n\npublic class Dijkstra {\n static class Edge {\n int to;\n int weight;\n Edge(int to, int weight) {\n this.to = to;\n this.weight = weight;\n }\n }\n\n public static void main(String[] args) {\n Scanner scanner = new Scanner(System.in);\n \n \/\/ Graph construction\n int N = scanner.nextInt(); \/\/ Number of vertices\n int M = scanner.nextInt(); \/\/ Number of edges\n int S = scanner.nextInt(); \/\/ Starting vertex\n int E = scanner.nextInt(); \/\/ Destination vertex\n\n List[] graph = new ArrayList[N + 1];\n for (int i = 1; i <= N; i++) {\n graph[i] = new ArrayList<>();\n }\n\n \/\/ Receive edge input\n for (int i = 0; i < M; i++) {\n int A = scanner.nextInt();\n int B = scanner.nextInt();\n int W = scanner.nextInt();\n graph[A].add(new Edge(B, W));\n graph[B].add(new Edge(A, W)); \/\/ Undirected graph\n }\n\n \/\/ Execute Dijkstra's algorithm\n int result = dijkstra(graph, N, S, E);\n System.out.println(result);\n }\n\n public static int dijkstra(List[] graph, int N, int start, int end) {\n int[] dist = new int[N + 1];\n Arrays.fill(dist, Integer.MAX_VALUE);\n dist[start] = 0;\n\n PriorityQueue pq = new PriorityQueue<>(Comparator.comparingInt(e -> e.weight));\n pq.offer(new Edge(start, 0));\n\n boolean[] visited = new boolean[N + 1];\n\n while (!pq.isEmpty()) {\n Edge current = pq.poll();\n int currentNode = current.to;\n\n if (visited[currentNode]) continue;\n visited[currentNode] = true;\n\n for (Edge edge : graph[currentNode]) {\n if (visited[edge.to]) continue;\n\n if (dist[currentNode] + edge.weight < dist[edge.to]) {\n dist[edge.to] = dist[currentNode] + edge.weight;\n pq.offer(new Edge(edge.to, dist[edge.to]));\n }\n }\n }\n\n return dist[end] == Integer.MAX_VALUE ? -1 : dist[end];\n }\n}<\/code><\/pre>\n3.2. Code Explanation<\/h3>\n
The above code is an implementation of Dijkstra's algorithm written in Java. Here is an explanation of the main parts:<\/p>\n
\n- Edge Class:<\/strong> A class that defines the edges of the graph. Each edge has a destination node and a weight.<\/li>\n
- Graph Initialization:<\/strong> Initializes the graph using an adjacency list approach.<\/li>\n
- Priority Queue:<\/strong> Used to explore the current shortest paths, prioritizing nodes with shorter distances.<\/li>\n
- Dijkstra's Algorithm:<\/strong> In each iteration, it selects the node with the smallest distance and updates the distances of the connected nodes.<\/li>\n<\/ul>\n
4. Time Complexity<\/h2>\n
The time complexity of Dijkstra's algorithm varies depending on the use of the priority queue. When using an array as a priority queue, it is O((N + M) log N). Here, N is the number of vertices and M is the number of edges. This algorithm performs well in graphs with many vertices compared to the number of edges.<\/p>\n
5. Conclusion<\/h2>\n
In this post, we explored how to solve the shortest path problem using Dijkstra's algorithm. This algorithm can be applied in various fields, particularly in networks, mapping services, and optimization problems. Understanding and problem-solving abilities related to such algorithms are crucial in coding tests, so it is recommended to practice consistently.<\/p>\n
<\/body><\/p>\n","protected":false},"excerpt":{"rendered":"