C++ Coding Test Course, Dijkstra

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++.

Problem Description

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.

The information about the cities and roads is as follows:

  • Number of cities: N (1 ≤ N ≤ 100,000)
  • Number of roads: M (1 ≤ M ≤ 200,000)
  • Road information: A, B, C (the weight of the road connecting City A and City B is C)

For example, if a graph with 5 cities and 6 roads is given, it will be input in the following format:

5 6
1 2 4
1 3 2
2 3 5
1 4 1
4 3 3
2 5 7

Input Format

First line: N M
From the second line to the M-th line: A B C (information about each road)

Output Format

Print the minimum cost for each city (1~N). 
If it is impossible, print -1.

Example Input

5 7
1 2 2
1 3 3
2 3 1
2 4 4
3 4 2
3 5 5
4 5 1

Example Output

1
2
3
3
4

Algorithm Explanation

Dijkstra’s Algorithm operates in a greedy manner to find the shortest path from one vertex to another. The basic idea is as follows:

  1. Set the initial distance to all vertices to infinity, and set the distance of the starting vertex to 0.
  2. Select the vertex with the shortest distance and update the distances of all vertices adjacent to that vertex.
  3. Repeat this process until the distances of all vertices are updated.

Implementation Steps

  1. Graph creation: Represent the graph using an adjacency list.
  2. Utilize a priority queue: Use a priority queue (heap) to find the shortest path.
  3. Initialize the distance array: Initialize the distances for each vertex.
  4. Calculate the shortest path: Repeat the process of updating the minimum distance.

C++ Code Implementation

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <limits>

using namespace std;

vector<pair<int, int>> graph[100001];
vector<int> dist;

void dijkstra(int start) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    dist[start] = 0;
    pq.push(make_pair(0, start));

    while (!pq.empty()) {
        int currentDist = pq.top().first;
        int currentNode = pq.top().second;
        pq.pop();

        if (currentDist > dist[currentNode]) continue;

        for (auto edge : graph[currentNode]) {
            int next = edge.first;
            int weight = edge.second;

            if (dist[currentNode] + weight < dist[next]) {
                dist[next] = dist[currentNode] + weight;
                pq.push(make_pair(dist[next], next));
            }
        }
    }
}

int main() {
    int N, M;
    cin >> N >> M;
    dist.resize(N + 1, numeric_limits<int>::max());

    for (int i = 0; i < M; i++) {
        int A, B, C;
        cin >> A >> B >> C;
        graph[A].push_back(make_pair(B, C));
        graph[B].push_back(make_pair(A, C)); // Undirected graph case
    }

    dijkstra(1); // Start from City 1

    for (int i = 1; i <= N; i++) {
        if (dist[i] == numeric_limits<int>::max()) {
            cout << -1 << &endl
        } else {
            cout << dist[i] << &endl
        }
    }

    return 0;
}

Code Explanation

The code above implements Dijkstra’s Algorithm in the following way:

  • Creating an adjacency list: Read the given information about cities and roads, and represent the graph in adjacency list form.
  • Priority queue: Use a priority queue to continuously extract the shortest distance to find the minimum distance.
  • Distance update: When moving from the current vertex to an adjacent vertex, update the distance if the new distance is shorter.
  • Output final results: Print the shortest distance to each city. Print -1 for cities that cannot be reached.

Review and Conclusion

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.

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!