C++求解两点间的最短距离 |21xrx.com

C++求解两点间的最短距离

2023-06-24 03:14:37 深夜i 18 0

C++ 求解两点最短距离

在计算机科学中，最短路径问题是一类重要的问题，它涉及从一个点到另一个点的起点和终点之间的最短路径。在图论中，最短路径问题也是一个经典的问题，涉及到树、图和网络等数据结构。本文将介绍如何使用C++求解两点间的最短距离。

在C++中，我们可以使用Dijkstra算法和Floyd算法来解决最短路径问题。Dijkstra算法是一种贪心算法，它通过从起点开始，选取到该点距离最小的点，逐步扩展出最短路径树，从而获得最短路径。Floyd算法则是一种动态规划算法，它通过维护已知节点间的最短路径，逐步推出全局最短路径。

接下来，我们以Dijkstra算法为例，来介绍如何使用C++求解两点间的最短路径。首先我们需要定义一个图类，并在其中定义一个求解最短路径的函数。


#include <vector>
#include <queue>
using namespace std;
class Graph{
private:
  int V; // 图的顶点数
  vector<pair<int, int>> *adj; // 邻接列表
public:
  Graph(int V);
  void addEdge(int u, int v, int w);
  void dijkstra(int src, int dest);
}
Graph::Graph(int V){
  this->V = V;
  adj = new vector<pair<int, int>>[V];
}
void Graph::addEdge(int u, int v, int w){
  adj[u].push_back(make_pair(v, w));
  adj[v].push_back(make_pair(u, w));
}
void Graph::dijkstra(int src, int dest){
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> > pq;
  vector<int> dist(V, INT_MAX);
  pq.push(make_pair(0, src));
  dist[src] = 0;
  while (!pq.empty()){
    int u = pq.top().second;
    pq.pop();
    for (auto i = adj[u].begin(); i != adj[u].end(); ++i){
      int v = (*i).first;
      int weight = (*i).second;
      if (dist[v] > dist[u] + weight){
        dist[v] = dist[u] + weight;
        pq.push(make_pair(dist[v], v));
      }
    }
  }
  printf("Shortest distance from %d to %d is %d", src, dest, dist[dest]);
}

在上面的代码中，我们利用了STL中的vector、pair和priority_queue等数据结构。其中priority_queue是C++中的优先队列，它可以方便地实现Dijkstra算法。

最后，我们可以在主程序中使用定义好的图类，并调用求解最短路径的函数。


int main(){
  int V = 5; // 图的顶点数
  Graph g(V);
  g.addEdge(0, 1, 9);
  g.addEdge(0, 2, 6);
  g.addEdge(0, 3, 5);
  g.addEdge(0, 4, 3);
  g.addEdge(2, 1, 2);
  g.addEdge(2, 3, 4);
  g.dijkstra(0, 1);
  return 0;
}

在上面的代码中，我们定义了一个有5个节点的图，并添加了相应的边。我们可以调用dijkstra函数，来求解从节点0到节点1的最短路径。在输出中，我们可以看到从节点0到节点1的最短距离是9。

总结一下，在C++中，我们可以使用Dijkstra算法和Floyd算法来求解两点间的最短路径。在实际应用中，我们可以通过定义图类，并使用相应的数据结构和算法，来快速求解实际问题中的最短路径问题。

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

下一篇: 如何在C++中生成SO文件

评论区

相似文章