21xrx.com
2024-12-22 21:50:29 Sunday
登录
文章检索 我的文章 写文章
C++实现邻接表Dijkstra算法
2023-07-08 14:50:33 深夜i     --     --
C++ 邻接表 Dijkstra算法 最短路径

Dijkstra算法是一个经典的单源最短路径算法,常用于解决带权重的图问题。邻接表是一种常见的图表示方法,它由多个链表组成,每个链表代表一个节点和它所连的所有边。邻接表在使用Dijkstra算法时可以大大提高效率。本文将介绍如何使用C++实现邻接表Dijkstra算法。

步骤:

1. 定义节点和边的结构体

为了方便操作,我们需要定义节点和边的结构体。节点结构体需要包括一个节点标识和一个指向邻接链表头的指针。边结构体需要包括一个终点节点、一条边的权重以及一个指向下一条边的指针。

2. 初始化邻接表

邻接表可以通过链表实现,在初始化时需要为每个节点创建一个链表头。在邻接表中插入边时,可以通过遍历链表找到对应的节点,然后在该节点的链表中插入边。

3. 实现Dijkstra算法

Dijkstra算法需要维护一个距离数组和一个标记数组。距离数组记录源点到各个节点的最短距离,标记数组记录每个节点是否已经被访问过。

Dijkstra算法的核心是不断地找到距离源点最近的未访问节点,并更新该节点的距离。更新距离时需要考虑两个因素:当前节点的距离和经过当前节点到达终点的距离。具体来说,需要将当前节点的距离加上当前边的权重,得到经过当前节点到达终点的距离,然后判断该距离是否小于当前终点的距离,如果是则更新终点的距离。

4. 输出结果

Dijkstra算法结束后,距离数组中存储的即为源点到各个节点的最短距离。可以依次输出每个节点的距离即可。

示例代码:


#include <iostream>

#include <vector>

#include <queue>

using namespace std;

const int MAXN = 10010;

const int INF = 1e9;

struct Edge w;

struct Node {

  int u, d;

  bool operator<(const Node &x) const

    return d > x.d;

  

};

int head[MAXN], dist[MAXN], vis[MAXN], edgeCnt;

Edge edges[MAXN * 2];

void addEdge(int u, int v, int w) {

  edges[++edgeCnt].to = v;

  edges[edgeCnt].w = w;

  edges[edgeCnt].next = head[u];

  head[u] = edgeCnt;

}

void dijkstra(int s) {

  priority_queue<Node> pq;

  pq.push((Node) 0);

  dist[s] = 0;

  while (!pq.empty()) {

    Node node = pq.top();

    pq.pop();

    int u = node.u;

    if (vis[u])

      continue;

    

    vis[u] = 1;

    for (int i = head[u]; i; i = edges[i].next) {

      int v = edges[i].to;

      if (dist[v] > dist[u] + edges[i].w) {

        dist[v] = dist[u] + edges[i].w;

        pq.push((Node) {v, dist[v]});

      }

    }

  }

}

int main() {

  int n, m, s, u, v, w;

  cin >> n >> m >> s;

  for (int i = 1; i <= m; i++) {

    cin >> u >> v >> w;

    addEdge(u, v, w);

  }

  fill(dist + 1, dist + n + 1, INF);

  dijkstra(s);

  for (int i = 1; i <= n; i++) {

    cout << (dist[i] == INF ? -1 : dist[i]) << endl;

  }

  return 0;

}

总结:

邻接表Dijkstra算法是解决带权重的图问题的重要算法之一。相比于邻接矩阵,使用邻接表可以节省空间,同时在查找节点相邻边时时间复杂度更低。在实际应用中,需要注意邻接表的创建和常用操作的实现方式,以及Dijkstra算法的基本思想和实现细节。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复