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

Dijkstra算法

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

Dijkstra算法的基本思想

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

算法步骤:
  1. 初始化

    • 将源点到自身的距离设为0,即 dist[source] = 0
    • 将源点到其他所有顶点的距离设为无穷大,即 dist[v] = +∞
    • 使用一个优先队列(最小堆)来存储待处理的顶点,初始时将源点加入队列。
  2. 松弛操作

    • 从优先队列中取出距离最小的顶点 u
    • 对于顶点 u 的所有出边 (u, v),尝试更新从源点到顶点 v 的距离:
      if dist[u] + weight(u, v) < dist[v]:
          dist[v] = dist[u] + weight(u, v)
      
    • 如果更新了 dist[v],则将顶点 v 加入优先队列。
  3. 重复上述过程,直到优先队列为空。

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;
}

算法复杂度

  • 时间复杂度
    • 如果使用普通数组实现,时间复杂度为 O(V²)
    • 如果使用优先队列(最小堆)实现,时间复杂度为 O(E + V log V),其中 E 是边数,V 是顶点数。
  • 空间复杂度O(V + E),主要用于存储图的邻接表和辅助数组。

适用场景

Dijkstra算法适用于以下场景:

  1. 图中不包含负权边
  2. 需要快速计算从单个源点到所有其他顶点的最短路径。
  3. 图的边数较多,且顶点数较少(适合稀疏图)。

注意事项

  1. 负权边问题

    • Dijkstra算法不能处理负权边。如果图中可能包含负权边,应使用Bellman-Ford算法或SPFA算法。
  2. 图的表示

    • 在实际应用中,图可以用邻接表或邻接矩阵表示。邻接表更适合稀疏图,而邻接矩阵更适合稠密图。
  3. 优化

    • 如果图中包含大量顶点,但只有少数顶点需要计算最短路径,可以使用启发式算法(如A*算法)来进一步优化。

总结

Dijkstra算法是一种高效的单源最短路径算法,特别适合处理不包含负权边的图。它通过贪心策略逐步扩展已知最短路径的集合,并利用优先队列优化松弛操作,从而在大多数情况下能够快速找到最短路径。


http://www.kler.cn/a/587153.html

相关文章:

  • 二叉树的层序遍历(102)
  • 平板作为笔记本副屏使用spacedesk
  • Java入职篇(5)—— IDEA快捷键
  • 计算机毕业设计:基于Android和SNS的音乐星球软件
  • rv1106上libwebsockets的编译
  • 阿里百炼Spring AI Alibaba
  • PECL(Positive Emitter-Coupled Logic)电平详解
  • 【AI】内容生成式AI(AIGC)的深度分析与扩展
  • PCDN 与边缘计算的结合:未来内容分发的新趋势
  • iOS应用程序开发(图片处理器)
  • 【前端基础】2、HTML的元素(基础说明)
  • 【Linux网络】HTTPS
  • 3.14-信号
  • WebRTC中音视频服务质量QoS之RTT衡量网络往返时延的加权平均RTT计算机制‌详解
  • DeepSeek 助力 Vue3 开发:打造丝滑的表格(Table)之添加列宽调整功能,示例Table14_10空状态的固定表头表格
  • 【云原生知识】如何搭建基于服务网关的分布式服务?
  • 【Linux-传输层协议TCP】流量控制+滑动窗口+拥塞控制+延迟应答+捎带应答+面向字节流+粘包问题+TCP异常情况+TCP小结
  • 时间序列重采样与pandas的resample方法是如何实现的?
  • 本地化部署Deepseek关于Ollama 安全加固方案(新手易学)
  • 使用spring data MongoDB对MongoDB进行简单CURD操作示例