Dijkstra算法C++代码 |21xrx.com

Dijkstra算法C++代码

2023-07-04 10:44:03 深夜i 13 0

Dijkstra 算法 C++ 代码图论

Dijkstra算法是一种经典的图论算法，用于计算带权图中的最短路径。它采用了一种贪心的策略，每步选取目前离源点最近的一个顶点，然后以该顶点为中心进行扩展，最终得到源点到其他所有顶点的最短路径。

下面是Dijkstra算法的C++实现代码：

#include <iostream>
#include <limits.h>
using namespace std;
const int MAXN = 1001;
int graph[MAXN][MAXN]; // 图的邻接矩阵，存储每条边的权值
int dist[MAXN]; // 存储源点到各个顶点的最短距离
bool vis[MAXN]; // 标记顶点是否已经访问过
int Dijkstra(int n, int s, int t)
{
  // 初始化
  for (int i = 1; i <= n; ++i) {
    dist[i] = graph[s][i];
    vis[i] = false;
  }
  vis[s] = true;
  // 进行n-1次循环（每个顶点最多被访问一次）
  for (int i = 1; i < n; ++i) {
    int minv = -1;
    for (int j = 1; j <= n; ++j) {
      if (!vis[j] && (minv == -1 || dist[j] < dist[minv]))
        // 找到距离最近的未访问顶点
        minv = j;
      
    }
    vis[minv] = true;
    // 更新源点s到其他未访问顶点的最短距离
    for (int j = 1; j <= n; ++j) {
      if (!vis[j]) {
        dist[j] = min(dist[j], dist[minv] + graph[minv][j]);
      }
    }
  }
  return dist[t];
}
int main()
{
  int n, m, s, t;
  cin >> n >> m >> s >> t;
  // 初始化图的邻接矩阵
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      graph[i][j] = INT_MAX;
    }
  }
  for (int i = 1; i <= m; ++i) {
    int u, v, w;
    cin >> u >> v >> w;
    graph[u][v] = graph[v][u] = w; // 无向图
  }
  int ans = Dijkstra(n, s, t);
  cout << ans << endl;
  return 0;
}

在这段代码中，我们用`graph`来存储图的邻接矩阵，`dist`存储源点到各个顶点的最短距离，`vis`用来标记顶点是否已经访问过。在主函数中，我们通过输入读入图的顶点数`n`、边数`m`、源点`s`和目标点`t`，并通过循环读入每条边的信息，并初始化邻接矩阵`graph`。

然后，我们调用`Dijkstra()`函数计算源点`s`到目标点`t`的最短距离，并输出结果。在函数`Dijkstra()`中，我们首先初始化源点`dist`数组和`vis`数组，然后使用循环选取距离最近的未访问顶点，并更新源点到其他未访问顶点的最短距离。最后，返回源点到目标点的最短距离。

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

下一篇: C++如何获取输入法状态

评论区

相似文章