当前位置：首页 > article >正文

Dijkstra算法

article 2025/3/16 16:10:19

Dijkstra算法（迪杰斯特拉算法）是一种经典的单源最短路径算法，用于在加权图中找到从一个源点到所有其他顶点的最短路径。它要求图中不能有负权边，因为负权边可能会导致算法的贪心策略失效。

Dijkstra算法的基本思想

Dijkstra算法的核心思想是贪心算法，通过逐步扩展已知最短路径的集合，最终找到从源点到所有顶点的最短路径。

算法步骤：

初始化：
- 将源点到自身的距离设为0，即 dist[source] = 0。
- 将源点到其他所有顶点的距离设为无穷大，即 dist[v] = +∞。
- 使用一个优先队列（最小堆）来存储待处理的顶点，初始时将源点加入队列。
松弛操作：
- 从优先队列中取出距离最小的顶点 u。
- 对于顶点 u 的所有出边 (u, v)，尝试更新从源点到顶点 v 的距离：
```
if dist[u] + weight(u, v) < dist[v]:
    dist[v] = dist[u] + weight(u, v)
```
- 如果更新了 dist[v]，则将顶点 v 加入优先队列。
重复上述过程，直到优先队列为空。

Dijkstra算法的实现

以下是Dijkstra算法的标准实现，使用优先队列（最小堆）来优化松弛操作。

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

const int MAXN = 100005; // 最大顶点数
const int INF = 0x3f3f3f3f; // 表示无穷大

struct Edge {
    int to, weight;
};

vector<Edge> graph[MAXN]; // 邻接表存储图
int dist[MAXN];           // 存储从源点到每个顶点的最短距离
bool visited[MAXN];       // 标记顶点是否已经被处理

// Dijkstra算法
void dijkstra(int n, int source) {
    // 初始化
    for (int i = 1; i <= n; i++) {
        dist[i] = INF;
        visited[i] = false;
    }
    dist[source] = 0;

    // 使用优先队列（最小堆）
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    pq.push({0, source}); // {距离, 顶点}

    while (!pq.empty()) {
        int u = pq.top().second; // 当前顶点
        int d = pq.top().first;  // 当前顶点的距离
        pq.pop();

        if (visited[u]) continue; // 如果已经处理过，跳过
        visited[u] = true;

        // 遍历所有出边
        for (const auto& edge : graph[u]) {
            int v = edge.to;
            int weight = edge.weight;

            // 尝试松弛
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v}); // 将更新后的顶点加入队列
            }
        }
    }
}

int main() {
    int n, m, source;
    cout << "Enter number of vertices and edges: ";
    cin >> n >> m;
    cout << "Enter source vertex: ";
    cin >> source;

    cout << "Enter edges (u, v, weight):" << endl;
    for (int i = 0; i < m; i++) {
        int u, v, weight;
        cin >> u >> v >> weight;
        graph[u].push_back({v, weight}); // 添加边
    }

    dijkstra(n, source);

    cout << "Shortest distances from source vertex " << source << ":" << endl;
    for (int i = 1; i <= n; i++) {
        if (dist[i] == INF) {
            cout << "Vertex " << i << ": No path" << endl;
        } else {
            cout << "Vertex " << i << ": " << dist[i] << endl;
        }
    }

    return 0;
}