C++Dijkstra算法

Dijkstra算法是解决单源最短路问题的一种贪心算法。它的基本思想是从起点开始，按照距离从小到大的顺序依次确定每个节点的最短路径，直到到达终点为止。具体实现时，Dijkstra算法使用一个优先队列来存储待处理的节点，每次从队列中取出距离起点最近的节点进行处理，并更新与该节点相邻的节点的距离。在处理完所有节点之后，每个节点的最短路径就被确定了。

Dijkstra算法的时间复杂度为O(E log V)，其中E是边的数量，V是节点的数量。它的优点是能够处理带有负权边的图，缺点是无法处理带有负权环的图。

相关问题

c++dijkstra算法

Dijkstra算法是一种用于解决单源最短路径问题的经典算法，它可以找到从一个顶点到其他所有顶点的最短路径。下面是C++中实现Dijkstra算法的基本步骤：

1. 创建一个距离数组dist[]，用于存储从源顶点到其他顶点的最短距离。初始化dist[]数组，将源顶点的距离设置为0，其他顶点的距离设置为无穷大。

2. 创建一个优先队列（最小堆）minHeap，用于选择下一个要访问的顶点。将源顶点加入minHeap，并将其距离设置为0。

3. 循环执行以下步骤，直到minHeap为空：
a. 从minHeap中取出距离最小的顶点u。
b. 遍历u的所有邻接顶点v，计算从源顶点到v的距离newDist。如果newDist小于dist[v]，则更新dist[v]为newDist，并将v加入minHeap。

4. 最终，dist[]数组中存储了从源顶点到所有其他顶点的最短距离。

下面是一个简单的C++代码示例：

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

using namespace std;

void dijkstra(vector<vector<pair<int, int>>>& graph, int source, vector<int>& dist) {
    int n = graph.size();
    dist.resize(n, INT_MAX);
    dist[source] = 0;

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minHeap;
    minHeap.push({0, source});

    while (!minHeap.empty()) {
        int u = minHeap.top().second;
        minHeap.pop();

        for (auto& neighbor : graph[u]) {
            int v = neighbor.first;
            int weight = neighbor.second;

            int newDist = dist[u] + weight;
            if (newDist < dist[v]) {
                dist[v] = newDist;
                minHeap.push({newDist, v});
            }
        }
    }
}

int main() {
    int n = 5; // 顶点数
    vector<vector<pair<int, int>>> graph(n);

    // 添加边
    graph[0].push_back({1, 2});
    graph[0].push_back({2, 4});
    graph[1].push_back({2, 1});
    graph[1].push_back({3, 7});
    graph[2].push_back({3, 3});
    graph[2].push_back({4, 5});
    graph[3].push_back({4, 2});

    int source = 0; // 源顶点

    vector<int> dist;
    dijkstra(graph, source, dist);

    // 输出最短路径
    for (int i = 0; i < n; i++) {
        cout << "Distance from source to vertex " << i << ": " << dist[i] << endl;
    }

    return 0;
}

c++ dijkstra算法 时间复杂度0（n logn）

Dijkstra算法是一种用于解决单源最短路径问题的贪心算法。它的时间复杂度为O(n logn)，其中n是图中节点的数量。下面是C++实现：

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

using namespace std;

const int MAXN = 1000;
const int INF = INT_MAX;

vector<pair<int, int>> adj[MAXN];
int dist[MAXN];

void dijkstra(int s, int n) {
    for (int i = 0; i < n; i++) {
        dist[i] = INF;
    }
    dist[s] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push(make_pair(0, s));

    while (!pq.empty()) {
        int u = pq.top().second;
        int d = pq.top().first;
        pq.pop();
        if (d > dist[u]) {
            continue;
        }
        for (auto& edge : adj[u]) {
            int v = edge.first;
            int w = edge.second;
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push(make_pair(dist[v], v));
            }
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back(make_pair(v, w));
        adj[v].push_back(make_pair(u, w));
    }
    dijkstra(0, n);
    for (int i = 0; i < n; i++) {
        cout << dist[i] << " ";
    }
    cout << endl;
    return 0;
}

在上面的实现中，使用了一个优先队列来维护当前到源点距离最小的节点，从而保证每次找到的节点是当前最短路径的节点。由于每个节点最多被加入一次优先队列中，因此总时间复杂度为O(n logn)。