C++ Coding Test Course, Finding the Shortest Path

1. Problem Definition

The shortest path problem is the problem of finding the minimum distance between two vertices in a given graph. The graph consists of nodes (vertices) and edges connecting them, with each edge expressed as a distance or weight.

For example, let’s assume there is a graph like the one below. Here, A, B, C, and D are nodes, and the edges have the following weights:

    A --1-- B
    |      /|
    4     2 |
    |  /      |
    C --3-- D
    

The task is to find the shortest path between two nodes A and D.

2. Algorithm Selection

The algorithms commonly used to solve the shortest path problem are Dijkstra’s algorithm and the Bellman-Ford algorithm.

In this problem, we will use Dijkstra’s algorithm, which is suitable for finding the shortest path in graphs with non-negative weights.

2.1 Explanation of Dijkstra’s Algorithm

Dijkstra’s algorithm works in the following steps:

1. Set the starting node and initialize the shortest distance to that node as 0.
2. Initialize the shortest distances for all other nodes to infinity.
3. Select the unvisited node with the lowest shortest distance value.
4. Set this node as the current node and update the shortest distance values of all adjacent nodes reachable through this node.
5. Repeat steps 3-4 until all nodes are visited.

3. C++ Implementation

Now let’s implement Dijkstra’s algorithm in C++. Below is the code for finding the shortest path in the graph described above:

#include <iostream>
#include <vector>
#include <queue>
#include <limits> // for numeric_limits
using namespace std;

// Graph structure definition
struct Edge {
    int destination;
    int weight;
};

// Dijkstra's algorithm implementation
vector dijkstra(int start, const vector>& graph) {
    int n = graph.size();
    vector distance(n, numeric_limits::max());
    distance[start] = 0;
    
    priority_queue, vector>, greater>> minHeap;
    minHeap.push({0, start});

    while (!minHeap.empty()) {
        int currentDistance = minHeap.top().first;
        int currentNode = minHeap.top().second;
        minHeap.pop();

        // Ignore if the current node's distance value is greater
        if (currentDistance > distance[currentNode]) continue;

        // Explore adjacent nodes
        for (const Edge& edge : graph[currentNode]) {
            int newDistance = currentDistance + edge.weight;
            if (newDistance < distance[edge.destination]) {
                distance[edge.destination] = newDistance;
                minHeap.push({newDistance, edge.destination});
            }
        }
    }

    return distance;
}

int main() {
    // Initialize the graph
    int n = 4; // Number of nodes
    vector> graph(n);
    
    // Add edges (0-based index)
    graph[0].push_back({1, 1});
    graph[0].push_back({2, 4});
    graph[1].push_back({2, 2});
    graph[1].push_back({3, 1});
    graph[2].push_back({3, 3});
    
    int startNode = 0; // A
    vector shortestPaths = dijkstra(startNode, graph);

    // Print results
    cout << "Shortest Path:" << endl;
    for (int i = 0; i < n; i++) {
        cout << "Shortest path from A to " << char('A' + i) << ": ";
        if (shortestPaths[i] == numeric_limits::max()) {
            cout << "Unreachable" << endl;
        } else {
            cout << shortestPaths[i] << endl;
        }
    }

    return 0;
}
    

4. Code Explanation

4.1 Graph Structure Setup

First, we define the edge structure to create a graph that includes information for each node and weight. We use vector<vector<Edge>> to represent the graph.

4.2 Implementation of Dijkstra

We wrote the function dijkstra for Dijkstra’s algorithm. It calculates the shortest distance from the starting node to each node and stores it in the distance vector. We use a priority_queue to efficiently manage the current shortest paths.

4.3 Main Function

The main function initializes the graph, calls the Dijkstra function to find the shortest path, and then prints the results.

5. Complexity Analysis

The time complexity of Dijkstra’s algorithm depends on the data structure used. Generally, when using a heap, it is represented as O(E log V), where E is the number of edges and V is the number of nodes.

6. References

• Dijkstra’s Algorithm – Wikipedia
• GeeksforGeeks – Dijkstra’s Algorithm Implementation

7. Conclusion

In this article, we learned how to find the shortest path in a given graph using Dijkstra’s algorithm implemented in C++. By understanding the basic concepts of the algorithm and its C++ implementation, we could deepen our understanding through examples. It is important to apply such algorithms to problem-solving during actual coding tests. Continuously solving various problems will help you gain experience.