Dijkstra’s Algorithm is a very useful algorithm for finding the shortest path from one vertex to another in a graph. It is particularly used to find the shortest path in weighted graphs. In this course, we will understand the principles of Dijkstra’s Algorithm and learn how to implement it using C++.<\/p>\n
Given N cities and M roads, find the minimum cost to travel from one city to another. Each city is represented as a vertex and the roads are represented as edges in the graph.<\/p>\n
The information about the cities and roads is as follows:<\/p>\n
For example, if a graph with 5 cities and 6 roads is given, it will be input in the following format:<\/p>\n
\n5 6\n1 2 4\n1 3 2\n2 3 5\n1 4 1\n4 3 3\n2 5 7\n <\/pre>\nInput Format<\/h2>\n
\nFirst line: N M\nFrom the second line to the M-th line: A B C (information about each road)\n <\/pre>\nOutput Format<\/h2>\n
\nPrint the minimum cost for each city (1~N). \nIf it is impossible, print -1.\n <\/pre>\nExample Input<\/h3>\n
\n5 7\n1 2 2\n1 3 3\n2 3 1\n2 4 4\n3 4 2\n3 5 5\n4 5 1\n <\/pre>\nExample Output<\/h3>\n
\n1\n2\n3\n3\n4\n <\/pre>\nAlgorithm Explanation<\/h2>\n
Dijkstra’s Algorithm operates in a greedy manner to find the shortest path from one vertex to another. The basic idea is as follows:<\/p>\n
\n
- Set the initial distance to all vertices to infinity, and set the distance of the starting vertex to 0.<\/li>\n
- Select the vertex with the shortest distance and update the distances of all vertices adjacent to that vertex.<\/li>\n
- Repeat this process until the distances of all vertices are updated.<\/li>\n<\/ol>\n
Implementation Steps<\/h3>\n
\n
- Graph creation: Represent the graph using an adjacency list.<\/li>\n
- Utilize a priority queue: Use a priority queue (heap) to find the shortest path.<\/li>\n
- Initialize the distance array: Initialize the distances for each vertex.<\/li>\n
- Calculate the shortest path: Repeat the process of updating the minimum distance.<\/li>\n<\/ol>\n
C++ Code Implementation<\/h2>\n
\n#include <iostream>\n#include <vector>\n#include <queue>\n#include <utility>\n#include <limits>\n\nusing namespace std;\n\nvector<pair<int, int>> graph[100001];\nvector<int> dist;\n\nvoid dijkstra(int start) {\n priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;\n dist[start] = 0;\n pq.push(make_pair(0, start));\n\n while (!pq.empty()) {\n int currentDist = pq.top().first;\n int currentNode = pq.top().second;\n pq.pop();\n\n if (currentDist > dist[currentNode]) continue;\n\n for (auto edge : graph[currentNode]) {\n int next = edge.first;\n int weight = edge.second;\n\n if (dist[currentNode] + weight < dist[next]) {\n dist[next] = dist[currentNode] + weight;\n pq.push(make_pair(dist[next], next));\n }\n }\n }\n}\n\nint main() {\n int N, M;\n cin >> N >> M;\n dist.resize(N + 1, numeric_limits<int>::max());\n\n for (int i = 0; i < M; i++) {\n int A, B, C;\n cin >> A >> B >> C;\n graph[A].push_back(make_pair(B, C));\n graph[B].push_back(make_pair(A, C)); \/\/ Undirected graph case\n }\n\n dijkstra(1); \/\/ Start from City 1\n\n for (int i = 1; i <= N; i++) {\n if (dist[i] == numeric_limits<int>::max()) {\n cout << -1 << &endl\n } else {\n cout << dist[i] << &endl\n }\n }\n\n return 0;\n}\n <\/pre>\nCode Explanation<\/h2>\n
The code above implements Dijkstra’s Algorithm in the following way:<\/p>\n
\n
- Creating an adjacency list:<\/strong> Read the given information about cities and roads, and represent the graph in adjacency list form.<\/li>\n
- Priority queue:<\/strong> Use a priority queue to continuously extract the shortest distance to find the minimum distance.<\/li>\n
- Distance update:<\/strong> When moving from the current vertex to an adjacent vertex, update the distance if the new distance is shorter.<\/li>\n
- Output final results:<\/strong> Print the shortest distance to each city. Print -1 for cities that cannot be reached.<\/li>\n<\/ul>\n
Review and Conclusion<\/h2>\n
In this course, we understood the functioning of Dijkstra’s Algorithm and learned how to implement it in C++. Algorithms and data structures are very important topics in coding tests, and Dijkstra’s Algorithm is particularly utilized in graph-related problems. Additionally, be sure to practice graph traversal algorithms such as BFS and DFS.<\/p>\n
To deepen your understanding of Dijkstra’s Algorithm, it is helpful to solve various problems and compare it with other algorithms. Next time, we will also learn about the Bellman-Ford Algorithm or the Floyd-Warshall Algorithm. Thank you!<\/p>\n<\/div>\n
<\/body><\/p>\n","protected":false},"excerpt":{"rendered":"