{"id":34308,"date":"2024-11-01T09:26:40","date_gmt":"2024-11-01T09:26:40","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=34308"},"modified":"2024-11-01T10:57:46","modified_gmt":"2024-11-01T10:57:46","slug":"c-coding-test-course-finding-the-shortest-path-2","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/34308\/","title":{"rendered":"C++ Coding Test Course, Finding the Shortest Path"},"content":{"rendered":"

<\/p>\n

1. Problem Definition<\/h2>\n

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.<\/p>\n

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:<\/p>\n

\n    A --1-- B\n    |      \/|\n    4     2 |\n    |  \/      |\n    C --3-- D\n    <\/pre>\n
The task is to find the shortest path between two nodes A and D.<\/p>\n
2. Algorithm Selection<\/h2>\n
The algorithms commonly used to solve the shortest path problem are Dijkstra’s algorithm and the Bellman-Ford algorithm.<\/p>\n
In this problem, we will use Dijkstra’s algorithm, which is suitable for finding the shortest path in graphs with non-negative weights.<\/p>\n
2.1 Explanation of Dijkstra’s Algorithm<\/h3>\n
Dijkstra’s algorithm works in the following steps:<\/p>\n
    \n
  1. Set the starting node and initialize the shortest distance to that node as 0.<\/li>\n
  2. Initialize the shortest distances for all other nodes to infinity.<\/li>\n
  3. Select the unvisited node with the lowest shortest distance value.<\/li>\n
  4. Set this node as the current node and update the shortest distance values of all adjacent nodes reachable through this node.<\/li>\n
  5. Repeat steps 3-4 until all nodes are visited.<\/li>\n<\/ol>\n
    3. C++ Implementation<\/h2>\n
    Now let’s implement Dijkstra’s algorithm in C++. Below is the code for finding the shortest path in the graph described above:<\/p>\n
    \n#include <iostream>\n#include <vector>\n#include <queue>\n#include <limits> \/\/ for numeric_limits\nusing namespace std;\n\n\/\/ Graph structure definition\nstruct Edge {\n    int destination;\n    int weight;\n};\n\n\/\/ Dijkstra's algorithm implementation\nvector dijkstra(int start, const vector>& graph) {\n    int n = graph.size();\n    vector distance(n, numeric_limits::max());\n    distance[start] = 0;\n    \n    priority_queue, vector>, greater>> minHeap;\n    minHeap.push({0, start});\n\n    while (!minHeap.empty()) {\n        int currentDistance = minHeap.top().first;\n        int currentNode = minHeap.top().second;\n        minHeap.pop();\n\n        \/\/ Ignore if the current node's distance value is greater\n        if (currentDistance > distance[currentNode]) continue;\n\n        \/\/ Explore adjacent nodes\n        for (const Edge& edge : graph[currentNode]) {\n            int newDistance = currentDistance + edge.weight;\n            if (newDistance < distance[edge.destination]) {\n                distance[edge.destination] = newDistance;\n                minHeap.push({newDistance, edge.destination});\n            }\n        }\n    }\n\n    return distance;\n}\n\nint main() {\n    \/\/ Initialize the graph\n    int n = 4; \/\/ Number of nodes\n    vector> graph(n);\n    \n    \/\/ Add edges (0-based index)\n    graph[0].push_back({1, 1});\n    graph[0].push_back({2, 4});\n    graph[1].push_back({2, 2});\n    graph[1].push_back({3, 1});\n    graph[2].push_back({3, 3});\n    \n    int startNode = 0; \/\/ A\n    vector shortestPaths = dijkstra(startNode, graph);\n\n    \/\/ Print results\n    cout << \"Shortest Path:\" << endl;\n    for (int i = 0; i < n; i++) {\n        cout << \"Shortest path from A to \" << char('A' + i) << \": \";\n        if (shortestPaths[i] == numeric_limits::max()) {\n            cout << \"Unreachable\" << endl;\n        } else {\n            cout << shortestPaths[i] << endl;\n        }\n    }\n\n    return 0;\n}\n    <\/int><\/int><\/vector<\/pair<\/pair<\/pair<\/int><\/int><\/vector<\/int><\/pre>\n
    4. Code Explanation<\/h2>\n
    4.1 Graph Structure Setup<\/h3>\n
    First, we define the edge structure to create a graph that includes information for each node and weight. We use vector<vector<Edge>><\/code> to represent the graph.<\/p>\n
    4.2 Implementation of Dijkstra<\/h3>\n
    We wrote the function dijkstra<\/code> for Dijkstra’s algorithm. It calculates the shortest distance from the starting node to each node and stores it in the distance<\/code> vector. We use a priority_queue<\/code> to efficiently manage the current shortest paths.<\/p>\n
    4.3 Main Function<\/h3>\n
    The main<\/code> function initializes the graph, calls the Dijkstra function to find the shortest path, and then prints the results.<\/p>\n
    5. Complexity Analysis<\/h2>\n
    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)<\/code>, where E<\/code> is the number of edges and V<\/code> is the number of nodes.<\/p>\n
    6. References<\/h2>\n