用C++解决最短路径问题

最短路径问题可以通过使用Dijkstra算法或者Bellman-Ford算法来解决。以下是使用C++实现这两种算法的示例代码：

1. 使用Dijkstra算法：

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

using namespace std;

const int INF = INT_MAX; // 无穷大

// 点类
class Point {
public:
    int id; // 点的编号
    int distance; // 从起点到该点的距离
    bool visited; // 是否访问过

    bool operator<(const Point &p) const {
        return distance > p.distance; // 比较点的距离，用于优先队列中的排序
    }
};

// 边类
class Edge {
public:
    int from; // 起点编号
    int to; // 终点编号
    int weight; // 权重
};

// 图类
class Graph {
public:
    int V; // 顶点数
    vector<vector<Edge>> adj; // 邻接表

    Graph(int V) {
        this->V = V;
        adj.resize(V);
    }

    void addEdge(int from, int to, int weight) {
        Edge edge = {from, to, weight};
        adj[from].push_back(edge);
    }

    vector<int> shortestPath(int start) {
        vector<int> distances(V, INF);
        priority_queue<Point> pq;
        Point s = {start, 0, false};
        pq.push(s);

        while (!pq.empty()) {
            Point p = pq.top();
            pq.pop();

            if (p.visited) continue;
            p.visited = true;
            distances[p.id] = p.distance;

            for (auto edge : adj[p.id]) {
                if (!p.visited) {
                    Point next = {edge.to, p.distance + edge.weight, false};
                    pq.push(next);
                }
            }
        }

        return distances;
    }
};

int main() {
    Graph g(5);
    g.addEdge(0, 1, 10);
    g.addEdge(0, 4, 5);
    g.addEdge(1, 2, 1);
    g.addEdge(1, 4, 2);
    g.addEdge(2, 3, 4);
    g.addEdge(3, 2, 6);
    g.addEdge(3, 0, 7);
    g.addEdge(4, 1, 3);
    g.addEdge(4, 2, 9);
    g.addEdge(4, 3, 2);

    vector<int> distances = g.shortestPath(0);

    for (int i = 0; i < distances.size(); i++) {
        cout << "Shortest distance from 0 to " << i << " is " << distances[i] << endl;
    }

    return 0;
}

2. 使用Bellman-Ford算法：

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

const int INF = INT_MAX; // 无穷大

// 边类
class Edge {
public:
    int from; // 起点编号
    int to; // 终点编号
    int weight; // 权重
};

// 图类
class Graph {
public:
    int V; // 顶点数
    vector<Edge> edges; // 边集合

    Graph(int V) {
        this->V = V;
    }

    void addEdge(int from, int to, int weight) {
        Edge edge = {from, to, weight};
        edges.push_back(edge);
    }

    vector<int> shortestPath(int start) {
        vector<int> distances(V, INF);
        distances[start] = 0;

        for (int i = 0; i < V - 1; i++) {
            for (auto edge : edges) {
                if (distances[edge.from] != INF && distances[edge.to] > distances[edge.from] + edge.weight) {
                    distances[edge.to] = distances[edge.from] + edge.weight;
                }
            }
        }

        return distances;
    }
};

int main() {
    Graph g(5);
    g.addEdge(0, 1, 10);
    g.addEdge(0, 4, 5);
    g.addEdge(1, 2, 1);
    g.addEdge(1, 4, 2);
    g.addEdge(2, 3, 4);
    g.addEdge(3, 2, 6);
    g.addEdge(3, 0, 7);
    g.addEdge(4, 1, 3);
    g.addEdge(4, 2, 9);
    g.addEdge(4, 3, 2);

    vector<int> distances = g.shortestPath(0);

    for (int i = 0; i < distances.size(); i++) {
        cout << "Shortest distance from 0 to " << i << " is " << distances[i] << endl;
    }

    return 0;
}

这两种算法在解决最短路径问题时的时间复杂度都是O(E*logV)，其中E是边数，V是顶点数。在实际应用中，Dijkstra算法适用于边权值为非负数的图，而Bellman-Ford算法适用于边权值可以是负数的图。