最短路问题 C++时间最优代码

最短路问题通常是指在一个有向图中找到两个顶点之间的最短路径，比如著名的Dijkstra算法和Floyd-Warshall算法。在C++中，对于大规模数据，Dijkstra算法通常是首选，因为它的时间复杂度相对较低，为O((E+V)logV)，其中E是边的数量，V是顶点的数量。

下面是使用Dijkstra算法的C++代码示例（使用优先队列实现），采用了贪心策略：

#include <vector>
#include <queue>
#include <climits>

using namespace std;

struct Edge {
    int to, weight;
};

class Graph {
private:
    vector<vector<Edge>> adj; // 邻接表表示图

public:
    void dijkstra(int start) {
        vector<int> dist(V, INT_MAX); // 初始化距离数组
        dist[start] = 0; // 设置起点的距离为0
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // 优先队列
        pq.push({0, start}); // 入队初始节点

        while (!pq.empty()) {
            int u = pq.top().second;
            pq.pop();

            for (const auto &edge : adj[u]) {
                int v = edge.to;
                int alt = dist[u] + edge.weight;

                if (alt < dist[v]) { // 更新邻接节点的距离
                    dist[v] = alt;
                    pq.push({dist[v], v});
                }
            }
        }

        // 输出最短路径
        for (int i = 0; i < V; ++i) {
            cout << "Shortest distance from node " << start << " to node " << i << ": " << dist[i] << endl;
        }
    }
};

在这个代码里，`adj`是一个邻接表，存储了每个节点的所有出边及其权重。`dijkstra()`函数接收起始节点，并通过优先队列持续探索未访问的节点，直到找到所有节点的最短路径。