使用C++编写Dijkstra算法 |21xrx.com

使用C++编写Dijkstra算法

2023-07-14 18:09:14 深夜i -- --

C++ Dijkstra算法图论最短路径编程

Dijkstra算法是一种常用的最短路径算法，可以求解任意两点之间的最短路径。本文介绍如何使用C++编写Dijkstra算法。

1. 定义图的数据结构

Dijkstra算法是基于图的，因此我们需要定义图的数据结构。可以使用邻接矩阵或邻接表来表示图，这里我们使用邻接表。邻接表由一组链表和一个数组组成，数组中的元素表示顶点，每个元素指向一个链表，链表中存储与该顶点相连的所有边的信息。定义如下：


struct Edge
  int to; // 边的终点
  int len; // 边的长度
  int next; // 下一条边
;
struct vertex
  int first; // 第一条邻接边
;

2. 初始化

在使用Dijkstra算法之前，需要初始化各个顶点的距离和标记值。对于每个顶点，我们将距离初始化为正无穷，标记值初始化为false，表示该顶点未被访问。Dijkstra算法也需要一个优先队列来存储顶点信息，优先队列按照距离从短到长排序。定义如下：


priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q; // 优先队列，按照距离从小到大排序
int d[N]; // 存储各个顶点到起点的距离
bool vis[N]; // 标记各个顶点是否访问过

3. 执行Dijkstra算法

Dijkstra算法是一种贪心算法，每次找到距离起点最近的未访问过的顶点，将其标记为已访问，并更新与该顶点相邻的顶点的距离。由于使用了优先队列，每次添加新元素之后，优先队列中的元素会自动按照距离由小到大排序。如下是实现代码：


void dijkstra(int s) {
  memset(d, INF, sizeof(d)); // 初始化距离无穷大
  memset(vis, false, sizeof(vis)); // 初始化全部未访问
  d[s] = 0; // 起点到自己的距离为0
  q.push(make_pair(0, s)); // 把起点加入队列
  while (!q.empty()) {
    int x = q.top().second; // 找出距离起点最近的顶点
    q.pop();
    if (vis[x]) continue; // 如果顶点已经被访问过，继续下一个循环
    vis[x] = true; // 把该顶点标记为已访问
    for (int i = head[x]; i != -1; i = edge[i].next) { // 遍历与该顶点相邻的所有顶点
      int y = edge[i].to;
      if (d[y] > d[x] + edge[i].len) { // 如果从起点到该顶点的距离更短
        d[y] = d[x] + edge[i].len; // 更新距离
        q.push(make_pair(d[y], y)); // 把该顶点加入队列
      }
    }
  }
}

4. 完整代码


#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 10010, M = 200010;
struct Edge
  int to; // 边的终点
  int len; // 边的长度
  int next; // 下一条边
edge[M];
struct Vertex
  int first; // 第一条邻接边
head[N];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q; // 优先队列，按照距离从小到大排序
int d[N]; // 存储各个顶点到起点的距离
bool vis[N]; // 标记各个顶点是否访问过
int idx = 0; // 边的数量
void add(int u, int v, int w) { // 添加一条从u到v的边，边权为w
  edge[idx].to = v;
  edge[idx].len = w;
  edge[idx].next = head[u].first;
  head[u].first = idx++;
}
void dijkstra(int s) { // 求从起点s到各个顶点的最短距离
  memset(d, INF, sizeof(d)); // 初始化距离无穷大
  memset(vis, false, sizeof(vis)); // 初始化全部未访问
  d[s] = 0; // 起点到自己的距离为0
  q.push(make_pair(0, s)); // 把起点加入队列
  while (!q.empty()) {
    int x = q.top().second; // 找出距离起点最近的顶点
    q.pop();
    if (vis[x]) continue; // 如果顶点已经被访问过，继续下一个循环
    vis[x] = true; // 把该顶点标记为已访问
    for (int i = head[x].first; i != -1; i = edge[i].next) { // 遍历与该顶点相邻的所有顶点
      int y = edge[i].to;
      if (d[y] > d[x] + edge[i].len) { // 如果从起点到该顶点的距离更短
        d[y] = d[x] + edge[i].len; // 更新距离
        q.push(make_pair(d[y], y)); // 把该顶点加入队列
      }
    }
  }
}
int main() {
  int n, m, s;
  scanf("%d%d%d", &n, &m, &s);
  memset(head, -1, sizeof(head)); // 邻接表初始化
  while (m--) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    add(u, v, w); // 将每条边添加到邻接表中
  }
  dijkstra(s); // 执行Dijkstra算法
  for (int i = 1; i <= n; i++) { // 输出结果
    if (d[i] == INF) printf("INF\n"); // 如果不存在路径，输出INF
    else printf("%d\n", d[i]);
  }
  return 0;
}

5. 总结

Dijkstra算法是一种常用的最短路径算法，可以求解任意两点之间的最短路径。使用C++编写Dijkstra算法的过程中需要注意图的数据结构，初始化和执行算法的代码实现。

上一篇: idea打包java可执行jar包

下一篇: 如何在C++中注释多行代码

评论区

()

相似文章