21xrx.com
2025-07-09 10:14:05 Wednesday
文章检索 我的文章 写文章
C++求解两点间的最短距离
2023-06-24 03:14:37 深夜i     23     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算法来求解两点间的最短路径。在实际应用中,我们可以通过定义图类,并使用相应的数据结构和算法,来快速求解实际问题中的最短路径问题。

  
  

评论区