Dijkstra算法C语言实现 |21xrx.com

Dijkstra算法C语言实现

2023-08-21 16:45:50 深夜i -- --

C语言实现

Dijkstra算法是一种用于解决单源最短路径问题的经典算法。它是由荷兰计算机科学家Edsger Dijkstra在1956年提出的。Dijkstra算法的主要思想是通过不断选择当前距离起始节点最近的节点，逐步更新节点的最短路径。

在C语言中，我们可以用邻接矩阵来表示图，该矩阵记录了各个节点之间的边的权重。下面是Dijkstra算法在C语言中的实现：


#include <stdio.h>
#include <limits.h>
// 定义最大节点数量
#define MAX_NODES 100
// 初始化图的邻接矩阵
void initializeGraph(int graph[MAX_NODES][MAX_NODES], int numNodes) {
  for (int i = 0; i < numNodes; i++) {
    for (int j = 0; j < numNodes; j++) {
      graph[i][j] = INT_MAX; // 将所有边的权重初始化为无穷大
    }
  }
}
// 执行Dijkstra算法
void dijkstra(int graph[MAX_NODES][MAX_NODES], int numNodes, int startNode) {
  int dist[MAX_NODES]; // 记录起始节点到各个节点的最短距离
  int visited[MAX_NODES]; // 标记节点是否已被访问
  // 初始化距离和访问数组
  for (int i = 0; i < numNodes; i++) {
    dist[i] = INT_MAX; // 将所有节点的距离初始化为无穷大
    visited[i] = 0; // 将所有节点的访问状态初始化为未访问
  }
  dist[startNode] = 0; // 起始节点到自身的距离为0
  for (int count = 0; count < numNodes - 1; count++) {
    int minDist = INT_MAX;
    int minDistNode;
    // 选择当前距离起始节点最近的节点
    for (int v = 0; v < numNodes; v++) {
      if (!visited[v] && dist[v] <= minDist) {
        minDist = dist[v];
        minDistNode = v;
      }
    }
    // 标记该节点为已访问
    visited[minDistNode] = 1;
    // 更新其他未访问节点的最短距离
    for (int v = 0; v < numNodes; v++) {
      if (!visited[v] && graph[minDistNode][v] != INT_MAX &&
        dist[minDistNode] + graph[minDistNode][v] < dist[v]) {
        dist[v] = dist[minDistNode] + graph[minDistNode][v];
      }
    }
  }
  // 打印最短距离
  for (int i = 0; i < numNodes; i++) {
    printf("距离节点 %d 的最短距离是：%d\n", i, dist[i]);
  }
}
int main() {
  int graph[MAX_NODES][MAX_NODES];
  int numNodes;
  // 读取图的节点数量
  printf("请输入节点数量：");
  scanf("%d", &numNodes);
  // 初始化图的邻接矩阵
  initializeGraph(graph, numNodes);
  // 读取图的边及权重
  printf("请输入边的数量：");
  int numEdges;
  scanf("%d", &numEdges);
 
  // 注意：这里只添加了无向图的边，如果是有向图需要修改
  printf("请输入每条边的起始节点、结束节点及其权重：\n");
  for (int i = 0; i < numEdges; i++) {
    int start, end, weight;
    scanf("%d %d %d", &start, &end, &weight);
    graph[start][end] = weight;
    graph[end][start] = weight;
  }
  // 读取起始节点
  int startNode;
  printf("请输入起始节点：");
  scanf("%d", &startNode);
  // 执行Dijkstra算法
  dijkstra(graph, numNodes, startNode);
  return 0;
}

以上是Dijkstra算法在C语言中的实现。该程序首先读取图的节点数量，然后读取每条边的起始节点、结束节点及其权重，并根据这些信息构建图的邻接矩阵。接着输入起始节点，程序将执行Dijkstra算法并输出最短距离。该程序使用了邻接矩阵表示图的结构，并使用数组来记录节点的最短距离和访问状态。

总结来说，Dijkstra算法是一种十分重要且常用的算法，它通过不断选择当前最短路径的节点来求解单源最短路径。在C语言中，我们可以使用邻接矩阵来表示图，并使用数组来记录节点的最短距离和访问状态。通过实现Dijkstra算法，我们可以方便地求解最短路径问题，对于网络路由和路径规划等领域具有广泛的应用前景。

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

下一篇: C++操作符重载函数说明

评论区

()

相似文章