How to use Dijkstra's algorithm in C++

How to use Dijkstra's algorithm in C?

Dijkstra's algorithm is a greedy algorithm used to find the shortest path between two vertices in a weighted directed graph. Its core idea is to gradually expand the shortest path by continuously updating the shortest distance from the starting vertex to other vertices.

The following will introduce how to use C to implement Dijkstra's algorithm and give specific code examples.

Implementing Dijkstra's algorithm requires the following steps:

Step 1: Initialization.

First, we need to initialize some data structures, including the starting vertex start, the shortest distance array dist and the access status array visited. The starting vertex start specifies the starting point of the shortest path, the shortest distance array dist is used to record the current shortest distance from the starting vertex to other vertices, and the access status array visited is used to mark whether the vertex has been visited.

Step 2: Initialize the shortest distance array.

Initialize the shortest distance from the starting vertex to other vertices to infinity, and initialize the shortest distance from the starting vertex to itself to 0. Also marks the starting vertex as visited.

Step 3: Update the shortest distance array.

For all vertices adjacent to the starting vertex, if a shorter path can be found through the starting vertex, update the shortest distance array. The specific update method is to add the distance from the starting vertex to the current vertex plus the weight of the edge from the starting vertex to the current vertex, and compare it with the original shortest distance from the current vertex.

Step 4: Select the next nearest vertex.

Select the vertex closest to the starting vertex from the unvisited vertices as the next vertex to be visited.

Step 5: Repeat steps 3 and 4.

Repeat steps 3 and 4 until all vertices have been visited. Finally, what is stored in the shortest distance array dist is the shortest distance from the starting vertex to each vertex.

The following is a code example that uses C to implement Dijkstra's algorithm:

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

vector<int> dijkstra(vector<vector<int>>& graph, int start) {
    int numVertices = graph.size();

    vector<int> dist(numVertices, INT_MAX); // 最短距离数组
    vector<bool> visited(numVertices, false); // 访问状态数组

    dist[start] = 0;

    for (int i = 0; i < numVertices - 1; i++) {
        int minDist = INT_MAX;
        int minIndex = -1;
        
        // 选取下一个最近顶点
        for (int j = 0; j < numVertices; j++) {
            if (!visited[j] && dist[j] < minDist) {
                minDist = dist[j];
                minIndex = j;
            }
        }

        visited[minIndex] = true;

        // 更新最短距离数组
        for (int j = 0; j < numVertices; j++) {
            if (!visited[j] && graph[minIndex][j] && dist[minIndex] != INT_MAX && dist[minIndex] + graph[minIndex][j] < dist[j]) {
                dist[j] = dist[minIndex] + graph[minIndex][j];
            }
        }
    }

    return dist;
}

int main() {
    vector<vector<int>> graph = {
        {0, 2, 4, 0, 0},
        {2, 0, 1, 3, 0},
        {4, 1, 0, 0, 2},
        {0, 3, 0, 0, 3},
        {0, 0, 2, 3, 0}
    };

    vector<int> shortestDist = dijkstra(graph, 0);

    cout << "起始顶点到各个顶点的最短距离：" << endl;
    for (int i = 0; i < shortestDist.size(); i++) {
        cout << "到顶点 " << i << " 的最短距离为：" << shortestDist[i] << endl;
    }

    return 0;
}

In the above code, we represent a weighted directed graph through a two-dimensional matrix. Each element in the matrix Element represents the weight of the edge between two vertices. Finally, the shortest distance from the starting vertex to each vertex is output.

The above is the detailed content of How to use Dijkstra's algorithm in C++. For more information, please follow other related articles on the PHP Chinese website!