最短路径问题用c++实现

最短路径问题是一个经典的图论问题，其中目标是找到从起点到终点的路径，使得路径上的边权重之和最小。在C++中，可以使用多种算法来解决这个问题，比如Dijkstra算法、Floyd-Warshall算法或A*搜索算法。

1. Dijkstra算法适用于带权有向无环图(DAG)或加权无向图，通常用于求单源最短路径。C++实现时，你可以使用优先队列（如`std::priority_queue`），初始化距离数组，然后按照贪心策略更新邻接节点的距离。

#include <queue>
void dijkstra(vector<pair<int, int>>& adj[], int src, vector<int>& dist, vector<bool>& visited)
{
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    dist[src] = 0;
    pq.push({0, src});

    while (!pq.empty())
    {
        int u = pq.top().second;
        pq.pop();
        if (visited[u])
            continue;

        visited[u] = true;

        for (auto v : adj[u])
        {
            int newDist = dist[u] + v.second;
            if (newDist < dist[v.first])
            {
                dist[v.first] = newDist;
                pq.push({dist[v.first], v.first});
            }
        }
    }
}

2. Floyd-Warshall算法适用于任意大小的有向或无向图，它可以在一次遍历中找出所有顶点对之间的最短路径。C++实现会使用动态规划的思想，创建一个矩阵来存储边长。

3. A*搜索算法则结合了启发式函数，适用于寻找二维网格环境中的最短路径，常见于游戏AI和地图导航等场景。