C++贪心算法解决单源点最短路径问题 |21xrx.com

C++贪心算法解决单源点最短路径问题

2023-07-14 21:44:02 深夜i -- --

C++ 贪心算法单源点最短路径问题解决

单源点最短路径问题是在一个有向带权图中，给定一个源节点，求从该源节点到其余所有节点的最短路径。解决这个问题的算法有很多，其中一种比较受欢迎的算法是贪心算法。

C++贪心算法解决单源点最短路径问题，首先需要理解贪心算法的思想。贪心算法是一种局部最优，不断迭代，最终达到全局最优的算法。对于单源点最短路径问题，贪心算法的思想是每次选择当前到源节点距离最短的节点加入最短路径集合中。在此过程中，需要维护一个数组用来记录源节点到各个节点的距离，以及一个数组用来记录已经加入最短路径集合的节点，这些节点我们把它们叫做“已确定的节点”。

接下来就是实现贪心算法的细节。首先，需要初始化源节点到各个节点的距离为无穷大，但源节点到自身的距离为0。然后，将源节点加入“已确定的节点”中，同时将源节点到各个邻居节点的距离更新到距离数组中。接着，选择距离最短的邻居节点加入“已确定的节点”中，并更新该邻居节点到其余未确定节点的距离。这个过程不断迭代，直到所有节点都被加入到“已确定的节点”中为止。

C++代码如下：


#include <iostream>
#define INF 1000000000
using namespace std;
int n, source; // n 表示节点数量，source 表示源节点编号
int graph[1001][1001]; // 存储图中边的权值
int dist[1001]; // 存储源节点到各个节点的距离
bool visited[1001]; // 记录节点是否已经加入最短路径集合
void Dijkstra()
{
  // 初始化 dist 数组
  for (int i = 1; i <= n; i++)
  {
    dist[i] = INF;
  }
  dist[source] = 0; // 源节点到自身的距离为0
  // 初始化 visited 数组
  for (int i = 1; i <= n; i++)
  {
    visited[i] = false;
  }
  // 循环 n 次，每次确定一个节点
  for (int i = 1; i <= n; i++)
  {
    int minDist = INF;
    int minNode = -1;
    // 选取距离最短的节点加入最短路径集合中
    for (int j = 1; j <= n; j++)
    {
      if (!visited[j] && dist[j] < minDist)
      {
        minDist = dist[j];
        minNode = j;
      }
    }
    // 找不到可加入最短路径集合的节点
    if (minNode == -1)
    
      break;
    
    visited[minNode] = true;
    // 更新该节点的邻居节点到源节点的距离
    for (int j = 1; j <= n; j++)
    {
      if (!visited[j] && graph[minNode][j] != INF)
      {
        dist[j] = min(dist[j], dist[minNode] + graph[minNode][j]);
      }
    }
  }
}
int main()
{
  // 输入图的信息
  cin >> n >> source;
  for (int i = 1; i <= n; i++)
  {
    for (int j = 1; j <= n; j++)
    {
      cin >> graph[i][j];
      if (graph[i][j] == -1)
      {
        graph[i][j] = INF; // -1 表示无边，权值为无穷大
      }
    }
  }
  // 求解最短路径
  Dijkstra();
  // 输出结果
  for (int i = 1; i <= n; i++)
  {
    cout << dist[i] << endl;
  }
  return 0;
}

以上就是使用C++贪心算法解决单源点最短路径问题的过程和代码。贪心算法虽然简单，但是在实际应用中会出现局部最优解无法达到全局最优的情况，因此需要结合实际问题进行具体分析。

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

下一篇: C++统计字符串中英文字母数量

评论区

()

相似文章